ABSTRACTS
1. Analysis of Probability and Energy of Nanometre CMOS Circuits in Presence of Noise
Pinar Korkmaz, Bilge E. S. Akgul and Krishna V. Palem
Electronics Letters, Vol. 43, Issue 17, Aug. 2007.
Motivated by the necessity to consider probabilistic approaches to future designs, probability and switching energy characteristics of probabilistic CMOS (PCMOS) circuits are analysed. Using 90 and 65 nm processes, detailed analytical models for the probability of correctness (p) of these circuits are developed and verified through circuit simulations.
Download the full paper in PDF format
2. Probabilistic System-on-a-Chip Architectures
Lakshmi N. Chakrapani, Pinar Korkmaz, Bilge E. S. Akgul and Krishna V. Palem
ACM Transactions on Design Automation of Electronic Systems (TODAES), Vol. 12, Issue 3, Aug. 2007.
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 x 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).
Download the full paper in PDF format
3. Probabilistic Arithmetic and Energy Efficient Embedded Signal Processing (Received Best Paper Award)
Jason George, Bo Marr, Bilge E. S. Akgul and Krishna V. Palem
Proceedings of the Intl. Conference on Compilers, Architecture and Synthesis for Embedded Systems (CASES), Seoul, Korea, October 23-25, 2006.
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 (PCMOS) 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) of the 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.
Download the full paper in PDF format
4. Probabilistic CMOS Technology: A Survey and Future Directions
Bilge E. S. Akgul, Lakshmi N. Chakrapani, Pinar Korkmaz and Krishna V. Palem
Proceedings of IFIP Intl. Conference on Very Large Scale Integration (VLSI-SoC), Nice, France, October 16-18, 2006.
Highly scaled CMOS devices in the nanoscale regime would inevitably exhibit statistical or probabilistic behavior. Such behavior is due to process variations and other perturbations such as noise. Therefore current circuit design methodologies, which depend on the existence of deterministic and uniform devices with no consideration for either power consumption or probabilistic behavior, would no longer be sufficient to design robust circuits. To help overcome this challenge, we have been characterizing CMOS devices with probabilistic behavior (probabilistic CMOS or PCMOS devices) at several levels: from foundational principles to analytical modeling, simulation, fabrication and measurement, as well as innovative approaches to harnessing PCMOS devices in system-on-a-chip architectures which can implement a wide range of applications. In this paper, we present a broad overview of our contributions in the domain of PCMOS, and outline ongoing work and future challenges in this area.
Download the full paper in PDF format
5. Advocating Noise as an Agent for Ultra-Low Energy Computing: Probabilistic Complementary Metal-Oxide-Semiconductor Devices and Their Characteristics
Pinar Korkmaz, Bilge E. S. Akgul, Krishna V. Palem and Lakshmi N. Chakrapani
Japanese Journal of Applied Physics, SSDM Special Issue Part 1, April 2006.
Noise immunity and low-energy computing have become limiting factors in the semiconductor roadmap as transistor feature sizes shrink. The subject of our study is the probabilistic switch, implemented in the complementary metal-oxide-semiconductor (CMOS) domain, referred to as a probabilistic CMOS (PCMOS) switch, whose behavior is rendered probabilistic by noise. In conducting this study, we are motivated by the possibility of using such probabilistic switches to realize ultra-low energy computing. Based on PCMOS switches realized using 0.5 and 0.25 μm processes, we present detailed analytical models, subsequently verified through HSpice simulations. We consider the thermal noise and power supply noise as our sources for probabilistic behavior. Through one interesting aspect of the study, we characterize the effects of the noise sampling frequency and the output sampling frequency on probabilistic behavior. Finally, we briefly outline the opportunity that such probabilistic switches offer to ultra low-energy computing through the concept of a probabilistic system-on-a-chip (PSoC) architecture (that is based on PCMOS switches); such architectures can achieve significant energy savings and performance improvements at the application level.
Download the full paper in PDF format
6. Ultra-Efficient (Embedded) SOC Architectures based on Probabilistic CMOS (PCMOS) Technology
Lakshmi N. Chakrapani, Bilge E. S. Akgul, Suresh Cheemalavagu, Pinar Korkmaz, Krishna V. Palem and Balasubramanian Seshasayee
Proceedings of the Design Automation and Test in Europe Conference (DATE), Munich, Germany, March 6-10, 2006.
(Earlier version of this paper appeared as CREST Technical Report, CREST-TR-05-08-02.)
Major impediments to technology scaling in the nanometer regime include power (or energy) dissipation and "erroneous" behavior induced by process variations and noise susceptibility. In this paper, we demonstrate that CMOS devices whose behavior is rendered probabilistic by noise (yielding probabilistic CMOS or PCMOS) can be harnessed for ultra low energy and high performance computation. PCMOS devices are inherently probabilistic in that they are guaranteed to compute correctly with a probability 1/2 < p < 1 and thus, by design, they are expected to compute incorrectly with a probability (1 – p). In this paper, we show that PCMOS technology yields significant improvements, both in the energy consumed as well as in the performance, for probabilistic applications with broad utility. These benefits are derived using an application-architecture-technology (A2T) co-designed methodology introduced here, yielding an entirely novel family of probabilistic system-on-a-chip (PSOC) architectures. All of our application and architectural savings are quantified using the product of the energy and the performance denoted (energy x 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.
Download the full paper in PDF format
7. Energy Aware Computing through Probabilistic Switching: A Study of Limits
Krishna V. Palem
IEEE Transactions on Computers, 54(9), pp. 1123-1137, September 2005.
Full version appears as Georgia Tech Technical Report GT-CC-03-16
The main result in this paper establishes the energy savings derived by using probabilistic AND as well as NOT gates constructed from an idealized switch that produces a probabilistic bit (PBIT). A probabilistic switch produces the desired value as an output that is 0 or 1 with probability p, represented as a PBIT, and, hence, can produce the wrong output value with a probability of (1 – p). In contrast with a probabilistic switch, a conventional deterministic switch produces a BIT whose value is always correct. Our switch-based gate constructions are a particular case of a systematic methodology developed here for building energy-aware networks for computing, using PBITs. Interesting examples of such networks include AND, OR, and NOT gates (or, as functions, Boolean conjunction, disjunction, and negation, respectively). To quantify the energy savings, novel measures of "technology independent" energy complexity are also introduced here — these measures parallel conventional machine-independent notions of computational complexity such as the algorithm's running time and space. Networks of switches can be related to Turing machines and to Boolean circuits, both of which are widely known and well-understood models of computation. Our gate and network constructions lend substance to the following thesis (established for the first time by this author [1], [2], [3]): The mathematical technique referred to as randomization yielding probabilistic algorithms results in energy savings through a physical interpretation based on statistical thermodynamics and, hence, can serve as a basis for energy-aware computing. While the estimates of the energy saved through PBIT-based probabilistic computing switches and networks developed here rely on the constructs and thermodynamic models due to Boltzmann, Gibbs, and Planck, this work has also led to the innovation of probabilistic CMOS-based devices and computing frameworks. Thus, for completeness, the relationship between the physical models on which this work is based and the electrical domain of CMOS-based switching will be discussed.
Download the full paper in PDF format
8. Computational Proof as Experiment: Probabilistic Algorithms from a Thermodynamic Perspective*,**
Krishna V. Palem
Proceedings of the Intl. Symposium on Verification (Theory and Practice), Taormina, Sicily, Italy, June 29-July 4, 2003.
A novel framework for the design and analysis of energy-aware algorithms is presented, centered around a deterministic Bit-level (Boltzmann) Random Access Machine or BRAM model of computing, as well its probabilistic counterpart, the RABRAM. Using this framework, it is shown for the first time that probabilistic algorithms can yield asymptotic savings in the energy consumed, over their deterministic counterparts. Concretely, we show that the expected energy savings derived from a probabilistic RABRAM algorithm for solving the distinct vector problem (or DVP for short) introduced here, over any deterministic BRAM algorithm grows as Ω(n log (n/n-εlog(n))), even though the corresponding deterministic and probabilistic algorithms have the same (asymptotic) time-complexity of Θ(n). Also, our probabilistic algorithm is guaranteed to be correct with a probability p≥ (1–1/nc) (for a constant c chosen as a design parameter). As usual n denotes the length of the input instance of the DVP measured in the number of bits. These results are derived in the context of a technology-independent complexity measure for energy consumption introduced here, referred to as logical work. In keeping with the theme of the symposium, the introduction to this work is presented in the context of "computational proof" (algorithm) and the "work done" to achieve it (its energy complexity characterized as logical work).
Download the full paper in PDF format
9. Energy Aware Algorithm Design via Probabilistic Computing: From Algorithms and Models to Moore's Law and Novel (Semiconductor) Devices
Krishna V. Palem
Proceedings of the Intl. Conference on Compilers, Architecture and Synthesis for Embedded Systems (CASES), October 30-November 1, 2003.
"Do not worry about your difficulties in Mathematics; I can assure you that mine are still greater."
--Albert Einstein
With their ever increasing proliferation, concerns of power (or energy) consumption have become significant in the context of the design and as well as the use of computing systems. While devices, computer architecture and the layers of software that reside and execute at higher levels of abstraction (such as operating systems, run-time, compilers and programming languages) all afford opportunities for being energy-aware, the most fundamental limits are truly rooted in the physics of energy consumption — specifically in thermodynamics. Based on this premise, this paper embodies the innovation of models of computing for energy-aware algorithm design and analysis, culminating in establishing, for the first time, the following central thesis of this work: the computational technique referred to as randomization yielding probabilistic algorithms, now ubiquitous to the mathematical theory of algorithm design and analysis, when interpreted as a physical phenomenon through classical statistical thermodynamics with such pioneers as Maxwell, Boltzmann and Gibbs at the helm, leads to energy savings that are proportional to the probability p with which each primitive computational step is guaranteed to be correct (or equivalently to the probability of error of (1 – p)).
Download the full paper in PDF format