Exploiting Errors for Efficiency: A Survey from Circuits to Algorithms

Exploiting Errors for Efficiency: A Survey from Circuits to Applications: ACM Computing Surveys: Vol 53, No 3

ACM Digital Library homePhillip Stanley-Marbell University of Cambridge, Cambridge, UK

Exploiting Errors for Efficiency: A Survey from Circuits to Algorithms

When a computational task tolerates a relaxation of its specification or whenan algorithm tolerates the effects of noise in its execution, hardware,programming languages, and system software can trade deviations from correctbehavior for lower resource usage. We present, for the first time, a synt…

arXiv.orgPhillip Stanley-Marbell

Abstract

When a computational task tolerates a relaxation of its specification or when an algorithm tolerates the effects of noise in its execution, hardware, system software, and programming language compilers or their runtime systems can trade deviations from correct behavior for lower resource usage. We present, for the first time, a synthesis of research results on computing systems that only make as many errors as their end-to-end applications can tolerate. The results span the disciplines of computer-aided design of circuits, digital system design, computer architecture, programming languages, operating systems, and information theory. Rather than over-provisioning the resources controlled by each of these layers of abstraction to avoid errors, it can be more efficient to exploit the masking of errors occurring at one layer and thereby prevent those errors from propagating to a higher layer.
We demonstrate the potential benefits of end-to-end approaches using two illustrative examples. We introduce a formalization of terminology that allows us to present a coherent view across the techniques traditionally used by different research communities in their individual layer of focus. Using this formalization, we survey tradeoffs for individual layers of computing systems at the circuit, architecture, operating system, and programming language levels as well as fundamental information-theoretic limits to tradeoffs between resource usage and correctness.

Cite as:

Phillip Stanley-Marbell, Armin Alaghi, Michael Carbin, Eva Darulova, Lara Dolecek, Andreas Gerstlauer, Ghayoor Gillani, Djordje Jevdjic, Thierry Moreau, Mattia Cacciotti, Alexandros Daglis, Natalie Enright Jerger, Babak Falsafi, Sasa Misailovic, Adrian Sampson, and Damien Zufferey. 2020. Exploiting Errors for Efficiency: A Survey from Circuits to Applications. ACM Comput. Surv. 53, 3, Article 51 (June 2020), 39 pages. DOI:https://doi.org/10.1145/3394898

BibTeX:

@article{10.1145/3394898,
    author = {Stanley-Marbell, Phillip and Alaghi, Armin and Carbin, Michael and Darulova, Eva and Dolecek, Lara and Gerstlauer, Andreas and Gillani, Ghayoor and Jevdjic, Djordje and Moreau, Thierry and Cacciotti, Mattia and Daglis, Alexandros and Jerger, Natalie Enright and Falsafi, Babak and Misailovic, Sasa and Sampson, Adrian and Zufferey, Damien},
    title = {Exploiting Errors for Efficiency: A Survey from Circuits to Applications},
    year = {2020},
    issue_date = {June 2020},
    publisher = {Association for Computing Machinery},
    address = {New York, NY, USA},
    volume = {53},
    number = {3},
    issn = {0360-0300},
    url = {https://doi.org/10.1145/3394898},
    doi = {10.1145/3394898},
    journal = {ACM Comput. Surv.},
    month = jun,
    articleno = {51},
    numpages = {39},
    keywords = {Approximate computing, cross-layer optimization, error efficiency}
}