skip to main content
10.1145/2228360.2228523acmconferencesArticle/Chapter ViewAbstractPublication PagesdacConference Proceedingsconference-collections
research-article

Incorrect systems: it's not the problem, it's the solution

Published: 03 June 2012 Publication History

Abstract

We present an overview of state-of-the-art work in the engineering of digital systems (hardware and software) where traditional correctness requirements are relaxed, usually for higher performance and lower resource consumption but possibly also for other non-functional properties such as more robustness and less cost. The work presented here is categorized into work that involves just hardware, hardware and software, and just software. In particular, we discuss work on probabilistic and approximate design of processors, unreliable cores in asymmetric multi-core architectures, best-effort computing, stochastic processors, accuracy-aware program transformations, and relaxed concurrent data structures. As common theme we identify, at least intuitively, "metrics of correctness" in each piece of work which appear to be important for understanding the effects of relaxed correctness requirements and their relationship to performance improvements and resource consumption.

References

[1]
Designing chips without guarantees. IEEE Design and Test of Computers, 27:60--67, 2010.
[2]
Y. Afek, G. Korland, and E. Yanovsky. Quasi-linearizability: Relaxed consistency for improved concurrency. In Proc. Conference on Principles of Distributed Systems (OPODIS), pages 395--410. Springer, 2010.
[3]
S. Chakradhar and A. Raghunathan. Best-effort computing: re-thinking parallel software and hardware. In Proc. Design Automation Conference (DAC), pages 865--870. ACM, 2010.
[4]
L. Chakrapani, P. Korkmaz, B. Akgul, and K. Palem. Probabilistic system-on-a-chip architectures. Transactions on Design Automation of Electronic Systems (TODAES), 12(3):29:1--29:28, May 2008.
[5]
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 Proc. Conference on Compilers, Architectures and Synthesis for Embedded Systems (CASES), pages 187--196. ACM, 2008.
[6]
T. A. Henzinger. The theory of hybrid automata. In Proc. Symposium on Logic in Computer Science (LICS), pages 278--292. IEEE, 1996.
[7]
D. H. I. Incze, N. Shavit, and M. Tzafrir. Flat combining and the synchronization-parallelism tradeoff. In Proc. Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 355--364. ACM, 2010.
[8]
C. Kirsch, H. Payer, H. Röck, and A. Sokolova. Brief announcement: Scalability versus semantics of concurrent FIFO queues. In Proc. Symposium on Principles of Distributed Computing (PODC), pages 331--332. ACM, 2011.
[9]
C. Kirsch, H. Payer, H. Röck, and A. Sokolova. Performance, scalability, and semantics of concurrent FIFO queues. Technical Report 2011--03, Department of Computer Sciences, University of Salzburg, September 2011.
[10]
L. Leem, C. Hyungmin, J. Bau, Q. Jacobson, and S. Mitra. Ersa: Error resilient system architecture for probabilistic applications. In Proc. Design, Automation Test in Europe Conference Exhibition (DATE), pages 1560--1565, 2010.
[11]
A. Lingamneni, K. Muntimadugu, C. Enz, R. Karp, K. Palem, and C. Piguet. Algorithmic methodologies for ultra-efficient inexact architectures for sustaining technology scaling. In Proc. Computing Frontiers (CF). ACM, 2012.
[12]
A. Lingamneni and K. Palem. What to do about the end of Moore's law, probably! In Proc. Design Automation Conference (DAC). ACM, 2012.
[13]
M. Michael and M. Scott. Simple, fast, and practical non-blocking and blocking concurrent queue algorithms. In Proc. Symposium on Principles of Distributed Computing (PODC), pages 267--275. ACM, 1996.
[14]
M. Michael, M. Vechev, and V. Saraswat. Idempotent work stealing. In Proc. Symposium on Principles and Practice of Parallel Programming (PPoPP), pages 45--54. ACM, 2009.
[15]
S. Narayanan, J. Sartori, R. Kumar, and D. Jones. Scalable stochastic processors. In Proc. Conference on Design, Automation and Test in Europe (DATE), pages 335--338. European Design and Automation Association, 2010.
[16]
K. Palem, L. Chakrapani, Z. Kedem, A. Lingamneni, and K. Muntimadugu. Sustaining moore's law in embedded computing through probabilistic and approximate design: Retrospects and prospects. In Proc. Conference on Compilers, Architecture, and Synthesis for Embedded Systems (CASES), pages 1--10. ACM, 2009.
[17]
M. Rinard. A lossy, synchronization-free, race-full, but still acceptably accurate parallel space-subdivision tree construction algorithm. Technical Report 2012-03-005, MIT-CSAIL, February 2012.
[18]
M. Rinard. Obtaining and reasoning about good enough software. In Proc. Design Automation Conference (DAC). ACM, 2012.
[19]
J. Sartori, J. Sloan, and R. Kumar. Stochastic computing: embracing errors in architectureand design of processors and applications. In Proc. Conference on Compilers, Architectures and Synthesis for Embedded Systems (CASES), pages 135--144. ACM, 2011.
[20]
S. Sidiroglou-Douskos, S. Misailovic, H. Hoffmann, and M. Rinard. Managing performance vs. accuracy trade-offs with loop perforation. In Proc. Symposium and Conference on Foundations of Software Engineering (ESEC/FSE), pages 124--134. ACM, 2011.
[21]
J. Sloan, J. Sartori, and R. Kumar. On software design for stochastic processors. In Proc. Design Automation Conference (DAC). ACM, 2012.
[22]
Z. Zhu, S. Misailovic, J. Kelner, and M. Rinard. Randomized accuracy-aware program transformations for efficient approximate computations. In Proc. Symposium on Principles of Programming Languages (POPL), pages 441--454. ACM, 2012.

