Zeyuan Allen Zhu
ABSTRACT
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).
Supplemental Material
Available for Download
Additional proofs.
- S. Acharya, P. Gibbons, V. Poosala, and S. Ramaswamy. Join synopses for approximate query answering. In SIGMOD, 1999. Google Scholar
Digital Library
- J. Ansel, C. Chan, Y. Wong, M. Olszewski, Q. Zhao, A. Edelman, and S. Amarasinghe. Petabricks: A language and compiler for algorithmic choice. In PLDI, 2009. Google ScholarDigital Library
- W. Baek and T. Chilimbi. Green: A framework for supporting energy-conscious programming using controlled approximation. In PLDI '10. Google ScholarDigital Library
- L. Chakrapani, K. Muntimadugu, A. Lingamneni, J. George, and K. Palem. Highly energy and performance efficient embedded computing through approximately correct arithmetic: A mathematical foundation and preliminary experimental validation. In CASES, 2008. Google ScholarDigital Library
- S. Chaudhuri, S. Gulwani, and R. Lublinerman. Continuity analysis of programs. In POPL, 2010. Google ScholarDigital Library
- S. Chaudhuri, S. Gulwani, R. Lublinerman, and S. Navidpour. Proving Programs Robust. In FSE, 2011. Google ScholarDigital Library
- S. Chaudhuri and A. Solar-Lezama. Smooth interpretation. In PLDI, 2010. Google ScholarDigital Library
- S. Chaudhuri and A. Solar-Lezama. Smoothing a program soundly and robustly. In CAV, 2011. Google ScholarDigital Library
- J. Flinn and M. Satyanarayanan. Energy-aware adaptation for mobile applications. In SOSP, 1999. Google ScholarDigital Library
- R. Hameed, W. Qadeer, M. Wachs, O. Azizi, A. Solomatnikov, B. Lee, S. Richardson, C. Kozyrakis, and M. Horowitz. Understanding sources of inefficiency in general-purpose chips. In ISCA, 2010. Google ScholarDigital Library
- J. Hellerstein, P. Haas, and H. Wang. Online aggregation. In SIGMOD/PODS, 1997. Google ScholarDigital Library
- H. Hoffman, S. Sidiroglou, M. Carbin, S. Misailovic, A. Agarwal, and M. Rinard. Dynamic knobs for power-aware computing. In ASPLOS, 2011. Google ScholarDigital Library
- H. Hoffmann, M. Maggio, M. D. Santambrogio, A. Leva, and A. Agarwal. Seec: A general and extensible framework for self-aware computing. Technical Report MIT-CSAIL-TR-2011-046, 2011.Google Scholar
- H. Hoffmann, S. Misailovic, S. Sidiroglou, A. Agarwal, and M. Rinard. Using Code Perforation to Improve Performance, Reduce Energy Consumption, and Respond to Failures. Technical Report MIT-CSAIL-TR-2009-042, 2009.Google Scholar
- W.-C. Hou, G. Ozsoyoglu, and B. K. Taneja. Processing aggregate relational queries with hard time constraints. SIGMOD, 1989. Google ScholarDigital Library
- Y. Hu, S. Sundara, and J. Srinivasan. Supporting time-constrained SQL queries in Oracle. VLDB, 2007. Google ScholarDigital Library
- S. Liu, K. Pattabiraman, T. Moscibroda, and B. Zorn. Flikker: Saving dram refresh-power through critical data partitioning. ASPLOS, 2011. Google ScholarDigital Library
- R. Majumdar and I. Saha. Symbolic robustness analysis. In RTSS '09. Google ScholarDigital Library
- R. Majumdar, I. Saha, and Z. Wang. Systematic testing for control applications. In MEMOCODE, 2010.Google ScholarDigital Library
- J. Meng, S. Chakradhar, and A. Raghunathan. Best-Effort Parallel Execution Framework for Recognition and Mining Applications. In IPDPS, 2009. Google ScholarDigital Library
- J. Meng, A. Raghunathan, and S. B. S. Chakradhar. Exploiting the Forgiving Nature of Applications for Scalable Parallel Execution. In IPDPS, 2010.Google Scholar
- S. Misailovic, D. Roy, and M. Rinard. Probabilistic and statistical analysis of perforated patterns. Technical Report MIT-CSAIL-TR-2011-003, January 2011.Google Scholar
- S. Misailovic, D. Roy, and M. Rinard. Probabilistically Accurate Program Transformations. In SAS, 2011. Google ScholarDigital Library
- S. Misailovic, S. Sidiroglou, H. Hoffmann, and M. Rinard. Quality of service profiling. In ICSE, 2010. Google ScholarDigital Library
- R. Motwani and P. Raghavan. Randomized algorithms. Cambridge University Press, 1995. Google ScholarDigital Library
- J. Reed and B. C. Pierce. Distance makes the types grow stronger: a calculus for differential privacy. In ICFP, 2010. Google ScholarDigital Library
- M. Rinard. Probabilistic accuracy bounds for fault-tolerant computations that discard tasks. In ICS, 2006. Google ScholarDigital Library
- M. Rinard. Using early phase termination to eliminate load imbalances at barrier synchronization points. In OOPSLA, 2007. Google ScholarDigital Library
- R. Rubinfeld. Sublinear time algorithms. In Intl. Congress of Mathematicians, 2006.Google Scholar
- A. Sampson, W. Dietl, E. Fortuna, D. Gnanapragasam, L. Ceze, and D. Grossman. EnerJ: approximate data types for safe and general low-power computation. In PLDI, 2011. Google ScholarDigital Library
- S. Sidiroglou, S. Misailovic, H. Hoffmann, and M. Rinard. Managing Performance vs. Accuracy Tradeoffs With Loop Perforation. In FSE, 2011.Google Scholar
- K. Sohraby, D. Minoli, and T. Znati. Wireless sensor networks: technology, protocols, and applications. Wiley-Blackwell, 2007. Google ScholarDigital Library
- J. Sorber, A. Kostadinov, M. Garber, M. Brennan, M. D. Corner, and E. D. Berger. Eon: a language and runtime system for perpetual systems. In SenSys, 2007. Google ScholarDigital Library
- P. Stanley-Marbell and D. Marculescu. Deviation-Tolerant Computation in Concurrent Failure-Prone Hardware. Technical Report ESR-2008-01, Eindhoven University of Technology, 2008.Google Scholar
- D. Suciu, D. Olteanu, C. Ré, and C. Koch. Probabilistic Databases. Morgan-Claypool, 2011. Google ScholarDigital Library
Index Terms
- Randomized accuracy-aware program transformations for efficient approximate computations
Recommendations
Randomized accuracy-aware program transformations for efficient approximate computations
POPL '12Despite 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 ...
Randomized Approximate Nearest Neighbor Search with Limited Adaptivity
Special Issue on SPAA 2016We study the complexity of parallel data structures for approximate nearest neighbor search in d-dimensional Hamming space {0,1}d. A classic model for static data structures is the cell-probe model [27]. We consider a cell-probe model with limited ...
Randomized Approximate Nearest Neighbor Search with Limited Adaptivity
SPAA '16: Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and ArchitecturesWe study the problem of approximate nearest neighbor search in $d$-dimensional Hamming space {0,1}d. We study the complexity of the problem in the famous cell-probe model, a classic model for data structures. We consider algorithms in the cell-probe ...
Comments