Exploiting Errors for Efficiency: A Survey from Circuits to Algorithms

Abstract

When a computational task tolerates a relaxation of its specification or when an algorithm tolerates the effects of noise in its execution, hardware, programming languages, and system software 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 users can tolerate, from across the disciplines of computer aided design of circuits, digital system design, computer architecture, programming languages, operating systems, and information theory. Rather than over-provisioning resources at each layer to avoid errors, it can be more efficient to exploit the masking of errors occurring at one layer which can prevent them from propagating to a higher layer. We survey tradeoffs for individual layers of computing systems from the circuit level to the operating system level and illustrate the potential benefits of end-to-end approaches using two illustrative examples. To tie together the survey, we present a consistent formalization of terminology, across the layers, which does not significantly deviate from the terminology traditionally used by research communities in their layer of focus.

arXiv comment35 pages

References in corpus (12)

• MobileNets: Efficient Convolutional Neural Networks for Mobile Vision Applications
• SqueezeNet: AlexNet-level accuracy with 50x fewer parameters and <0.5MB model size
• Deep Compression: Compressing Deep Neural Networks with Pruning, Trained Quantization and Huffman Coding
• FitNets: Hints for Thin Deep Nets
• BinaryConnect: Training Deep Neural Networks with binary weights during propagations
• Exploiting Linear Structure Within Convolutional Networks for Efficient Evaluation
• Compressing Neural Networks with the Hashing Trick
• Limits on Fundamental Limits to Computation
• Compression of Deep Convolutional Neural Networks for Fast and Low Power Mobile Applications
• Probabilistic Value-Deviation-Bounded Integer Codes for Approximate Communication
• A Hardware Platform for Efficient Multi-Modal Sensing with Adaptive Approximation
• Incremental Color Quantization for Color-Vision-Deficient Observers Using Mobile Gaming Data