research-article

Randomized accuracy-aware program transformations for efficient approximate computations

Authors:

Zeyuan Allen Zhu,

Sasa Misailovic,

Jonathan A. Kelner,

Martin RinardAuthors Info & Claims

POPL '12: Proceedings of the 39th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages

Pages 441 - 454

https://doi.org/10.1145/2103656.2103710

Published: 25 January 2012 Publication History

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).

Supplementary Material

JPG File (popl_7a_2.jpg)

Download
15.38 KB

ZIP File (popl075.zip)

Additional proofs.

Download
169.40 KB

MP4 File (popl_7a_2.mp4)

Download
184.79 MB

References

[1]

S. Acharya, P. Gibbons, V. Poosala, and S. Ramaswamy. Join synopses for approximate query answering. In SIGMOD, 1999.

Digital Library

[2]

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.

Digital Library

[3]

W. Baek and T. Chilimbi. Green: A framework for supporting energy-conscious programming using controlled approximation. In PLDI '10.

Digital Library

[4]

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.

Digital Library

[5]

S. Chaudhuri, S. Gulwani, and R. Lublinerman. Continuity analysis of programs. In POPL, 2010.

Digital Library

[6]

S. Chaudhuri, S. Gulwani, R. Lublinerman, and S. Navidpour. Proving Programs Robust. In FSE, 2011.

Digital Library

[7]

S. Chaudhuri and A. Solar-Lezama. Smooth interpretation. In PLDI, 2010.

Digital Library

[8]

S. Chaudhuri and A. Solar-Lezama. Smoothing a program soundly and robustly. In CAV, 2011.

Digital Library

[9]

J. Flinn and M. Satyanarayanan. Energy-aware adaptation for mobile applications. In SOSP, 1999.

Digital Library

[10]

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.

Digital Library

[11]

J. Hellerstein, P. Haas, and H. Wang. Online aggregation. In SIGMOD/PODS, 1997.

Digital Library

[12]

H. Hoffman, S. Sidiroglou, M. Carbin, S. Misailovic, A. Agarwal, and M. Rinard. Dynamic knobs for power-aware computing. In ASPLOS, 2011.

Digital Library

[13]

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.

[14]

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.

[15]

W.-C. Hou, G. Ozsoyoglu, and B. K. Taneja. Processing aggregate relational queries with hard time constraints. SIGMOD, 1989.

Digital Library

[16]

Y. Hu, S. Sundara, and J. Srinivasan. Supporting time-constrained SQL queries in Oracle. VLDB, 2007.

Digital Library

[17]

S. Liu, K. Pattabiraman, T. Moscibroda, and B. Zorn. Flikker: Saving dram refresh-power through critical data partitioning. ASPLOS, 2011.

Digital Library

[18]

R. Majumdar and I. Saha. Symbolic robustness analysis. In RTSS '09.

Digital Library

[19]

R. Majumdar, I. Saha, and Z. Wang. Systematic testing for control applications. In MEMOCODE, 2010.

Digital Library

[20]

J. Meng, S. Chakradhar, and A. Raghunathan. Best-Effort Parallel Execution Framework for Recognition and Mining Applications. In IPDPS, 2009.

Digital Library

[21]

J. Meng, A. Raghunathan, and S. B. S. Chakradhar. Exploiting the Forgiving Nature of Applications for Scalable Parallel Execution. In IPDPS, 2010.

[22]

S. Misailovic, D. Roy, and M. Rinard. Probabilistic and statistical analysis of perforated patterns. Technical Report MIT-CSAIL-TR-2011-003, January 2011.

[23]

S. Misailovic, D. Roy, and M. Rinard. Probabilistically Accurate Program Transformations. In SAS, 2011.

Digital Library

[24]

S. Misailovic, S. Sidiroglou, H. Hoffmann, and M. Rinard. Quality of service profiling. In ICSE, 2010.

Digital Library

[25]

R. Motwani and P. Raghavan. Randomized algorithms. Cambridge University Press, 1995.

Digital Library

[26]

J. Reed and B. C. Pierce. Distance makes the types grow stronger: a calculus for differential privacy. In ICFP, 2010.

Digital Library

[27]

M. Rinard. Probabilistic accuracy bounds for fault-tolerant computations that discard tasks. In ICS, 2006.

Digital Library

[28]

M. Rinard. Using early phase termination to eliminate load imbalances at barrier synchronization points. In OOPSLA, 2007.

Digital Library

[29]

R. Rubinfeld. Sublinear time algorithms. In Intl. Congress of Mathematicians, 2006.

[30]

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.

Digital Library

[31]

S. Sidiroglou, S. Misailovic, H. Hoffmann, and M. Rinard. Managing Performance vs. Accuracy Tradeoffs With Loop Perforation. In FSE, 2011.

[32]

K. Sohraby, D. Minoli, and T. Znati. Wireless sensor networks: technology, protocols, and applications. Wiley-Blackwell, 2007.

Digital Library

[33]

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.

Digital Library

[34]

P. Stanley-Marbell and D. Marculescu. Deviation-Tolerant Computation in Concurrent Failure-Prone Hardware. Technical Report ESR-2008-01, Eindhoven University of Technology, 2008.

[35]

D. Suciu, D. Olteanu, C. Ré, and C. Koch. Probabilistic Databases. Morgan-Claypool, 2011.

