Exploiting Errors for Efficiency: A Survey from Circuits to Algorithms <s> Theoretical bounds <s> When logic upsets (faults) affect digital representations of numbers, it is possible to consider their effects in terms of the magnitude of the value deviation they induce. When some upper limit on such a change in value is tolerable, one may consider techniques for encoding to limit value deviations in the presence of faults. Examples of applications with tolerance to value deviation include computer graphics computations, and the computation, communication and storage of analog sensor values in sensor networks. This article presents upper bounds for the achievable efficiency of encoding under the constraint relaxation of a tolerable value deviation. Closed-form expressions and numerical evaluations for upper bounds on the achievable encoding efficiency under a maximum tolerable value deviation, for several different conditions under which logic upsets may occur, are presented. The bounds demonstrate the possibility of significant gains in encoding efficiency, when some semantic deviation of values is tolerable. Lower and upper bounds on the possible absolute value of deviation resulting from a given number of upsets in words of a known size are provided. It is shown that, if possible to bias the physical design of a system such that logic upsets in both high and low logic direction may occur simultaneously (versus only one or the other), the minimum values of the resulting deviations will be reduced. <s> BIB001 </s> Exploiting Errors for Efficiency: A Survey from Circuits to Algorithms <s> Theoretical bounds <s> Departing from traditional communication theory where decoding algorithms are assumed to perform without error, a system where noise perturbs both computational devices and communication channels is considered here. This paper studies limits in processing noisy signals with noisy circuits by investigating the effect of noise on standard iterative decoders for low-density parity-check (LDPC) codes. Concentration of decoding performance around its average is shown to hold when noise is introduced into message-passing and local computation. Density evolution equations for simple faulty iterative decoders are derived. In one model, computing nonlinear estimation thresholds shows that performance degrades smoothly as decoder noise increases, but arbitrarily small probability of error is not achievable. Probability of error may be driven to zero in another system model; the decoding threshold again decreases smoothly with decoder noise. As an application of the methods developed, an achievability result for reliable memory systems constructed from unreliable components is provided. <s> BIB002 </s> Exploiting Errors for Efficiency: A Survey from Circuits to Algorithms <s> Theoretical bounds <s> With scaling of process technologies and increase in process variations, embedded memories will be inherently unreliable. Approximate computing is a new class of techniques that relax the accuracy requirement of computing systems. In this paper, we present the A daptive Co ding for approximate Co mputing (ACOCO) framework, which provides us with an analysis-guided design methodology to develop adaptive codes for different computations on the data read from faulty memories. In ACOCO, we first compress the data by introducing distortion in the source encoder, and then add redundant bits to protect the data against memory errors in the channel encoder. We are thus able to protect the data against memory errors without additional memory overhead so that the coded data have the same bit-length as the uncoded data. We design the source encoder by first specifying a cost function measuring the effect of the data compression on the system output, and then design the source code according to this cost function. We develop adaptive codes for two types of systems under ACOCO. The first type of systems we consider, which includes many machine learning and graph-based inference systems, is the systems dominated by product operations. We evaluate the cost function statistics for the proposed adaptive codes, and demonstrate its effectiveness via two application examples: max-product image denoising and naive Bayesian classification. Next, we consider another type of systems: iterative decoders with min operation and sign-bit decision, which are widely applied in wireless communication systems. We develop an adaptive coding scheme for the min-sum decoder subject to memory errors. A density evolution analysis and simulations on finite length codes both demonstrate that the decoder with our adaptive code achieves a residual error rate that is on the order of the square of the residual error rate achieved by the nominal min-sum decoder. <s> BIB003 </s> Exploiting Errors for Efficiency: A Survey from Circuits to Algorithms <s> Theoretical bounds <s> In the nanoscale regime, the behavior of both extant and emerging semiconductor devices are often unreliable. Reliability of such devices often trades-off with their energy consumption, speed, and/or chip area. We study the energy-reliability limits for circuits designed using such devices. Using the mutual information propagation in logic circuits technique developed by Pippenger, together with optimization, we obtain lower bounds on the energy consumption for computing n-input boolean functions. Most extant technologies require all gates to have the same electrical operating point and in circuits of such uniform gates, the minimum energy required to achieve any non-trivial reliability scales superlinearly with the number of inputs. On the other hand, in some emerging technologies such as spin electronics, where the gates in a circuit can have different operating points, energy scaling can be linear in the number of inputs. As part of our development we find a simple procedure for energy allocation across gates in a boolean circuit with different operating points. <s> BIB004
Recent research has used information theory as a foundation to investigate theoretical bounds on performance  , efficiency BIB001 , energy consumption BIB004 , Shannon-style channel capacity and storage bounds BIB001 BIB002 for computing and communication systems which trade resource usage for correctness. Varshney BIB002 demonstrates Shannon-style bounds on storage capacity in the context of noisy LDPC iterative decoders. Stanley-Marbell BIB001 derives best-case efficiency bounds for encoding techniques which limit the deviations of values in the presence of logic upsets. Chatterjee et al. BIB004 present lower bounds on energy consumption for achieving a desired level of reliability in computation of an n-input Boolean function and Yazdi et al.  formulate an optimization problem to produce a noisy Gallager B LDPC decoder that achieves minimal bit error rate, by treating unreliable hardware components as communication channels as in stochastic computing (see Section 5 for coverage of stochastic computing). These recent research efforts demonstrate that information and coding theory can provide a baseline to derive bounds on efficiency, capacity, energy consumption, and performance in the systems of interest in this survey: computing systems which trade resource usage for correctness. 10.3 Application-aware source and channel coding across the hardware stack Mitigating the effects of errors across the stack will ultimately require encoding techniques, applied across the layers of the stack that are designed to take advantage of application characteristics. Early examples of such application-aware codes can be found in the work of Huang et al. BIB003 which proposes a redundancy-free adaptive code that can correct errors in data retrieved from potentially faulty cells. The technique relies on an application-specific cost function and an input-adaptive coding scheme that pairs a source encoder that introduces modest distortion, with a channel encoder that adds redundant bits to protect the distorted data against errors. Adaptive coding can greatly reduce output quality degradation in the presence of noise, compared to naïve implementations where noise is allowed to traverse the stack unchecked.