More Web Proxy on the site http://driver.im/

research-article

Patterns and statistical analysis for understanding reduced resource computing

Authors:

Henry Hoffmann,

Sasa Misailovic,

Stelios SidiroglouAuthors Info & Claims

OOPSLA '10: Proceedings of the ACM international conference on Object oriented programming systems languages and applications

Pages 806 - 821

https://doi.org/10.1145/1869459.1869525

Published: 17 October 2010 Publication History

Abstract

We present several general, broadly applicable mechanisms that enable computations to execute with reduced resources, typically at the cost of some loss in the accuracy of the result they produce.We identify several general computational patterns that interact well with these resource reduction mechanisms, present a concrete manifestation of these patterns in the form of simple model programs, perform simulationbased explorations of the quantitative consequences of applying these mechanisms to our model programs, and relate the model computations (and their interaction with the resource reduction mechanisms) to more complex benchmark applications drawn from a variety of fields.

References

[1]

}}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 '09.

Digital Library

[2]

}}W. Baek and T. Chilimbi. Green: A system for supporting energy-conscious programming using principled approximation. Technical Report TR-2009-089, Microsoft Research, Aug. 2009.

[3]

}}J. Berg, J. Tymoczko, and L. Stryer. Biochemistry. W.H. Freeman, 2006.

[4]

}}E. Berger and B. Zorn. DieHard: probabilistic memory safety for unsafe languages. In PLDI, June 2006.

Digital Library

[5]

}}C. Bienia, S. Kumar, J. P. Singh, and K. Li. The PARSEC benchmark suite: Characterization and architectural implications. In PACT '08.

Digital Library

[6]

}}E. Brewer. Towards robust distributed systems. Keynote, ACM Symposium on Principles of Distributed Systems (PODC), 2000.

Digital Library

[7]

}}R. Browning, T. Li, B. Chui, J. Ye, R. Pease, Z. Czyzewski, and D. Joy. Low-energy electron/atom elastic scattering cross sections from 0.1-30 keV. Scanning, 17(4), 1995.

[8]

}}B. Demsky, M. Ernst, P. Guo, S. McCamant, J. Perkins, and M. Rinard. Inference and enforcement of data structure consistency specifications. In ISSTA '06.

Digital Library

[9]

}}B. Demsky and M. Rinard. Automatic detection and repair of errors in data structures. In OOPSLA '03, 2003.

Digital Library

[10]

}}B. Demsky and M. Rinard. Data structure repair using goal-directed reasoning. In ICSE '05, 2005.

Digital Library

[11]

}}R. Floyd. Assigning meanings to programs. In Proceedings of the Symposium in Applied Mathematics, number 19, 1967.

[12]

}}E. Gamma, R. Helm, R. Johnson, and J. Vlissides. Design Patterns: Elements of Reusable Object-Oriented Software. Addison-Wesley, 1995.

Digital Library

[13]

}}J. Harris, S. Lazaratos, and R. Michelena. Tomographic string inversion. In Proceedings of the 60th Annual International Meeting, Society of Exploration and Geophysics, Extended Abstracts, 1990.

[14]

}}C. A. R. Hoare. An axiomatic basis for computer programming. Commun. ACM, 12(10), 1969.

Digital Library

[15]

}}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, MIT, Sept. 2009.

[16]

}}D. Le Gall. MPEG: A video compression standard for multimedia applications. CACM, Apr. 1991.

Digital Library

[17]

}}S. Misailovic, D. Kim, and M. Rinard. Parallelizing sequential programs with statistical accuracy tests. Technical Report TR-2010-038, Computer Science and Artificial Intelligence Laboratory, MIT, 2010.

[18]

}}S. Misailovic, S. Sidiroglou, H. Hoffman, and M. Rinard. Quality of service profiling. In ISCE '10.

Digital Library

[19]

}}H. Nguyen and M. Rinard. Detecting and eliminating memory leaks using cyclic memory allocation. In ISMM '07.

Digital Library

[20]

}}J. Perkins, S. Kim, S. Larsen, S. Amarasinghe, J. Bachrach, M. Carbin, C. Pacheco, F. Sherwood, S. Sidiroglou, G. Sullivan, W. Wong, Y. Zibin, M. Ernst, and M. Rinard. Automatically patching errors in deployed software. In SOSP '09.

Digital Library

[21]

}}M. Rinard. Probabilistic accuracy bounds for fault-tolerant computations that discard tasks. In ICS '06.

