Exploiting Errors for Efficiency: A Survey from Circuits to Algorithms <s> Stochastic computing: unary representation and computing on probabilities <s> The implementation of artificial neural networks using stochastic arithmetic capable of in situ learning is described. Stochastic arithmetic uses values encoded as a pulse density, and allows addition, multiplication, and the nonlinearity to be implemented in a very small amount of digital hardware. A VLSI implementation of such a network is capable of processing 100000 training vectors per second. The performance of this architecture is demonstrated by two examples. > <s> BIB001 </s> Exploiting Errors for Efficiency: A Survey from Circuits to Algorithms <s> Stochastic computing: unary representation and computing on probabilities <s> A new architecture and a statistical model for a pulse-mode digital multilayer neural network (DMNN) are presented. Algebraic neural operations are replaced by stochastic processes using pseudo-random pulse sequences. Synaptic weights and neuron states are represented as probabilities and estimated as average rates of pulse occurrences in corresponding pulse sequences. A statistical model of error (or noise) is developed to estimate relative accuracy associated with stochastic computing in terms of mean and variance. The stochastic computing technique is implemented with simple logic gates as basic computing elements leading to a high neuron-density on a chip. Furthermore, the use of simple logic gates for neural operations, the pulse-mode signal representation, and the modular design techniques lead to a massively parallel yet compact and flexible network architecture, well suited for VLSI implementation. Any size of a feedforward network can be configured where processing speed is independent of the network size. Multilayer feedforward networks are modeled and applied to pattern classification problems such as encoding and character recognition. > <s> BIB002 </s> Exploiting Errors for Efficiency: A Survey from Circuits to Algorithms <s> Stochastic computing: unary representation and computing on probabilities <s> Among the different pulse codification techniques, stochastic pulse codification has its own arithmetic based on the similarity between Boolean algebra and statistical algebra. Summation and multiplication are the two basic arithmetic operations treated in depth in the literature. In this paper we present two digital stochastic circuits that extend traditional stochastic algebra: a division circuit and a square-root circuit, and the interfaces between the analog and stochastic domain. As a result, we are able to process analog input signals with a simple and complete processing system. These circuits can be implemented in low-cost and low-power digital programmable devices. <s> BIB003 </s> Exploiting Errors for Efficiency: A Survey from Circuits to Algorithms <s> Stochastic computing: unary representation and computing on probabilities <s> Mounting concerns over variability, defects, and noise motivate a new approach for digital circuitry: stochastic logic, that is to say, logic that operates on probabilistic signals and so can cope with errors and uncertainty. Techniques for probabilistic analysis of circuits and systems are well established. We advocate a strategy for synthesis. In prior work, we described a methodology for synthesizing stochastic logic, that is to say logic that operates on probabilistic bit streams. In this paper, we apply the concept of stochastic logic to a reconfigurable architecture that implements processing operations on a datapath. We analyze cost as well as the sources of error: approximation, quantization, and random fluctuations. We study the effectiveness of the architecture on a collection of benchmarks for image processing. The stochastic architecture requires less area than conventional hardware implementations. Moreover, it is much more tolerant of soft errors (bit flips) than these deterministic implementations. This fault tolerance scales gracefully to very large numbers of errors. <s> BIB004 </s> Exploiting Errors for Efficiency: A Survey from Circuits to Algorithms <s> Stochastic computing: unary representation and computing on probabilities <s> Stochastic computing (SC) was proposed in the 1960s as a low-cost alternative to conventional binary computing. It is unique in that it represents and processes information in the form of digitized probabilities. SC employs very low-complexity arithmetic units which was a primary design concern in the past. Despite this advantage and also its inherent error tolerance, SC was seen as impractical because of very long computation times and relatively low accuracy. However, current technology trends tend to increase uncertainty in circuit behavior and imply a need to better understand, and perhaps exploit, probability in computation. This article surveys SC from a modern perspective where the small size, error resilience, and probabilistic features of SC may compete successfully with conventional methodologies in certain applications. First, we survey the literature and review the key concepts of stochastic number representation and circuit structure. We then describe the design of SC-based circuits and evaluate their advantages and disadvantages. Finally, we give examples of the potential applications of SC and discuss some practical problems that are yet to be solved. <s> BIB005 </s> Exploiting Errors for Efficiency: A Survey from Circuits to Algorithms <s> Stochastic computing: unary representation and computing on probabilities <s> A two-terminal memristor device is a promising digital memory for its high integration density, substantially lower energy consumption compared to CMOS, and scalability below 10 nm. However, a nanoscale memristor is an inherently stochastic device, and extra energy and latency are required to make a deterministic memory based on memristors. Instead of enforcing deterministic storage, we take advantage of the nondeterministic memory for native stochastic computing, where the randomness required by stochastic computing is intrinsic to the devices without resorting to expensive stochastic number generation. This native stochastic computing system can be implemented as a hybrid integration of memristor memory and simple CMOS stochastic computing circuits. We use an approach called group write to program memristor memory cells in arrays to generate random bit streams for stochastic computing. Three methods are proposed to program memristors using stochastic bit streams and compensate for the nonlinear memristor write function: voltage predistortion, parallel single-pulse write, and downscaled write and upscaled read. To evaluate these technical approaches, we show by simulation a memristor-based stochastic processor for gradient descent optimization, and k-means clustering. The native stochastic computing based on memristors demonstrates key advantages in energy and speed in compute-intensive, data-intensive, and probabilistic applications. <s> BIB006 </s> Exploiting Errors for Efficiency: A Survey from Circuits to Algorithms <s> Stochastic computing: unary representation and computing on probabilities <s> Stochastic computing (SC) is a low-cost design technique that has great promise in applications such as image processing. SC enables arithmetic operations to be performed on stochastic bit-streams using ultra-small and low-power circuitry. However, accurate computations tend to require long run-times due to the random fluctuations inherent in stochastic numbers (SNs). We present novel techniques for SN generation that lead to better accuracy/run-time trade-offs. First, we analyze a property called progressive precision (PP) which allows computational accuracy to grow systematically with run-time. Second, borrowing from Monte Carlo methods, we show that SC performance can be greatly improved by replacing the usual pseudo-random number sources by low-discrepancy (LD) sequences that are predictably progressive. Finally, we evaluate the use of LD stochastic numbers in SC, and show they can produce significantly faster and more accurate results than existing stochastic designs. <s> BIB007 </s> Exploiting Errors for Efficiency: A Survey from Circuits to Algorithms <s> Stochastic computing: unary representation and computing on probabilities <s> Recent advances in neural networks (NNs) exhibit unprecedented success at transforming large, unstructured data streams into compact higher-level semantic information for tasks such as handwriting recognition, image classification, and speech recognition. Ideally, systems would employ near-sensor computation to execute these tasks at sensor endpoints to maximize data reduction and minimize data movement. However, near- sensor computing presents its own set of challenges such as operating power constraints, energy budgets, and communication bandwidth capacities. In this paper, we propose a stochastic- binary hybrid design which splits the computation between the stochastic and binary domains for near-sensor NN applications. In addition, our design uses a new stochastic adder and multiplier that are significantly more accurate than existing adders and multipliers. We also show that retraining the binary portion of the NN computation can compensate for precision losses introduced by shorter stochastic bit-streams, allowing faster run times at minimal accuracy losses. Our evaluation shows that our hybrid stochastic-binary design can achieve 9.8x energy efficiency savings, and application-level accuracies within 0.05% compared to conventional all-binary designs. <s> BIB008 </s> Exploiting Errors for Efficiency: A Survey from Circuits to Algorithms <s> Stochastic computing: unary representation and computing on probabilities <s> Stochastic computing (SC) is an unconventional method of computation that treats data as probabilities. Typically, each bit of an ${N}$ -bit stochastic number (SN) ${X}$ is randomly chosen to be 1 with some probability $p_{X}$ , and ${X}$ is generated and processed by conventional logic circuits. For instance, a single AND gate performs multiplication. The value X of an SN is measured by the density of 1 s in it, an information-coding scheme also found in biological neural systems. SC has uses in massively parallel systems and is very tolerant of soft errors. Its drawbacks include low accuracy, slow processing, and complex design needs. Its ability to efficiently perform tasks like communication decoding and neural network inference has rekindled interest in the field. Many challenges remain to be overcome, however, before SC becomes widespread. In this paper, we discuss the evolution of SC, mostly focusing on recent developments. We highlight the main challenges and discuss potential methods of overcoming them. <s> BIB009
Stochastic computing (SC) uses a data representation of bit streams that denote real-valued probabilities BIB009 . In theory, the probabilities can have unbounded precision, but in practice, the length of the bit-streams determines precision BIB005 . SC was first introduced in the 1960s  and its main benefit is that it allows arithmetic operations to be implemented via simple logic gates: a single and gate performs SC multiplication. This made SC attractive in the era of expensive transistors. But as transistors became cheaper, SC's benefit faded away, and its main drawbacks, i.e., limited speed and precision, became dominant BIB005 . For this reason, SC was only used in certain applications, such as neural networks BIB001 BIB002 and control systems BIB003 . SC has seen renewed interest over the last decade BIB005 , mainly because of its energy efficiency. SC's probabilistic nature copes with new inherently random technologies such as memristors BIB006 . Furthermore, the unary encoding of numbers on SC makes the computation robust against errors BIB004 , and allows variable precision computation BIB007 . With the low precision requirement of modern machine learning applications, SC is becoming an attractive alternative to conventional binary-encoded computation BIB008 .