Michael A. Laurenzano
Jason Mars
ABSTRACT
This paper introduces Input Responsive Approximation (IRA), an approach that uses a canary input — a small program input carefully constructed to capture the intrinsic properties of the original input — to automatically control how program approximation is applied on an input-by-input basis. Motivating this approach is the observation that many of the prior techniques focusing on choosing how to approximate arrive at conservative decisions by discounting substantial differences between inputs when applying approximation. The main challenges in overcoming this limitation lie in making the choice of how to approximate both effectively (e.g., the fastest approximation that meets a particular accuracy target) and rapidly for every input. With IRA, each time the approximate program is run, a canary input is constructed and used dynamically to quickly test a spectrum of approximation alternatives. Based on these runtime tests, the approximation that best fits the desired accuracy constraints is selected and applied to the full input to produce an approximate result. We use IRA to select and parameterize mixes of four approximation techniques from the literature for a range of 13 image processing, machine learning, and data mining applications. Our results demonstrate that IRA significantly outperforms prior approaches, delivering an average of 10.2× speedup over exact execution while minimizing accuracy losses in program outputs.
- S. Agarwal, B. Mozafari, A. Panda, H. Milner, S. Madden, and I. Stoica. BlinkDB: Queries with bounded errors and bounded response times on very large data. In European Conference on Computer Systems (EuroSys), 2013. Google Scholar
Digital Library
- R. S. Amant, A. Yazdanbakhsh, J. Park, B. Thwaites, H. Esmaeilzadeh, A. Hassibi, L. Ceze, and D. Burger. Generalpurpose code acceleration with limited-precision analog computation. In International Symposium on Computer Architecture (ISCA), 2014. Google ScholarDigital Library
- J. Ansel, Y. L. Wong, C. Chan, M. Olszewski, A. Edelman, and S. Amarasinghe. Language and compiler support for autotuning variable-accuracy algorithms. Code Generation and Optimization (CGO), 2011. Google ScholarDigital Library
- Apple. Siri. https://www.apple.com/ios/siri/, 2016.Google Scholar
- {Online; accessed 10-April-2016}.Google Scholar
- K. Bache and M. Lichman. UCI machine learning repository. http://archive.ics.uci.edu/ml/, 2016. {Online; accessed 10-April-2016}.Google Scholar
- W. Baek and T. M. Chilimbi. Green: a framework for supporting energy-conscious programming using controlled approximation. In Programming Language Design and Implementation (PLDI), 2010. Google ScholarDigital Library
- K. Barker, T. Benson, D. Campbell, D. Ediger, R. Gioiosa, A. Hoisie, D. Kerbyson, J. Manzano, A. Marquez, L. Song, N. Tallent, and A. Tumeo. PERFECT (Power Efficiency Revolution For Embedded Computing Technologies) Benchmark Suite Manual. Pacific Northwest National Laboratory and Georgia Tech Research Institute, 2013.Google Scholar
- E. D. Berger and B. G. Zorn. Diehard: probabilistic memory safety for unsafe languages. In Programming Language Design and Implementation (PLDI), 2006. Google ScholarDigital Library
- J. Bornholt, T. Mytkowicz, and K. S. McKinley. Uncertain<T>: A first-order type for uncertain data. In Architectural Support for Programming Languages and Operating Systems (ASPLOS), 2014. Google ScholarDigital Library
- S. Byna, J. Meng, A. Raghunathan, S. Chakradhar, and S. Cadambi. Best-effort semantic document search on GPUs. In Workshop on General-Purpose Computation on Graphics Processing Units (GPGPU), 2010. Google ScholarDigital Library
- M. Carbin, D. Kim, S. Misailovic, and M. C. Rinard. Proving acceptability properties of relaxed nondeterministic approximate programs. In Programming Language Design and Implementation (PLDI), 2012. Google ScholarDigital Library
- M. Carbin, S. Misailovic, and M. C. Rinard. Verifying quantitative reliability for programs that execute on unreliable hardware. In Object Oriented Programming Systems Languages and Applications (OOPSLA), 2013. Google ScholarDigital Library
- S. Chaudhuri, S. Gulwani, R. Lublinerman, and S. Navidpour. Proving programs robust. In Foundations of Software Engineering (FSE), 2011. Google ScholarDigital Library
- J. Cohen. Statistical power analysis for the behavioral sciences. Lawrence Erlbaum, 1988.Google Scholar
- Y. Ding, J. Ansel, K. Veeramachaneni, X. Shen, U.-M. O’Reilly, and S. Amarasinghe. Autotuning algorithmic choice for input sensitivity. In Programming Language Design and Implementation (PLDI), 2015. Google ScholarDigital Library
- O. J. Dunn. Multiple comparisons among means. Journal of the American Statistical Association, 1961.Google ScholarCross Ref
- H. Esmaeilzadeh, A. Sampson, L. Ceze, and D. Burger. Architecture support for disciplined approximate programming. In Architectural Support for Programming Languages and Operating Systems (ASPLOS), 2012. Google ScholarDigital Library
- H. Esmaeilzadeh, A. Sampson, L. Ceze, and D. Burger. Neural acceleration for general-purpose approximate programs. In International Symposium on Microarchitecture (MICRO), 2012. Google ScholarDigital Library
- I. Goiri, R. Bianchini, S. NagaraKatte, and T. Nguyen. Approxhadoop: Bringing approximations to mapreduce frameworks. In Architectural Support for Programming Languages and Operating Systems (ASPLOS), 2015. Google ScholarDigital Library
- Google. Glass. https://www.google.com/glass/ start/, 2016. {Online; accessed 10-April-2016}.Google Scholar
- Google. Google Now. http://www.google.com/ landing/now/, 2016. {Online; accessed 10-April-2016}.Google Scholar
- B. Grigorian and G. Reinman. Dynamically adaptive and reliable approximate computing using light-weight error analysis. In NASA/ESA Conference on Adaptive Hardware and Systems (AHS), 2014.Google ScholarCross Ref
- B. Grigorian, N. Farahpour, and G. Reinman. Brainiac: Bringing reliable accuracy into neurally-implemented approximate computing. In High Performance Computer Architecture (HPCA), 2015.Google ScholarCross Ref
- J. R. Hauser. Handling floating-point exceptions in numeric programs. Transactions on Programming Languages and Systems (TOPLAS), 1996. Google ScholarDigital Library
- F. B. Hildebrand. Introduction to numerical analysis. Courier Corporation, 1987. Google ScholarDigital Library
- H. Hoffmann, J. Eastep, M. Santambrogio, J. Miller, and A. Agarwal. Application heartbeats for software performance and health. MIT CSAIL Technical Report, 2009.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. MIT CSAIL Technical Report, 2009.Google Scholar
- H. Hoffmann, S. Sidiroglou, M. Carbin, S. Misailovic, A. Agarwal, and M. Rinard. Dynamic knobs for responsive power-aware computing. In Architectural Support for Programming Languages and Operating Systems (ASPLOS), 2011. Google ScholarDigital Library
- S. Holm. A simple sequentially rejective multiple test procedure. Scandinavian Journal of Statistics, 1979.Google Scholar
- D. S. Khudia, B. Zamirai, M. Samadi, and S. Mahlke. Rumba: an online quality management system for approximate computing. In International Symposium on Computer Architecture (ISCA), 2015. Google ScholarDigital Library
- L. Leem, H. Cho, J. Bau, Q. A. Jacobson, and S. Mitra. ERSA: Error resilient system architecture for probabilistic applications. In Design, Automation and Test in Europe (DATE), 2010. Google ScholarDigital Library
- M.-L. Li, P. Ramachandran, S. K. Sahoo, S. V. Adve, V. S. Adve, and Y. Zhou. SWAT: an error resilient system. In Workshop on Silicon Errors in Logic-System Effects (SELSE), 2008.Google Scholar
- S. Liu, K. Pattabiraman, T. Moscibroda, and B. G. Zorn. Flikker: Saving DRAM refresh-power through data partitioning. In Architectural Support for Programming Languages and Operating Systems (ASPLOS), 2011. Google ScholarDigital Library
- J. Meng, S. Chakradhar, and A. Raghunathan. Best-effort parallel execution framework for recognition and mining applications. In International Symposium on Parallel and Distributed Processing (IPDPS), 2009. Google ScholarDigital Library
- Meta. https://www.metavision.com/, 2016.Google Scholar
- {Online; accessed 10-April-2016}.Google Scholar
- Microsoft. Cortana. https://www.microsoft.com/ en-us/mobile/experiences/cortana/, 2016.Google Scholar
- {Online; accessed 10-April-2016}.Google Scholar
- R. G. Miller. Simultaneous Statistical Inference. Springer, 1981.Google ScholarCross Ref
- S. Misailovic, S. Sidiroglou, H. Hoffmann, and M. Rinard. Quality of service profiling. In International Conference on Software Engineering (ICSE), 2010. Google ScholarDigital Library
- S. Misailovic, D. M. Roy, and M. C. Rinard. Probabilistically accurate program transformations. In Static Analysis Symposium (SAS). 2011. Google ScholarDigital Library
- S. Misailovic, D. Kim, and M. Rinard. Parallelizing sequential programs with statistical accuracy tests. Transactions on Embedded Computing Systems (TECS), 2013. Google ScholarDigital Library
- T. Moreau, M. Wyse, J. Nelson, A. Sampson, H. Esmaeilzadeh, L. Ceze, and M. Oskin. Snnap: Approximate computing on programmable socs via neural acceleration. In High Performance Computer Architecture (HPCA), 2015.Google ScholarCross Ref
- C. Poynton. Digital video and HD: Algorithms and Interfaces. Elsevier, 2012. Google ScholarDigital Library
- L. Renganarayana, V. Srinivasan, R. Nair, and D. Prener. Programming with relaxed synchronization. In Workshop on Relaxing Synchronization for Multicore and Manycore Scalability (RACES), 2012. Google ScholarDigital Library
- M. Rinard. Probabilistic accuracy bounds for fault-tolerant computations that discard tasks. In International Conference on Supercomputing (ICS), 2006. Google ScholarDigital Library
- M. Rinard. Probabilistic accuracy bounds for perforated programs. In Workshop on Partial Evaluation and Program Manipulation (PEPM), 2011. Google ScholarDigital Library
- M. Rinard, H. Hoffmann, S. Misailovic, and S. Sidiroglou. Patterns and statistical analysis for understanding reduced resource computing. In Object Oriented Programming Systems Languages and Applications (OOPSLA), 2010. Google ScholarDigital Library
- M. Ringenburg, A. Sampson, I. Ackerman, L. Ceze, and D. Grossman. Monitoring and debugging the quality of results in approximate programs. In Architectural Support for Programming Languages and Operating Systems (ASPLOS), 2015. Google ScholarDigital Library
- S. Russell and P. Norvig. Artificial intelligence: A modern approach. Prentice Hall Press, 1995. Google ScholarDigital Library
- M. Samadi, J. Lee, D. A. Jamshidi, A. Hormati, and S. Mahlke. SAGE: Self-tuning approximation for graphics engines. In International Symposium on Microarchitecture (MICRO), 2013. Google ScholarDigital Library
- M. Samadi, D. A. Jamshidi, J. Lee, and S. Mahlke. Paraprox: Pattern-based approximation for data parallel applications. In Architectural Support for Programming Languages and Operating Systems (ASPLOS), 2014. Google ScholarDigital Library
- 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 Programming Language Design and Implementation (PLDI), 2011. Google ScholarDigital Library
- A. Sampson, J. Nelson, K. Strauss, and L. Ceze. Approximate storage in solid-state memories. In International Symposium on Microarchitecture (MICRO), 2013. Google ScholarDigital Library
- A. Sampson, P. Panchekha, T. Mytkowicz, K. S. McKinley, D. Grossman, and L. Ceze. Expressing and verifying probabilistic assertions. In Programming Language Design and Implementation (PLDI), 2014. Google ScholarDigital Library
- J. Sartori and R. Kumar. Branch and data herding: Reducing control and memory divergence for error-tolerant GPU applications. In IEEE Transactions on Multimedia. 2013. Google ScholarDigital Library
- S. Sidiroglou, O. Laadan, C. Perez, N. Viennot, J. Nieh, and A. D. Keromytis. Assure: automatic software self-healing using rescue points. Architectural Support for Programming Languages and Operating Systems (ASPLOS), 2009. Google ScholarDigital Library
- S. Sidiroglou, S. Misailovic, H. Hoffmann, and M. Rinard. Managing performance vs. accuracy trade-offs with loop perforation. In Foundations of Software Engineering (FSE), 2011. Google ScholarDigital Library
- J. Sloan, D. Kesler, R. Kumar, and A. Rahimi. A numerical optimization-based methodology for application robustification: Transforming applications for error tolerance. In Dependable Systems and Networks (DSN), 2010.Google ScholarCross Ref
- 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 Conference on Embedded Networked Sensor Systems (Sensys), 2007. Google ScholarDigital Library
- D. Ungar, D. Kimelman, and S. Adams. Inconsistency robustness for scalability in interactive concurrent-update inmemory molap cubes. Inconsistency Robustness (IR), 2011.Google Scholar
- J. S. Witte, R. C. Elston, and L. R. Cardon. On the relative sample size required for multiple comparisons. Statistics in medicine, 2000.Google Scholar
- T. Y. Yeh, P. Faloutsos, M. Ercegovac, S. J. Patel, and G. Reinman. The art of deception: Adaptive precision reduction for area efficient physics acceleration. In International Symposium on Microarchitecture (MICRO), 2007. Google ScholarDigital Library
- Z. A. Zhu, S. Misailovic, J. A. Kelner, and M. Rinard. Randomized accuracy-aware program transformations for efficient approximate computations. In Principles of Programming Languages (POPL), 2012. Google ScholarDigital Library
Index Terms
- Input responsiveness: using canary inputs to dynamically steer approximation
Recommendations
ApproxTuner: a compiler and runtime system for adaptive approximations
PPoPP '21: Proceedings of the 26th ACM SIGPLAN Symposium on Principles and Practice of Parallel ProgrammingManually optimizing the tradeoffs between accuracy, performance and energy for resource-intensive applications with flexible accuracy or precision requirements is extremely difficult. We present ApproxTuner, an automatic framework for accuracy-aware ...
Input responsiveness: using canary inputs to dynamically steer approximation
PLDI '16This paper introduces Input Responsive Approximation (IRA), an approach that uses a canary input — a small program input carefully constructed to capture the intrinsic properties of the original input — to automatically control how program ...
Multiple Discrete Logarithm Problems with Auxiliary Inputs
Proceedings, Part I, of the 21st International Conference on Advances in Cryptology -- ASIACRYPT 2015 - Volume 9452Let g be an element of prime order p in an abelian group and let $$\alpha _1, \dots , \alpha _L \in {\mathbb Z}_p$$ for a positive integer L. First, we show that, if $$g, g^{\alpha _i}$$, and $$g^{\alpha _i^d}$$$$i=1, \dots , L$$ are given for $$d \mid ...
Comments