Exploiting Errors for Efficiency: A Survey from Circuits to Algorithms <s> Probabilistic computing: exploiting device-level noise for efficiency <s> The energy consumed by computations is becoming an increasing concern both within the context of high-performance systems well as embedded systems, on par with the past focus on raw speed or its derivative performance. In this talk, we will outline a novel framework for designing and analyzing algorithms wherein the figure of merit is the energy complexity – a measure of the (physical) energy consumed. Using the formulation of an energy-aware switch, and a network of such switches, fundamental limits will be established for the energy needed for switching deterministically, as well as energy savings derived from probabilistic switching, with a probability of being correct, p. Specifically, it is shown that a single deterministic switching step for computing a BIT consumes at least (.(κ.T ln(2))) Joules of energy, whereas the energy consumed by a single probabilistic switching step to compute a PBIT can be as low as (.(κ.T ln(2p))) Joules. These results are developed within the context of an idealized switching device introduced here, constrained by the laws of classical (statistical) thermodynamics (of Maxwell, Boltzmann and Gibbs), as well as by the constraints of idealized semiconductor devices. Based on this notion of switching, models for algorithm analysis and design, as well as upper- and lower- bounds on energy complexity and hence, for the first time, asymptotic energy savings via the use of probabilistic computing will be established. Possible approaches to realizing these probabilistic switches using conventional CMOS technology, as well as their potential for accelerating the current semiconductor roadmap that is based on deterministic computing, including the projections implied by Moore’s law, will be outlined. This work draws upon basic concepts from computer science, microelectronics and classical thermodynamics, and in the interest of being self-contained, the presentation will include a brief survey of the relevant thermodynamics. <s> BIB001 </s> Exploiting Errors for Efficiency: A Survey from Circuits to Algorithms <s> Probabilistic computing: exploiting device-level noise for efficiency <s> Probabilistic arithmetic, where the ith output bit of addition and multiplication is correct with a probability pi , is shown to be a vehicle for realizing extremely energy-efficient, embedded computing. Specifically, probabilistic adders and multipliers, realized using elements such as gates that are in turn probabilistic, are shown to form a natural basis for primitives in the signal processing (DSP) domain. In this paper, we show that probabilistic arithmetic can be used to compute the FFT in an extremely energy-efficient manner, yielding energy savings of over 5. 6X in the context of the widely used synthetic aperture radar (SAR) application [1]. Our results are derived using novel probabilistic cmos (PC-MOS) technology, characterized and applied in the past to realize ultra-efficient architectures for probabilistic applications [2, 3, 4]. When applied to the dsp domain, the resulting error in the output of a probabilistic arithmetic primitive, such as an adder for example, manifests as degradation in the signal-to-noise ratio (SNR) ofthe sar image that is reconstructed through the FFT algorithm. In return for this degradation that is enabled by our probabilistic arithmetic primitives ?- degradation visually indistinguishable from an image reconstructed using conventional deterministic approaches -- significant energy savings and performance gains are shown to be possible per unit of SNR degradation. These savings stem from a novel method of voltage scaling, which we refer to as biased voltage scaling (or BIVOS), that is the major technical innovation on which our probabilistic designs are based. <s> BIB002 </s> Exploiting Errors for Efficiency: A Survey from Circuits to Algorithms <s> Probabilistic computing: exploiting device-level noise for efficiency <s> Parameter variations, noise susceptibility, and increasing energy dissipation of cmos devices have been recognized as major challenges in circuit and microarchitecture design in the nanometer regime. Among these, parameter variations and noise susceptibility are increasingly causing cmos devices to behave in an “unreliable” or “probabilistic” manner. To address these challenges, a shift in design paradigm from current-day deterministic designs to “statistical” or “probabilistic” designs is deemed inevitable. To respond to this need, in this article, we introduce and study an entirely novel family of probabilistic architectures: the probabilistic system-on-a-chip (psoc). psoc architectures are based on cmos devices rendered probabilistic due to noise, referred to as probabilistic CMOS or PCMOS devices. We demonstrate that in addition to harnessing the probabilistic behavior of pcmos devices, psoc architectures yield significant improvements, both in energy consumed as well as performance in the context of probabilistic or randomized applications with broad utility. All of our application and architectural savings are quantified using the product of the energy and performance, denoted (energy × performance): The pcmos-based gains are as high as a substantial multiplicative factor of over 560 when compared to a competing energy-efficient cmos-based realization. Our architectural design is application specific and involves navigating design space spanning the algorithm (application), its architecture (psoc), and the probabilistic technology (pcmos). <s> BIB003 </s> Exploiting Errors for Efficiency: A Survey from Circuits to Algorithms <s> Probabilistic computing: exploiting device-level noise for efficiency <s> Numerous computing applications can tolerate low error rates. In such applications, inexact approaches provide the ability to achieve significantly lower power. This work demonstrates the power-error trade-offs that can be achieved. Using probabilistic modeling in sub-50-nm silicon transistor technology, the relationship between statistical uncertainties and errors are elucidated for different configurations and topologies and the trade-offs quantified. Gate-level implementation of the probabilistic CMOS logic is validated by circuit simulations of a commercial 45-nm SOI CMOS process technology. Using a practical ALU architecture where voltages can be scaled from most significant to least significant bit blocks as an example, the potential benefits of this technique are shown. A calculation error of 10−6, an error rate quite tolerable for many computational tasks, is shown to be possible with a total power reduction of more than 40p. <s> BIB004
A line of research pioneered by Palem et al.  BIB001 ("probabilistic computing") proposes harnessing intrinsic thermal noise of CMOS circuits to improve the performance of probabilistic algorithms that exploit a source of entropy for their execution. Chakrapani et al. BIB003 show an improvement in the energy-performance product for algorithms such as Bayesian inference, probabilistic cellular automata, and random neural networks using this approach and they establish a tradeoff between the energy consumption and the probability of correctness of a circuit's behavior. These techniques have also shown energy savings for digital signal processing algorithms that do not employ probabilistic algorithms but which can tolerate some amount of noise BIB002 BIB004 .