TY - JOUR
T1 - Exploiting Errors for Efficiency
T2 - A Survey from Circuits to Applications
AU - Stanley-Marbell, Phillip
AU - Alaghi, Armin
AU - Carbin, Michael
AU - Darulova, Eva
AU - Dolecek, Lara
AU - Gerstlauer, Andreas
AU - Gillani, Ghayoor
AU - Jevdjic, Djordje
AU - Moreau, Thierry
AU - Cacciotti, Mattia
AU - Daglis, Alexandros
AU - Jerger, Natalie Enright
AU - Falsafi, Babak
AU - Misailovic, Sasa
AU - Sampson, Adrian
AU - Zufferey, Damien
N1 - Funding Information:
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
Publisher Copyright:
© 2020 ACM.
PY - 2020/6
Y1 - 2020/6
N2 - 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.
AB - 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.
KW - Approximate computing
KW - cross-layer optimization
KW - error efficiency
UR - http://www.scopus.com/inward/record.url?scp=85089411152&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85089411152&partnerID=8YFLogxK
U2 - 10.1145/3394898
DO - 10.1145/3394898
M3 - Review article
AN - SCOPUS:85089411152
VL - 53
JO - ACM Computing Surveys
JF - ACM Computing Surveys
SN - 0360-0300
IS - 3
M1 - 51
ER -