Stochastic computing
Stochastic computing is a collection of techniques that represent continuous values by streams of random bits.
(Because of the method of reconstruction, devices that perform these operations are sometimes called stochastic averaging processors.)
Stochastic computing was first introduced in a pioneering paper by John von Neumann in 1953.
[1] However, the theory could not be fully developed until advances in computing of the 1960s,[2] [3] mostly through a series of simultaneous and parallel efforts in the US[4] and the UK.
[5] By the late 1960s, attention turned to the design of special-purpose hardware to perform stochastic computation.
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[8] took place in 1978; active research in the area dwindled over the next few years.
[13] Recent advancement in stochastic circuits also shows promising speed and energy efficiency advantages in artificial intelligence (AI) hardware acceleration on edge computing.
Although stochastic computing was a historical failure, it may still remain relevant for solving certain problems.
With stochastic computing, we can AND together any number of bits and the expected value will always be correct.
(However, with a small number of samples the variance will render the actual result highly inaccurate).
Moreover, the underlying operations in a digital multiplier are full adders, whereas a stochastic computer only requires an AND gate.
Additionally, stochastic computing is robust against noise; if a few bits in a stream are flipped, those errors will have no significant impact on the solution.
Furthermore, stochastic computing elements can tolerate skew in the arrival time of the inputs.
[14] Finally, stochastic computing provides an estimate of the solution that grows more accurate as we extend the bit stream.
When we examine a random bit stream and try to reconstruct the underlying value, the effective precision can be measured by the variance of our sample.
In certain applications, however, the progressive precision property of stochastic computing can be exploited to compensate this exponential loss.
Second, stochastic computing requires a method of generating random biased bit streams.
Unfortunately, generating (pseudo-)random bits is fairly costly (compared to the expense of, e.g., a full adder).
Third, the analysis of stochastic computing assumes that the bit streams are independent (uncorrelated).
Systems of stochastic processors are prone to latching, where feedback between different components can achieve a deadlocked state.
[16] A great deal of effort must be spent decorrelating the system to attempt to remediate latching.
Fourth, although some digital functions have very simple stochastic counterparts (such as the translation between multiplication and the AND gate), many do not.
In 2003, researchers realized that these two operations could be modeled very simply with stochastic computing.
[17] Moreover, since the belief propagation algorithm is iterative, stochastic computing provides partial solutions that may lead to faster convergence.
[18] The proponents of these methods argue that the performance of stochastic decoding is competitive with digital alternatives.
To produce completely accurate result with these methods, the operation must run for the product of the length of input bit-streams.
Bundle Processing involves sending a fixed number of bits instead of a stream.
Burst Processing encodes a number by a higher base increasing stream.
For instance, we would encode 4.3 with ten decimal digits as since the average value of the preceding stream is 4.3.
