Exploiting Errors for Efficiency: A Survey from Circuits to Applications

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; Damien Zufferey

doi:10.1145/3394898

Journal article

Exploiting Errors for Efficiency: A Survey from Circuits to Applications

Phillip Stanley-Marbell, Armin Alaghi, Michael Carbin, Eva Darulova, Lara Dolecek, Andreas Gerstlauer, Ghayoor Gillani, Djordje Jevdjic, Thierry Moreau, Mattia Cacciotti, …

ACM Computing Surveys

2020

DOI: https://doi.org/10.1145/3394898

Abstract

Commerce

Computation theory

Computer aided design

Computer architecture

Computer circuits

Computer programming languages

Computer systems programming

Errors

Information theory

Program compilers

Surveys

Timing circuits

Computational task

Digital system design

End-to-end application

Information-theoretic limits

Over provisioning

Potential benefits

Research communities

Research results

Computer operating systems

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. © 2020 ACM.

Files and links (1)

url

https://doi.org/10.1145/3394898View

Published (Version of record) Open

Metrics

1 Record Views

Details

Title: Exploiting Errors for Efficiency: A Survey from Circuits to Applications
Creators - without role: Phillip Stanley-Marbell - University of Cambridge
Armin Alaghi - University of Washington
Michael Carbin - Massachusetts Institute of Technology
Eva Darulova - Max Planck Institute for Software Systems
Lara Dolecek - University of California, Los Angeles
Andreas Gerstlauer - The University of Texas at Austin
Ghayoor Gillani - University of Twente
Djordje Jevdjic - National University of Singapore
Thierry Moreau - University of Washington
Mattia Cacciotti - École Polytechnique Fédérale de Lausanne
Alexandros Daglis - Georgia Institute of Technology
Natalie Enright Jerger - University of Toronto
Babak Falsafi - École Polytechnique Fédérale de Lausanne
Sasa Misailovic - University of Illinois Urbana-Champaign
Adrian Sampson - Cornell University
Damien Zufferey - Max Planck Institute for Software Systems
Publication Details: ACM Computing Surveys
Publisher: Association for Computing Machinery
Grant note: The workshop was funded by the Swiss National Science Foundation (SNF) under Grant No. IZ32Z0_173393/1: “International Exploratory Workshop on Theory and Practice for Error-Efficient Computing,” and by the EPFL EcoCloud Research Center. Phillip Stanley-Marbell is supported by an Alan Turing Institute Award No. TU/B/000096 under EPSRC Grant No. EP/N510129/1, by Royal Society Grant No. RG170136, and by EPSRC Grants No. EP/P001246/1 and No. EP/R022534/1 Authors’ addresses: P. S.-Marbell, 9 JJ Thomson Avenue, Cambridge CB3 0FA, UK; email: phillip.stanley-marbell@eng.cam.ac.uk; A. Alaghi, Paul G. Allen Center, 185 E Stevens Way NE Seattle, WA 98195, USA; email: armin@cs.washington.edu; M. Carbin, Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 77 Massachusetts Avenue, Cambridge, MA 02139, USA; email: mcarbin@csail.mit.edu; E. Darulova, Max Planck Institute for Software Systems, Paul-Ehrlich-Strasse 26, 67663 Kaiserslautern, Germany; email: eva@mpi-sws.org; L. Dolecek, Eng IV-147B, University of California, Los Angeles, Los Angeles, CA, 90095, USA; email: dole-cek@ee.ucla.edu; A. Gerstlauer, The University of Texas at Austin, Department of Electrical and Computer Engineering, 2501 Speedway, Austin, TX 78712, USA; email: gerstl@ece.utexas.edu; G. Gillani, Faculty of EEMCS, University of Twente, 7500 AE Enschede, The Netherlands; email: s.ghayoor.gillani@utwente; D. Jevdjic, National University of Singapore, 13 Computing Drive, COM2-03-34, Singapore 117417; email: jevdjic@comp.nus.edu.sg; T. Moreau, Paul G. Allen Center, 185 E Stevens Way NE Seattle, WA 98195, USA; email: moreau@cs.washington.edu; M. Cacciotti, EPFL Microcity, Rue de la Mal-adière 71b, CH-2002, Neuchâtel, Switzerland; email: mattia.cacciotti@epfl.ch; A. Daglis, Georgia Institute of Technology, School of Computer Science, 266 Ferst Dr NW, Atlanta, GA 30332, USA; email: alexandros.daglis@cc.gatech.edu; N. Enright Jerger, University of Toronto, 10 King’s College Rd, Toronto ON, Canada M5S 3G4; email: enright@ece.utoronto.ca; B. Falsafi, EPFL, IC IINFCOM PARSA, INJ 233, Station 14, CH-1015 Lausanne, Switzerland; email: babak.falsafi@epfl.ch; S. Misailovic, University of Illinois at Urbana-Champaign, Department of Computer Science, 201 N Goodwin Ave, Urbana, IL 61801; email: misailo@illinois.edu; A. Sampson, 411A Gates Hall, Cornell University, Ithaca NY 14853-7501; email: asampson@cs.cornell.edu; D. Zufferey, Max Planck Institute for Software Systems, Paul-Ehrlich-Str. 26, 67663 Kaiser-slautern, Germany; email: zufferey@mpi-sws.org. 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 permissions@acm.org. © 2020 Association for Computing Machinery. 0360-0300/2020/05-ART51 $15.00 https://doi.org/10.1145/3394898
Identifiers: 9920206909548
Academic Unit: Alan Turing Institute
Language: English
Resource Type: Journal article
Date published: 2020

Exploiting Errors for Efficiency: A Survey from Circuits to Applications

Abstract

Files and links (1)

Metrics

Details

Alan Turing Institute Social media