Probabilistic Boolean logic, arithmetic and architectures

In this dissertation, we introduce a logic and arithmetic combined with probabilistic behaviors. First, we define models of computation rooted in the resulting Probabilistic Boolean Logic (PBL), and demonstrate a system-on-a-chip architecture based on these models. Next, we extend PBL to arithmetic and study the properties of the resulting arithmetic. In both cases (PBL gates as well as probabilistic arithmetic), the introduction of probabilistic behavior yields significant gains in the in the physical domain. These gains are in the energy consumed and the overall performance (speed) of computing. These developments collectively offer theoretical and empirical proof to support the thesis.;Parameter variations, noise susceptibility, and increasing energy dissipation of complementary metal oxide semiconductor (CMOS) devices (transistors) have been recognized as major challenges in circuit and architecture design in the nanometer regime. Among these, parametric variations and noise susceptibility increasingly cause CMOS devices to behave in an unreliable or "probabilistic" manner. This is true for novel non- CMOS materials as well, whose properties and manufacturing difficulties cause logic elements to behave in a probabilistic manner. To address these challenges, a shift in the design paradigm from current-day deterministic designs to statistical or probabilistic designs is deemed inevitable.;In this context, it should be noted that advances in Boolean logic, an understanding of its properties, and algorithms based on such properties have played a vital role in the design and synthesis of digital circuits. If an analogous approach were to be adopted to theoretically characterize probabilistic logic elements, considerations of probability need to be injected into Boolean logic.;Motivated by these facts and considerations, a Probabilistic Boolean Logic, whose logical operators are by definition "correct" with a probability 1/2 ≤ p ≤ 1 is introduced. To characterize the meaning of a probabilistic Boolean formula (PBF) in this logic, we introduce and study the concept of event sets. Event sets serve as a basis for developing the laws of probabilistic Boolean logic. While most of the laws of Boolean logic can be naturally extended and shown to be valid in the case of probabilistic Boolean logic, there are some surprising differences. Based on probabilistic Boolean logic, we study two models of computation: the probabilistic Boolean circuit, and the probabilistic automaton whose transition function is computed by such a circuit.;To empirically demonstrate the utility and advantages of probabilistic Boolean circuits, we introduce and study a novel family of probabilistic architectures: the probabilistic system-on-a-chip (PSOC) architecture. These are based on CMOS devices rendered probabilistic due to noise, which are referred to as probabilistic CMOS or PCMOS devices. In addition to harnessing the probabilistic behavior of PCMOS devices, PSOC architectures yield significant improvements, in terms of energy as well as performance, in the context of probabilistic applications with broad utility. All of the 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 realization.;Finally, we extend the consideration of probability of correctness from logic to arithmetic through Probabilistic Arithmetic, where the magnitude of correctness of an arithmetic operation may be traded for its energy; we can show that a relatively small amount of error in the arithmetic operators can be traded for significant energy savings. This work provides the theoretical basis for the energy savings reported in the video decoding and radar processing applications, performed using digital filters realized using probabilistic arithmetic operations, that has been demonstrated by George et al. [66].