Stochastic computing is a collection of techniques that represent continuous values by streams of random bits. Complex computations can then be computed by simple bit-wise operations on the streams. Stochastic computing is distinct from the study of randomized algorithms.
Motivation and a simple example Suppose that p , q ∈ [ 0 , 1 ] {\displaystyle p,q\in [0,1]} is given, and we wish to compute p × q {\displaystyle p\times q} . Stochastic computing performs this operation using probability instead of arithmetic. Specifically, suppose that there are two random, independent bit streams called stochastic numbers (i.e. Bernoulli processes), where the probability of a 1 in the first stream is p {\displaystyle p} , and the probability in the second stream is q {\displaystyle q} . We can take the logical AND of the two streams.
The probability of a 1 in the output stream is p q {\displaystyle pq} . By observing enough output bits and measuring the frequency of 1s, it is possible to estimate p q {\displaystyle pq} to arbitrary accuracy. The operation above converts a fairly complicated computation (multiplication of p {\displaystyle p} and q {\displaystyle q} ) into a series of very simple operations (evaluation of a i ∧ b i {\displaystyle a_{i}\land b_{i}} ) on random bits. To put in another perspective, assuming the truth table of an AND gate. Conventional interpretation is that the output is true if and only if input A and B are true. However, if the table is interpreted vertically, (0011) AND (0101) is (0001), i.e., 1/2 x 1/2 = 1/4, which is exactly an arithmetic multiplication. As the information is presented in probability distribution, probability multiplication is literally an AND operation.
More generally speaking, stochastic computing represents numbers as streams of random bits and reconstructs numbers by calculating frequencies. The computations are performed on the streams and translate complicated operations on p {\displaystyle p} and q {\displaystyle q} into simple operations on their stream representations. (Because of the method of reconstruction, devices that perform these operations are sometimes called stochastic averaging processors.) In modern terms, stochastic computing can be viewed as an interpretation of calculations in probabilistic terms, which are then evaluated with a Gibbs sampler. It can also be interpreted as a hybrid analog/digital computer.
History
Stochastic computing was first introduced in a pioneering paper by John von Neumann in 1953. However, the theory could not be fully developed until advances in computing of the 1960s,
mostly through a series of simultaneous and parallel efforts in the US and the UK. By the late 1960s, attention turned to the design of special-purpose hardware to perform stochastic computation. A host of these machines were constructed between 1969 and 1974; RASCEL is pictured in this article. Despite the intense interest in the 1960s and 1970s, stochastic computing ultimately failed to compete with more traditional digital logic, for reasons outlined below. The first (and last) International Symposium on Stochastic Computing took place in 1978; active research in the area dwindled over the next few years. Although stochastic computing declined as a general method of computing, it has shown promise in several applications. Research has traditionally focused on certain tasks in machine learning and control.
Somewhat recently, interest has turned towards stochastic decoding, which applies stochastic computing to the decoding of error correcting codes. More recently, stochastic circuits have been successfully used in image processing tasks such as edge detection and image thresholding. Recent advancement in stochastic circuits also shows promising speed and energy efficiency advantages in artificial intelligence (AI) hardware acceleration on edge computing.
Strengths and weaknesses Although stochastic computing was a historical failure, it may still remain relevant for solving certain problems. To understand when it remains relevant, it is useful to compare stochastic computing with more traditional methods of digital computing.
Strengths Suppose we wish to multiply two numbers each with n {\displaystyle n} bits of precision. Using the typical long multiplication method, we need to perform
… excerpt ends here. Continue reading the full article.
