research-article

Public Access

Proactive Control of Approximate Programs

Authors:

Andrew Lenharth,

Donald S. Fussell,

Keshav PingaliAuthors Info & Claims

ASPLOS '16: Proceedings of the Twenty-First International Conference on Architectural Support for Programming Languages and Operating Systems

Pages 607 - 621

https://doi.org/10.1145/2872362.2872402

Published: 25 March 2016 Publication History

Abstract

Approximate computing trades off accuracy of results for resources such as energy or computing time. There is a large and rapidly growing literature on approximate computing that has focused mostly on showing the benefits of approximate computing. However, we know relatively little about how to control approximation in a disciplined way. In this paper, we address the problem of controlling approximation for non-streaming programs that have a set of "knobs" that can be dialed up or down to control the level of approximation of different components in the program. We formulate this control problem as a constrained optimization problem, and describe a system called Capri that uses machine learning to learn cost and error models for the program, and uses these models to determine, for a desired level of approximation, knob settings that optimize metrics such as running time or energy usage. Experimental results with complex benchmarks from different problem domains demonstrate the effectiveness of this approach.

References

[1]

Cubist. https://www.rulequest.com/cubist-info.html.

[2]

Jason Ansel, Cy Chan, Yee Lok Wong, Marek Olszewski, Qin Zhao, Alan Edelman, and Saman Amarasinghe. Petabricks: A language and compiler for algorithmic choice. In Proceedings of the 2009 ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI '09, 2009.

Digital Library

[3]

Jason Ansel, Yee Lok Wong, Cy Chan, Marek Olszewski, Alan Edelman, and Saman Amarasinghe. Language and compiler support for auto-tuning variable-accuracy algorithms. Proceedings of the 2013 IEEE/ACM International Symposium on Code Generation and Optimization (CGO), 2011.

[4]

Woongki Baek and Trishul M. Chilimbi. Green: A framework for supporting energy-conscious programming using controlled approximation. In Proceedings of the 2010 ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI '10, 2010.

Digital Library

[5]

Judit Bar-Ilan, Mazlita Mat-Hassan, and Mark Levene. Methods for comparing rankings of search engine results. Comput. Netw., 2006.

Digital Library

[6]

Christian Bienia. Benchmarking Modern Multiprocessors. PhD thesis, Princeton University, January 2011.

Digital Library

[7]