Digital Library

[22]

}}M. Rinard. Using early phase termination to eliminate load imbalancess at barrier synchronization points. In OOPSLA '07.

Digital Library

[23]

}}M. Rinard. The Design, Implementation and Evaluation of Jade, a Portable, Implicitly Parallel Programming Language. PhD thesis, Stanford University, Department of Computer Science, 1994.

Digital Library

[24]

}}M. Rinard. Acceptability-oriented computing. In OOPSLA '03 Companion, Oct. 2003.

Digital Library

[25]

}}M. Rinard, C. Cadar, D. Dumitran, D. M. Roy, T. Leu, and J. William S. Beebee. Enhancing Server Availability and Security Through Failure-Oblivious Computing. In OSDI '04.

Digital Library

[26]

}}M. Rinard, D. Scales, and M. Lam. Jade: A high-level, machine-independent language for parallel programming. parallel computing, 29, 1993.

[27]

}}M. C. Rinard, C. Cadar, D. Dumitran, D. M. Roy, and T. Leu. A dynamic technique for eliminating buffer overflow vulnerabilities (and other memory errors). In ACSAC 04.

Digital Library

[28]

}}M. C. Rinard, C. Cadar, and H. H. Nguyen. Exploring the acceptability envelope. In OOPSLA '05 Companion.

Digital Library

[29]

}}K. Schmidt-Nielsen, R. Schroter, and A. Shkolnik. Desaturation of exhaled air in camels. Proceedings of the Royal Society of London, Series B, Biological Sciences, 211(1184), 1981.

[30]

}}S. Sidiroglou, O. Laadan, C. Perez, N. Viennot, J. Nieh, and A. D. Keromytis. Assure: automatic software self-healing using rescue points. In ASPLOS '09.

Digital Library

[31]

}}S. Sidiroglou, M. E. Locasto, S. W. Boyd, and A. D. Keromytis. Building a reactive immune system for software services. In USENIX '05.

Digital Library

Cited By

Rahimipour SFlayyih WKamsani NHashim SStan MRokhani F(2020)Low-Power, Highly Reliable Dynamic Thermal Management by Exploiting Approximate ComputingIEEE Transactions on Very Large Scale Integration (VLSI) Systems10.1109/TVLSI.2020.301262628:10(2210-2222)Online publication date: Oct-2020
https://doi.org/10.1109/TVLSI.2020.3012626
Guo LLi D(2019)MOARD: Modeling Application Resilience to Transient Faults on Data Objects2019 IEEE International Parallel and Distributed Processing Symposium (IPDPS)10.1109/IPDPS.2019.00096(878-889)Online publication date: May-2019
https://doi.org/10.1109/IPDPS.2019.00096
Stanley-Marbell PRinard M(2017)Error-Efficient Computing SystemsFoundations and Trends in Electronic Design Automation10.1561/100000004911:4(362-461)Online publication date: 18-Dec-2017
https://dl.acm.org/doi/10.1561/1000000049
Show More Cited By

Index Terms

Patterns and statistical analysis for understanding reduced resource computing
1. Software and its engineering
  1. Software notations and tools
    1. Formal language definitions
      1. Semantics
    2. General programming languages
      1. Language features
        Patterns
  2. Software organization and properties
    1. Software system structures
      1. Distributed systems organizing principles
        Client-server architectures
      2. Software architectures
2. Theory of computation
  1. Semantics and reasoning
    1. Program reasoning
      1. Program verification
    2. Program semantics

Recommendations

Patterns and statistical analysis for understanding reduced resource computing
OOPSLA '10

We present several general, broadly applicable mechanisms that enable computations to execute with reduced resources, typically at the cost of some loss in the accuracy of the result they produce.We identify several general computational patterns that ...
Understanding and Supporting Debugging Workflows in Multiverse Analysis
CHI '23: Proceedings of the 2023 CHI Conference on Human Factors in Computing Systems

Multiverse analysis—a paradigm for statistical analysis that considers all combinations of reasonable analysis choices in parallel—promises to improve transparency and reproducibility. Although recent tools help analysts specify multiverse analyses, ...
Milliways: Taming Multiverses through Principled Evaluation of Data Analysis Paths
CHI '24: Proceedings of the 2024 CHI Conference on Human Factors in Computing Systems