Cited By

View all
  • (2021)Combination of Task Allocation and Approximate Computing for Fog-Architecture-Based IoTIEEE Internet of Things Journal10.1109/JIOT.2020.30408928:9(7638-7648)Online publication date: 1-May-2021
  • (2020)TAAC: Task Allocation Meets Approximate Computing for Internet of Things2020 IEEE International Symposium on Circuits and Systems (ISCAS)10.1109/ISCAS45731.2020.9180895(1-5)Online publication date: Oct-2020
  • (2018)Genetic Improvement of Software: A Comprehensive SurveyIEEE Transactions on Evolutionary Computation10.1109/TEVC.2017.269321922:3(415-432)Online publication date: Jun-2018
  • Show More Cited By

Index Terms

  1. Incorrect systems: it's not the problem, it's the solution

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    DAC '12: Proceedings of the 49th Annual Design Automation Conference
    June 2012
    1357 pages
    ISBN:9781450311991
    DOI:10.1145/2228360
    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

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 03 June 2012

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. performance
    2. power consumption
    3. probabilistic computing
    4. relaxed correctness
    5. robustness
    6. scalability

    Qualifiers

    • Research-article

    Funding Sources

    Conference

    DAC '12
    Sponsor:
    DAC '12: The 49th Annual Design Automation Conference 2012
    June 3 - 7, 2012
    California, San Francisco

    Acceptance Rates

    Overall Acceptance Rate 1,770 of 5,499 submissions, 32%

    Upcoming Conference

    DAC '25
    62nd ACM/IEEE Design Automation Conference
    June 22 - 26, 2025
    San Francisco , CA , USA

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)10
    • Downloads (Last 6 weeks)6
    Reflects downloads up to 20 Feb 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2021)Combination of Task Allocation and Approximate Computing for Fog-Architecture-Based IoTIEEE Internet of Things Journal10.1109/JIOT.2020.30408928:9(7638-7648)Online publication date: 1-May-2021
    • (2020)TAAC: Task Allocation Meets Approximate Computing for Internet of Things2020 IEEE International Symposium on Circuits and Systems (ISCAS)10.1109/ISCAS45731.2020.9180895(1-5)Online publication date: Oct-2020
    • (2018)Genetic Improvement of Software: A Comprehensive SurveyIEEE Transactions on Evolutionary Computation10.1109/TEVC.2017.269321922:3(415-432)Online publication date: Jun-2018
    • (2018)Design of Approximate Circuits by Fabrication of False Timing Paths: The Carry Cut-Back AdderIEEE Journal on Emerging and Selected Topics in Circuits and Systems10.1109/JETCAS.2018.28517498:4(746-757)Online publication date: Dec-2018
    • (2018)Use of Magnetoresistive Random-Access Memory as Approximate Memory for Training Neural Networks2018 25th IEEE International Conference on Electronics, Circuits and Systems (ICECS)10.1109/ICECS.2018.8617952(553-556)Online publication date: Dec-2018
    • (2016)A low-power carry cut-back approximate adder with fixed-point implementation and floating-point precisionProceedings of the 53rd Annual Design Automation Conference10.1145/2897937.2897964(1-6)Online publication date: 5-Jun-2016
    • (2016)Approximate 32-bit floating-point unit design with 53% power-area product reductionESSCIRC Conference 2016: 42nd European Solid-State Circuits Conference10.1109/ESSCIRC.2016.7598342(465-468)Online publication date: Sep-2016
    • (2016)SARP: Synopsis-Based Approximate Request Processing for Low Latency and Small Correctness Loss in Cloud Online ServicesInternational Journal of Parallel Programming10.1007/s10766-016-0406-944:5(1054-1077)Online publication date: 22-Mar-2016
    • (2016)Verifying a quantitative relaxation of linearizability via refinementInternational Journal on Software Tools for Technology Transfer (STTT)10.1007/s10009-015-0373-218:4(393-407)Online publication date: 1-Aug-2016
    • (2015)SARPProceedings of the 12th ACM International Conference on Computing Frontiers10.1145/2742854.2742858(1-8)Online publication date: 6-May-2015
    • Show More Cited By

    View Options

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Figures

    Tables

    Media

    Share

    Share

    Share this Publication link

    Share on social media