Léon Bottou. Large-scale machine learning with stochastic gradient descent. In Proceedings of the 19th International Conference on Computational Statistics (COMPSTAT'2010), 2010.

[8]

John Burkardt. 3d graphics models. http://people.sc.fsu.edu/jburkardt/data/ply/ply.html.

[9]

Simone Campanoni, Glenn Holloway, Gu-Yeon Wei, and David Brooks. Helix-up: Relaxing program semantics to unleash parallelization. In Proceedings of the 13th Annual IEEE/ACM International Symposium on Code Generation and Optimization, CGO '15, 2015.

[10]

Michael Carbin, Sasa Misailovic, and Martin C. Rinard. Verifying quantitative reliability for programs that execute on unreliable hardware. In Proceedings of the 2013 ACM SIGPLAN International Conference on Object Oriented Programming Systems Languages and Applications, OOPSLA '13, 2013.

Digital Library

[11]

Swarat Chaudhuri, Sumit Gulwani, and Roberto Lublinerman. Continuity and robustness of programs. Commun. ACM, 55(8):107--115, August 2012.

Digital Library

[12]

Swarat Chaudhuri and Armando Solar-Lezama. Smooth interpretation. In Proceedings of the 2010 ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI '10, 2010.

Digital Library

[13]

Thomas Cormen, Charles Leiserson, Ronald Rivest, and Clifford Stein, editors. Introduction to Algorithms. MIT Press, 2001.

Digital Library

[14]

Yufei Ding, Jason Ansel, Kalyan Veeramachaneni, Xipeng Shen, Una-May O'Reilly, and Saman Amarasinghe. Autotuning algorithmic choice for input sensitivity. In ACM SIGPLAN Conference on Programming Language Design and Implementation, June 2015.

Digital Library

[15]

Hadi Esmaeilzadeh, Adrian Sampson, Luis Ceze, and Doug Burger. Architecture support for disciplined approximate programming. In Proceedings of the Seventeenth International Conference on Architectural Support for Programming Languages and Operating Systems, ASPLOS XVII, 2012.

Digital Library

[16]

Hadi Esmaeilzadeh, Adrian Sampson, Luis Ceze, and Doug Burger. Neural acceleration for general-purpose approximate programs. In Proceedings of the 2012 45th Annual IEEE/ACM International Symposium on Microarchitecture, MICRO-45, 2012.

Digital Library

[17]

Shuangde Fang, Zidong Du, Yuntan Fang, Yuanjie Huang, Yang Chen, Lieven Eeckhout, Olivier Temam, Huawei Li, Yunji Chen, and Chengyong Wu. Performance portability across heterogeneous socs using a generalized library-based approach. ACM Trans. Archit. Code Optim., 2014.

Digital Library

[18]

Davide Gadioli, Gianluca Palermo, and Cristina Silvano. Application autotuning to support runtime adaptivity in multicorearchitectures. In SAMOS XV, 2015.

[19]

Michael Garland and Paul S. Heckbert. Surface simplification using quadric error metrics. In Proceedings of the 24th Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH '97, 1997.

Digital Library

[20]

Inigo Goiri, Ricardo Bianchini, Santosh Nagarakatte, and Thu D. Nguyen. Approxhadoop: Bringing approximations to mapreduce frameworks. In Proceedings of the Twentieth International Conference on Architectural Support for Programming Languages and Operating Systems, ASPLOS '15, 2015.

Digital Library

[21]

Henry Hoffmann, Anant Agarwal, and Srinivas Devadas. Selecting spatiotemporal patterns for development of parallel applications. IEEE Transactions on Parallel and Distributed Systems, 23(10):1970--1982, 2012.

Digital Library

[22]

Henry Hoffmann, Stelios Sidiroglou, Michael Carbin, Sasa Misailovic, Anant Agarwal, and Martin Rinard. Dynamic knobs for responsive power-aware computing. In Proceedings of the Sixteenth International Conference on Architectural Support for Programming Languages and Operating Systems, ASPLOS XVI, 2011.

Digital Library

[23]

Søren Højsgaard. Graphical independence networks with the grain package for r. Journal of Statistical Software, 46, 2012.

[24]

Benjamin Kuo. Automatic control systems. Prentice-Hall Publishers, 1991.

[25]

Jure Leskovec. Stanford large network dataset collection(snap). http://snap.stanford.edu/data/.

[26]

Chih-Jen Lin. Libsvm classification dataset. http://www.csie.ntu.edu.tw/cjlin/libsvmtools/datasets/.

[27]

Divya Mahajan, Amir Yazdanbakhsh, Jongse Park, Bradley Thwaites, and Hadi Esmaeilzadeh. Prediction-based qualitycontrol for approximate accelerators. In Second Workshop on Approximate Computing Across the System Stack, WACAS, 2015.

[28]

Shawn Martin, W. Michael Brown, Richard Klavans, and Kevin W. Boyack. Openord: an open-source toolbox for large graph layout. volume 7868, 2011.

[29]

Joshua San Miguel, Mario Badr, and Natalie Enright Jerger. Load value approximation. In Proceedings of the 47th Annual IEEE/ACM International Symposium on Microarchitecture, MICRO-47, 2014.

Digital Library

[30]

Sasa Misailovic, Michael Carbin, Sara Achour, Zichao Qi, and Martin C. Rinard. Chisel: Reliability- and accuracy-aware optimization of approximate computational kernels. In Proceedings of the 2014 ACM International Conference on Object Oriented Programming Systems, Languages and Applications, OOPSLA '14, 2014.

Digital Library

[31]

R. E. Neapolitan. Learning Bayesian Networks. Prentice Hall, 2003.

Digital Library

[32]

Miguel A. Otaduy and Ming C. Lin. Clods: Dual hierarchies for multiresolution collision detection. In Proceedings of the 2003 Eurographics/ACM SIGGRAPH Symposium on Geometry Processing, SGP '03, 2003.

[33]

Krishna V. Palem. Energy aware computing through probabilistic switching: A study of limits. IEEE Trans. Comput., 2005.

Digital Library

[34]

J. R. Quinlan. Learning with continuous classes. In Proceedings of the Australian Joint Conference on Artificial Intelligence, pages 343--348. World Scientific, 1992.

[35]

Martin Rinard. Probabilistic accuracy bounds for fault-tolerant computations that discard tasks. In Proceedings of the 20th Annual International Conference on Supercomputing, ICS '06, 2006.

Digital Library

[36]

Martin C. Rinard. Using early phase termination to eliminate load imbalances at barrier synchronization points. In Proceedings of the 22Nd Annual ACM SIGPLAN Conference on Object-oriented Programming Systems and Applications, OOPSLA '07, 2007.

Digital Library

[37]

Michael Ringenburg, Adrian Sampson, Isaac Ackerman, Luis Ceze, and Dan Grossman. Monitoring and debugging the quality of results in approximate programs. In Proceedings of the Twentieth International Conference on Architectural Support for Programming Languages and Operating Systems, ASPLOS '15, 2015.

Digital Library

[38]

Cindy Rubio-González, Cuong Nguyen, Hong Diep Nguyen, James Demmel, William Kahan, Koushik Sen, David H. Bailey, Costin Iancu, and David Hough. Precimonious: Tuning assistant for floating-point precision. In Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis, SC '13, 2013.

Digital Library

[39]

Mehrzad Samadi, Davoud Anoushe Jamshidi, Janghaeng Lee, and Scott Mahlke. Paraprox: Pattern-based approximation for data parallel applications. In Proceedings of the 19th International Conference on Architectural Support for Programming Languages and Operating Systems, ASPLOS '14, 2014.

Digital Library

[40]

Mehrzad Samadi, Janghaeng Lee, D. Anoushe Jamshidi, Amir Hormati, and Scott Mahlke. Sage: Self-tuning approximation for graphics engines. In Proceedings of the 46th Annual IEEE/ACM International Symposium on Microarchitecture, MICRO-46, 2013.

Digital Library

[41]

Adrian Sampson, Werner Dietl, Emily Fortuna, Danushen Gnanapragasam, Luis Ceze, and Dan Grossman. Enerj: Approximate data types for safe and general low-power computation. In Proceedings of the 32Nd ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI '11, 2011.

[42]

Adrian Sampson, Jacob Nelson, Karin Strauss, and Luis Ceze. Approximate storage in solid-state memories. In Proceedings of the 46th Annual IEEE/ACM International Symposium on Microarchitecture, MICRO-46, 2013.

Digital Library

[43]

Eric Schkufza, Rahul Sharma, and Alex Aiken. Stochastic optimization of floating-point programs with tunable precision. In Proceedings of the 35th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI '14, 2014.

Digital Library

[44]

M. Scutari. Learning Bayesian Networks with the bnlearn R Package. Journal of Statistical Software, 35, 2010.

[45]

M. Shoushtari, A. BanaiyanMofrad, and N. Dutt. Exploiting partially-forgetful memories for approximate computing. Embedded Systems Letters, IEEE, March 2015.

[46]

Stelios Sidiroglou-Douskos, Sasa Misailovic, Henry Hoffmann, and Martin Rinard. Managing performance vs. accuracy trade-offs with loop perforation. In Proceedings of the 19th ACM SIGSOFT Symposium and the 13th European Conference on Foundations of Software Engineering, ESEC/FSE '11, 2011.

Digital Library

[47]

Jean-Jacques Slotine and Weiping Li. Applied Nonlinear control. Prenctice-Hall Publishers, 1991.

[48]

Soeren Sonnenburg, Vojtech Franc, Elad Yom-Tov, and Michele Sebag. Pascal large scale learning challenge. http://largescale.ml.tu-berlin.de.

[49]

Karthik Swaminathan, Chung-Ching Lin, Augusto Vega, Alper Buyuktosunoglu, Pradip Bose, and Sharathchandra Pankanti. A case for approximate computing in real-time mobile cognition. In Second Workshop on Approximate Computing Across the System Stack, WACAS, 2015.

[50]

TF3DM. 3d graphics models. http://tf3dm.com.

[51]

L. G. Valiant. A theory of the learnable. CACM, 27(11), 1984.

[52]

Joyce Jiyoung Whang, Xin Sui, and Inderjit S. Dhillon. Scalable and memory-efficient clustering of large-scale social networks. In ICDM, 2012.

Digital Library

[53]

R. Zafarani and H. Liu. Social computing data repository at ASU, 2009. http://socialcomputing.asu.edu.

[54]

Andreas Zeller and Ralf Hildebrandt. Simplifying and isolating failure-inducing input. IEEE Trans. Softw. Eng., 28(2):183--200, February 2002.

Digital Library

[55]

Zeyuan Allen Zhu, Sasa Misailovic, Jonathan A. Kelner, and Martin Rinard. Randomized accuracy-aware program transformations for efficient approximate computations. In Proceedings of the 39th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL '12, 2012.

Digital Library

Cited By

Pervaiz AYang YDuracz ABartha FSai RImes CCartwright RPalem KLu SHoffmann HScholliers CSinger J(2022)GOAL: Supporting General and Dynamic Adaptation in Computing SystemsProceedings of the 2022 ACM SIGPLAN International Symposium on New Ideas, New Paradigms, and Reflections on Programming and Software10.1145/3563835.3567655(16-32)Online publication date: 29-Nov-2022
https://dl.acm.org/doi/10.1145/3563835.3567655
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
Masadeh MHasan OTahar S(2021)Machine-Learning-Based Self-Tunable Design of Approximate ComputingIEEE Transactions on Very Large Scale Integration (VLSI) Systems10.1109/TVLSI.2021.305624329:4(800-813)Online publication date: Apr-2021
https://doi.org/10.1109/TVLSI.2021.3056243
Show More Cited By

Index Terms

Proactive Control of Approximate Programs

Recommendations

Proactive Control of Approximate Programs
ASPLOS '16

Approximate computing trades off accuracy of results for resources such as energy or computing time. There is a large and rapidly growing literature on approximate computing that has focused mostly on showing the benefits of approximate computing. ...
Proactive Control of Approximate Programs
ASPLOS'16

Approximate computing trades off accuracy of results for resources such as energy or computing time. There is a large and rapidly growing literature on approximate computing that has focused mostly on showing the benefits of approximate computing. ...
On the existence of solutions to compact dynamic optimization problems

We consider a system where, at each stagen ź {1, 2, ...}=N, an elementxn* is to be chosen out of a nonempty, closed, feasible regionAn in a compact semigroupX, so as to achieve a sequence $$\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{x} $$...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ASPLOS '16: Proceedings of the Twenty-First International Conference on Architectural Support for Programming Languages and Operating Systems

March 2016

824 pages

ISBN:9781450340915

DOI:10.1145/2872362

General Chair:
Tom Conte
Georgia Tech, USA
,
Program Chair:
Yuanyuan Zhou
University of California, San Diego, USA

ACM SIGPLAN Notices Volume 51, Issue 4
ASPLOS '16
April 2016
774 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/2954679
Editor:
Andy Gill
University of Kansas, Lawrence, KS
Issue’s Table of Contents
ACM SIGARCH Computer Architecture News Volume 44, Issue 2
ASPLOS'16
May 2016
774 pages
ISSN:0163-5964
DOI:10.1145/2980024
Editor:
Doug DeGroot
acm dot org
Issue’s Table of Contents

Copyright © 2016 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

In-Cooperation

SIGBED: ACM Special Interest Group on Embedded Systems

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 25 March 2016

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Conference

ASPLOS '16

Sponsor:

ASPLOS '16: Architectural Support for Programming Languages and Operating Systems

April 2 - 6, 2016

Georgia, Atlanta, USA

Acceptance Rates

ASPLOS '16 Paper Acceptance Rate 53 of 232 submissions, 23%;

Overall Acceptance Rate 535 of 2,713 submissions, 20%

Upcoming Conference

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

47
Total Citations
View Citations
2,167
Total Downloads

Downloads (Last 12 months)164
Downloads (Last 6 weeks)20

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Pervaiz AYang YDuracz ABartha FSai RImes CCartwright RPalem KLu SHoffmann HScholliers CSinger J(2022)GOAL: Supporting General and Dynamic Adaptation in Computing SystemsProceedings of the 2022 ACM SIGPLAN International Symposium on New Ideas, New Paradigms, and Reflections on Programming and Software10.1145/3563835.3567655(16-32)Online publication date: 29-Nov-2022
https://dl.acm.org/doi/10.1145/3563835.3567655
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
Masadeh MHasan OTahar S(2021)Machine-Learning-Based Self-Tunable Design of Approximate ComputingIEEE Transactions on Very Large Scale Integration (VLSI) Systems10.1109/TVLSI.2021.305624329:4(800-813)Online publication date: Apr-2021
https://doi.org/10.1109/TVLSI.2021.3056243
Vitali EGadioli DPalermo GGolasowski MBispo JPinto PMartinovic JSlaninova KCardoso JSilvano C(2021)An Efficient Monte Carlo-Based Probabilistic Time-Dependent Routing Calculation Targeting a Server-Side Car Navigation SystemIEEE Transactions on Emerging Topics in Computing10.1109/TETC.2019.29198019:2(1006-1019)Online publication date: 1-Apr-2021
https://doi.org/10.1109/TETC.2019.2919801
Akram RMandal SMuzahid A(2021)XMeter: Finding Approximable Functions and Predicting Their AccuracyIEEE Transactions on Computers10.1109/TC.2020.300508370:7(1081-1093)Online publication date: 1-Jul-2021
https://doi.org/10.1109/TC.2020.3005083
Ravi GMiguel JLipasti M(2020)SHASTAACM Transactions on Architecture and Code Optimization10.1145/341237517:4(1-26)Online publication date: 30-Sep-2020
https://dl.acm.org/doi/10.1145/3412375
Pei YBiswas SFussell DPingali KSarkar VKim H(2020)A Methodology for Principled Approximation in Visual SLAMProceedings of the ACM International Conference on Parallel Architectures and Compilation Techniques10.1145/3410463.3414636(373-386)Online publication date: 30-Sep-2020
https://dl.acm.org/doi/10.1145/3410463.3414636
Liu LIsaacman SKremer UDevanbu PCohen MZimmermann T(2020)Global cost/quality management across multiple applicationsProceedings of the 28th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering10.1145/3368089.3409721(350-361)Online publication date: 8-Nov-2020
https://dl.acm.org/doi/10.1145/3368089.3409721
Hu YLokhandwala MI TTseng H(2020)Varifocal Storage: Dynamic Multiresolution Data StorageIEEE Micro10.1109/MM.2020.298595540:3(47-55)Online publication date: 1-May-2020
https://doi.org/10.1109/MM.2020.2985955
Moazzemi KMaity BYi SRahmani ADutt N(2019)HESSLE-FREEACM Transactions on Embedded Computing Systems10.1145/335820318:5s(1-19)Online publication date: 8-Oct-2019
https://dl.acm.org/doi/10.1145/3358203
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

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

Media

Figures

Other

Tables

View Table of Contents