Multiverse analyses involve conducting all combinations of reasonable choices in a data analysis process. A reader of a study containing a multiverse analysis might question—are all the choices included in the multiverse reasonable and equally ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

OOPSLA '10: Proceedings of the ACM international conference on Object oriented programming systems languages and applications

October 2010

984 pages

ISBN:9781450302036

DOI:10.1145/1869459

General Chairs:
William R. Cook
University of Texas at Austin
,
Siobhán Clarke
Trinity College Dublin
,
Program Chairs:
Martin Rinard
MIT
,
Kevin J. Sullivan
University of Virginia
,
Daniel H. Steinberg
Dim Sum Thinking Inc.

ACM SIGPLAN Notices Volume 45, Issue 10
OOPSLA '10
October 2010
957 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/1932682
Issue’s Table of Contents

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

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 17 October 2010

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SPLASH '10

Sponsor:

SIGPLAN

SPLASH '10: Systems Programming Languages and Applications: Software for Humanity

October 17 - 21, 2010

Nevada, Reno/Tahoe, USA

Acceptance Rates

Overall Acceptance Rate 268 of 1,244 submissions, 22%

Upcoming Conference

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

32
Total Citations
View Citations
369
Total Downloads

Downloads (Last 12 months)5
Downloads (Last 6 weeks)1

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Rahimipour SFlayyih WKamsani NHashim SStan MRokhani F(2020)Low-Power, Highly Reliable Dynamic Thermal Management by Exploiting Approximate ComputingIEEE Transactions on Very Large Scale Integration (VLSI) Systems10.1109/TVLSI.2020.301262628:10(2210-2222)Online publication date: Oct-2020
https://doi.org/10.1109/TVLSI.2020.3012626
Guo LLi D(2019)MOARD: Modeling Application Resilience to Transient Faults on Data Objects2019 IEEE International Parallel and Distributed Processing Symposium (IPDPS)10.1109/IPDPS.2019.00096(878-889)Online publication date: May-2019
https://doi.org/10.1109/IPDPS.2019.00096
Stanley-Marbell PRinard M(2017)Error-Efficient Computing SystemsFoundations and Trends in Electronic Design Automation10.1561/100000004911:4(362-461)Online publication date: 18-Dec-2017
https://dl.acm.org/doi/10.1561/1000000049
Ceze LSampson A(2017)APPROXIMATE COMPUTINGGetMobile: Mobile Computing and Communications10.1145/3036699.303670320:3(12-16)Online publication date: 5-Jan-2017
https://dl.acm.org/doi/10.1145/3036699.3036703
Park YKhajeh AShin JKurdahi FEltawil ADutt N(2017)Microarchitecture-Level SoC DesignHandbook of Hardware/Software Codesign10.1007/978-94-017-7358-4_28-2(1-46)Online publication date: 11-Apr-2017
https://doi.org/10.1007/978-94-017-7358-4_28-2
Park YKhajeh AShin JKurdahi FEltawil ADutt N(2017)Microarchitecture-Level SoC DesignHandbook of Hardware/Software Codesign10.1007/978-94-017-7267-9_28(867-913)Online publication date: 27-Sep-2017
https://doi.org/10.1007/978-94-017-7267-9_28
Laurenzano MHill PSamadi MMahlke SMars JTang L(2016)Input responsiveness: using canary inputs to dynamically steer approximationACM SIGPLAN Notices10.1145/2980983.290808751:6(161-176)Online publication date: 2-Jun-2016
https://dl.acm.org/doi/10.1145/2980983.2908087
Park JAmaro EMahajan DThwaites BEsmaeilzadeh H(2016)AxGamesACM SIGARCH Computer Architecture News10.1145/2980024.287237644:2(623-636)Online publication date: 25-Mar-2016
https://dl.acm.org/doi/10.1145/2980024.2872376
Park JAmaro EMahajan DThwaites BEsmaeilzadeh H(2016)AxGamesACM SIGOPS Operating Systems Review10.1145/2954680.287237650:2(623-636)Online publication date: 25-Mar-2016
https://doi.org/10.1145/2954680.2872376
Park JAmaro EMahajan DThwaites BEsmaeilzadeh H(2016)AxGamesACM SIGPLAN Notices10.1145/2954679.287237651:4(623-636)Online publication date: 25-Mar-2016
https://dl.acm.org/doi/10.1145/2954679.2872376
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.

Media

Figures

Other

Tables

View Table of Contents