Exploiting Errors for Efficiency: A Survey from Circuits to Algorithms <s> FUNDAMENTAL LIMITS OF RESOURCE VERSUS CORRECTNESS TRADEOFFS <s> In this paper we study the ability of array-based networks to tolerate worst-case faults. We show that an $N \times N$ two-dimensional array can sustain $N^{1-\epsilon}$ worst-case faults, for any fixed $\epsilon > 0$, and still emulate $T$ steps of a fully functioning $N \times N$ array in $O(T+N)$ steps, i.e., with only constant slowdown. Previously, it was known only that an array could tolerate a constant number of faults with constant slowdown. We also show that if faulty nodes are allowed to communicate, but not compute, then an $N$-node one-dimensional array can tolerate $\log^k N$ worst-case faults, for any constant $k > 0$, and still emulate a fault-free array with constant slowdown, and this bound is tight. <s> BIB001 </s> Exploiting Errors for Efficiency: A Survey from Circuits to Algorithms <s> FUNDAMENTAL LIMITS OF RESOURCE VERSUS CORRECTNESS TRADEOFFS <s> Lossy coding of speech, high-quality audio, still images, and video is commonplace today. However, in 1948, few lossy compression systems were in service. Shannon introduced and developed the theory of source coding with a fidelity criterion, also called rate-distortion theory. For the first 25 years of its existence, rate-distortion theory had relatively little impact on the methods and systems actually used to compress real sources. Today, however, rate-distortion theoretic concepts are an important component of many lossy compression techniques and standards. We chronicle the development of rate-distortion theory and provide an overview of its influence on the practice of lossy source coding. <s> BIB002 </s> Exploiting Errors for Efficiency: A Survey from Circuits to Algorithms <s> FUNDAMENTAL LIMITS OF RESOURCE VERSUS CORRECTNESS TRADEOFFS <s> It is shown that if a formula is constructed from noisy 2-input NAND gates, with each gate failing independently with probability E, then reliable computation can or cannot take place according as /spl epsiv/ is less than or greater than /spl epsiv//sub 0/=(3-/spl radic/7)/4=0.08856.... <s> BIB003 </s> Exploiting Errors for Efficiency: A Survey from Circuits to Algorithms <s> FUNDAMENTAL LIMITS OF RESOURCE VERSUS CORRECTNESS TRADEOFFS <s> In this paper, we propose a framework for low-energy digital signal processing (DSP) where the supply voltage is scaled beyond the critical voltage required to match the critical path delay to the throughput. This deliberate introduction of input-dependent errors leads to degradation in the algorithmic performance, which is compensated for via algorithmic noise-tolerance (ANT) schemes. The resulting setup comprised of the DSP architecture operating at sub-critical voltage and the error control scheme is referred to as soft DSP. It is shown that technology scaling renders the proposed scheme more effective as the delay penalty suffered due to voltage scaling reduces due to short channel effects. The effectiveness of the proposed scheme is also enhanced when arithmetic units with a higher "delay-imbalance" are employed. A prediction based error-control scheme is proposed to enhance the performance of the filtering algorithm in presence of errors due to soft computations. For a frequency selective filter, it is shown that the proposed scheme provides 60%-81% reduction in energy dissipation for filter bandwidths up to 0.5 /spl pi/ (where 2 /spl pi/ corresponds to the sampling frequency f/sub s/) over that achieved via conventional voltage scaling, with a maximum of 0.5 dB degradation in the output signal-to-noise ratio (SNR/sub o/). It is also shown that the proposed algorithmic noise-tolerance schemes can be used to improve the performance of DSP algorithms in presence of bit-error rates of up to 10/sup -3/ due to deep submicron (DSM) noise. <s> BIB004
Section 5 through Section 8 presented concrete techniques for trading resource usage for correctness at levels of abstraction ranging form the device-, gate-, and circuit-level, to the operating system. For techniques at each of these levels of abstraction, this article formulated the resource usage versus correctness tradeoff in terms of a computational problem, its implementation in an algorithm, and a distance function d between the state representations of a computation's correct and resource-reduced variants. That relation between a computation's input and output or between a computation's state prior to and subsequent to computation has parallels to communication systems. We can draw an analogy between the state transformation performed by an algorithm which must consume resources (time, energy, die area) to achieve the exact behavior specified by the computational problem which it implements, and source-and channel-coding for communication over a channel: Source-and channel-coding which likewise consume resources in order to maximize the mutual information between the transmitter and receiver over a channel. Von Neumann  , Berger and Gibson BIB002 , Evans BIB003 , Maggs BIB001 , Elias  , Spielman  , and Shanbhag BIB004 , among others, have previously drawn similar analogies between resource usage versus correctness tradeoffs and communication channels. And doing so provides a useful lens through which to study the fundamental limits of resource usage versus correctness tradeoffs in computing systems.