Digital Library

Cited By

Misailovic S(2022)Accuracy-Aware CompilersApproximate Computing Techniques10.1007/978-3-030-94705-7_7(177-214)Online publication date: 3-Jan-2022
https://doi.org/10.1007/978-3-030-94705-7_7
Stanley-Marbell PAlaghi ACarbin MDarulova EDolecek LGerstlauer AGillani GJevdjic DMoreau TCacciotti MDaglis AJerger NFalsafi BMisailovic SSampson AZufferey D(2020)Exploiting Errors for EfficiencyACM Computing Surveys10.1145/339489853:3(1-39)Online publication date: 12-Jun-2020
https://dl.acm.org/doi/10.1145/3394898
Ismail LMaterwala H(2020)Computing Server Power Modeling in a Data CenterACM Computing Surveys10.1145/339060553:3(1-34)Online publication date: 12-Jun-2020
https://dl.acm.org/doi/10.1145/3390605
Show More Cited By

Index Terms

Randomized accuracy-aware program transformations for efficient approximate computations

Recommendations

Randomized accuracy-aware program transformations for efficient approximate computations
POPL '12

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 ...
Randomized Approximate Nearest Neighbor Search with Limited Adaptivity
Special Issue on SPAA 2016

We 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 Architectures

We 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

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

POPL '12: Proceedings of the 39th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages

January 2012

602 pages

ISBN:9781450310833

DOI:10.1145/2103656

General Chair:
John Field
Google, USA
,
Program Chair:
Michael Hicks
University of Maryland, College Park, USA

ACM SIGPLAN Notices Volume 47, Issue 1
POPL '12
January 2012
569 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/2103621
Issue’s Table of Contents

Copyright © 2012 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGPLAN: ACM Special Interest Group on Programming Languages

In-Cooperation

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 25 January 2012

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

POPL '12

Sponsor:

SIGPLAN

POPL '12: The 39th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages

January 25 - 27, 2012

PA, Philadelphia, USA

Acceptance Rates

Overall Acceptance Rate 860 of 4,328 submissions, 20%

Upcoming Conference

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

100
Total Citations
View Citations
695
Total Downloads

Downloads (Last 12 months)12
Downloads (Last 6 weeks)0

Reflects downloads up to 10 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Misailovic S(2022)Accuracy-Aware CompilersApproximate Computing Techniques10.1007/978-3-030-94705-7_7(177-214)Online publication date: 3-Jan-2022
https://doi.org/10.1007/978-3-030-94705-7_7
Stanley-Marbell PAlaghi ACarbin MDarulova EDolecek LGerstlauer AGillani GJevdjic DMoreau TCacciotti MDaglis AJerger NFalsafi BMisailovic SSampson AZufferey D(2020)Exploiting Errors for EfficiencyACM Computing Surveys10.1145/339489853:3(1-39)Online publication date: 12-Jun-2020
https://dl.acm.org/doi/10.1145/3394898
Ismail LMaterwala H(2020)Computing Server Power Modeling in a Data CenterACM Computing Surveys10.1145/339060553:3(1-34)Online publication date: 12-Jun-2020
https://dl.acm.org/doi/10.1145/3390605
Anwar SKhan SBarnes N(2020)A Deep Journey into Super-resolutionACM Computing Surveys10.1145/339046253:3(1-34)Online publication date: 28-May-2020
https://dl.acm.org/doi/10.1145/3390462
Welsh TBenkhelifa E(2020)On Resilience in Cloud ComputingACM Computing Surveys10.1145/338892253:3(1-36)Online publication date: 28-May-2020
https://dl.acm.org/doi/10.1145/3388922
Prenkaj BVelardi PStilo GDistante DFaralli S(2020)A Survey of Machine Learning Approaches for Student Dropout Prediction in Online CoursesACM Computing Surveys10.1145/338879253:3(1-34)Online publication date: 28-May-2020
https://dl.acm.org/doi/10.1145/3388792
Alhakamy ATuceryan M(2020)Real-time Illumination and Visual Coherence for Photorealistic Augmented/Mixed RealityACM Computing Surveys10.1145/338649653:3(1-34)Online publication date: 28-May-2020
https://dl.acm.org/doi/10.1145/3386496
Liu XBuyya R(2020)Resource Management and Scheduling in Distributed Stream Processing SystemsACM Computing Surveys10.1145/335539953:3(1-41)Online publication date: 28-May-2020
https://dl.acm.org/doi/10.1145/3355399
Castro-Godinez JShafique MHenkel J(2020)Towards Quality-Driven Approximate Software Generation for Accurate Hardware: Work-in-Progress2020 International Conference on Compilers, Architecture, and Synthesis for Embedded Systems (CASES)10.1109/CASES51649.2020.9243814(12-14)Online publication date: 20-Sep-2020
https://doi.org/10.1109/CASES51649.2020.9243814
Sharif HSrivastava PHuzaifa MKotsifakou MJoshi KSarita YZhao NAdve VMisailovic SAdve S(2019)ApproxHPVM: a portable compiler IR for accuracy-aware optimizationsProceedings of the ACM on Programming Languages10.1145/33606123:OOPSLA(1-30)Online publication date: 10-Oct-2019
https://dl.acm.org/doi/10.1145/3360612
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten