ACM SIGPLAN Notices · 2012 · 60 citations · 32 references
ComputingComputer ScienceCompilersProgramming LanguagesApproximation AlgorithmsRandomized ComputationApproximate ComputingProgram OptimizationProgram Transformation
Despite the fact that approximate computations have come to dominate many areas of computer science, the field of program transformations has focused almost exclusively on traditional semantics-preserving transformations that do not attempt to exploit the opportunity, available in many computations, to acceptably trade off accuracy for benefits such as increased performance and reduced resource consumption. We present a model of computation for approximate computations and an algorithm for optimizing these computations. The algorithm works with two classes of transformations: substitution transformations (which select one of a number of available implementations for a given function, with each implementation offering a different combination of accuracy and resource consumption) and sampling transformations (which randomly discard some of the inputs to a given reduction). The algorithm produces a (1+ε) randomized approximation to the optimal randomized computation (which minimizes resource consumption subject to a probabilistic accuracy specification in the form of a maximum expected error or maximum error variance).
32
Joseph M. Hellerstein, Peter J. Haas, Helen J. Wang · 1997 · 928 citations · Full text
Wireless Sensor Networks: Technology, Protocols, and Applications
Sensor Review · 2007 · 836 citations
Energy-aware adaptation for mobile applications
Jason Flinn, Mahadev Satyanarayanan · 1999 · 599 citations
Adrian Sampson, Werner Dietl, Emily Fortuna et al. · ACM SIGPLAN Notices · 2011 · 590 citations
Managing performance vs. accuracy trade-offs with loop perforation
Stelios Sidiroglou-Douskos, Saša Misailovíc, Henry Hoffmann et al. · 2011 · 500 citations · Full text