Xin Sui
Keshav Pingali
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.
- Cubist. https://www.rulequest.com/cubist-info.html.Google Scholar
- 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.Google ScholarDigital Library
- 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.Google Scholar
- 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.Google ScholarDigital Library
- Judit Bar-Ilan, Mazlita Mat-Hassan, and Mark Levene. Methods for comparing rankings of search engine results. Comput. Netw., 2006.Google ScholarDigital Library
- Christian Bienia. Benchmarking Modern Multiprocessors. PhD thesis, Princeton University, January 2011.Google ScholarDigital Library
- Léon Bottou. Large-scale machine learning with stochastic gradient descent. In Proceedings of the 19th International Conference on Computational Statistics (COMPSTAT'2010), 2010.Google ScholarCross Ref
- John Burkardt. 3d graphics models. http://people.sc.fsu.edu/jburkardt/data/ply/ply.html.Google Scholar
- 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.Google Scholar
- 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.Google ScholarDigital Library
- Swarat Chaudhuri, Sumit Gulwani, and Roberto Lublinerman. Continuity and robustness of programs. Commun. ACM, 55(8):107--115, August 2012.Google ScholarDigital Library
- 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.Google ScholarDigital Library
- Thomas Cormen, Charles Leiserson, Ronald Rivest, and Clifford Stein, editors. Introduction to Algorithms. MIT Press, 2001.Google ScholarDigital Library
- 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.Google ScholarDigital Library
- 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.Google ScholarDigital Library
- 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.Google ScholarDigital Library
- 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.Google ScholarDigital Library
- Davide Gadioli, Gianluca Palermo, and Cristina Silvano. Application autotuning to support runtime adaptivity in multicorearchitectures. In SAMOS XV, 2015.Google Scholar
- 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.Google ScholarDigital Library
- 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.Google ScholarDigital Library
- 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.Google ScholarDigital Library
- 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.Google ScholarDigital Library
- Søren Højsgaard. Graphical independence networks with the grain package for r. Journal of Statistical Software, 46, 2012.Google Scholar
- Benjamin Kuo. Automatic control systems. Prentice-Hall Publishers, 1991.Google Scholar
- Jure Leskovec. Stanford large network dataset collection(snap). http://snap.stanford.edu/data/.Google Scholar
- Chih-Jen Lin. Libsvm classification dataset. http://www.csie.ntu.edu.tw/cjlin/libsvmtools/datasets/.Google Scholar
- 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.Google Scholar
- Shawn Martin, W. Michael Brown, Richard Klavans, and Kevin W. Boyack. Openord: an open-source toolbox for large graph layout. volume 7868, 2011.Google Scholar
- 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.Google ScholarDigital Library
- 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.Google ScholarDigital Library
- R. E. Neapolitan. Learning Bayesian Networks. Prentice Hall, 2003.Google ScholarDigital Library
- 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.Google Scholar
- Krishna V. Palem. Energy aware computing through probabilistic switching: A study of limits. IEEE Trans. Comput., 2005.Google ScholarDigital Library
- J. R. Quinlan. Learning with continuous classes. In Proceedings of the Australian Joint Conference on Artificial Intelligence, pages 343--348. World Scientific, 1992.Google Scholar
- 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.Google ScholarDigital Library
- 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.Google ScholarDigital Library
- 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.Google ScholarDigital Library
- 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.Google ScholarDigital Library
- 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.Google ScholarDigital Library
- 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.Google ScholarDigital Library
- 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.Google Scholar
- 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.Google ScholarDigital Library
- 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.Google ScholarDigital Library
- M. Scutari. Learning Bayesian Networks with the bnlearn R Package. Journal of Statistical Software, 35, 2010.Google Scholar
- M. Shoushtari, A. BanaiyanMofrad, and N. Dutt. Exploiting partially-forgetful memories for approximate computing. Embedded Systems Letters, IEEE, March 2015.Google ScholarCross Ref
- 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.Google ScholarDigital Library
- Jean-Jacques Slotine and Weiping Li. Applied Nonlinear control. Prenctice-Hall Publishers, 1991.Google Scholar
- Soeren Sonnenburg, Vojtech Franc, Elad Yom-Tov, and Michele Sebag. Pascal large scale learning challenge. http://largescale.ml.tu-berlin.de.Google Scholar
- 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.Google Scholar
- TF3DM. 3d graphics models. http://tf3dm.com.Google Scholar
- L. G. Valiant. A theory of the learnable. CACM, 27(11), 1984.Google Scholar
- Joyce Jiyoung Whang, Xin Sui, and Inderjit S. Dhillon. Scalable and memory-efficient clustering of large-scale social networks. In ICDM, 2012.Google ScholarDigital Library
- R. Zafarani and H. Liu. Social computing data repository at ASU, 2009. http://socialcomputing.asu.edu.Google Scholar
- Andreas Zeller and Ralf Hildebrandt. Simplifying and isolating failure-inducing input. IEEE Trans. Softw. Eng., 28(2):183--200, February 2002.Google ScholarDigital Library
- 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.Google ScholarDigital Library
Index Terms
- Proactive Control of Approximate Programs
Recommendations
Proactive Control of Approximate Programs
ASPLOS '16Approximate 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'16Approximate 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