Stochastic computing is a collection of techniques that represent continuous values by streams of bits. Complex computations can then be computed by simple bit-wise operations on the streams.

Motivation and a Simple Example

edit

Suppose we are given  , and we wish to compute  . Stochastic computing performs this operation using probability instead of arithmetic.

Specifically, suppose that we have two random, independent bit streams (i.e. Bernoulli processes), where the probability of a one in the first stream is  , and the probability in the second stream is  . We can take the logical AND of the two streams

  1 0 1 1 0 1 ...
  1 1 0 1 1 0 ...
  1 0 0 1 0 0 ...

The the probability of a one in the output stream is  . By observing enough output bits and measuring the frequency of ones, we can estimate   to arbitrary accuracy.

The operation above converts a fairly complicated computation (multiplication of   and  ) into a series of very simple operations (evaluation of  ) on random bits.

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   and   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 interpretion of calculations in probabilistic terms, which are then evaluated with a Gibbs sampler.

History

edit

Stochastic computing was first described (in a very rough form) by a classic paper by John von Neumann in 1953.[1] However, the theory was not fully developed until the 1960's,[2] [3] mostly through a series of simultaneous and parallel efforts in the US[4] and the UK[5]. By the late 1960's, attention turned to the design of special-purpose hardware to perform stochastic computation. A host[6] of these machines were constructed between 1969 and 1974; RASCEL[7] is pictured in this article.

Despite the intense interest in the 1960's and 1970's, 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.

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.[9] More recently, interest has turned towards stochastic decoding, which applies stochastic computing to the decoding of error correcting codes.

Strengths and Weaknesses

edit

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

edit

Suppose we wish to multiply two numbers each with   bits of precision. Using the typical long multiplication method, we need to perform   operations. 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, a digital multiplier would naively require   input wires, whereas a stochastic multiplier would only require 2 input wires. (If the digital multiplier serialized its output, however, it would also require only 2 input wires.)

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.

Finally, stochastic computing provides an estimate of the solution that grows more accurate as we extend the bit stream. In particular, it provides a rough estimate very rapidly. In some iterative systems these partial solutions can provide faster feedback than through traditional computing methods, leading to faster convergence.

Weaknesses

edit

Stochastic computing is, by its very nature, random. 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 the example above, the digital multiplier computes a number to   bits of accuracy, so the precision is  . If we are using a random bit stream to estimate a number and want the standard deviation of our estimate of the solution to be at least  , we would need   samples. This represents an exponential increase in work.

Second, stochastic computing requires a method of generating random biased bit streams. In practice, these streams are generated with pseudo-random number generators. Unfortunately, generating (pseudo-)random bits is fairly costly (compared to the expense of, e.g., a full adder). Therefore, the gate-level advantage of stochastic computing is typically lost.

Third, the analysis of stochastic computing assumes that the bit streams are independent (uncorrelated). If this assumption does not hold, stochastic computing can fail dramatically. For instance, if we try to compute   by multiplying a bit stream for   by itself, the process fails: since  , the stochastic computation would yield  , which is not generally true (unless  0 or 1). In systems with feedback, the problem of decorrelation can manifest in more complicated ways. Systems of stochastic processors are prone to latching, where feedback between different components can achieve a deadlocked state.[10] 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. Trying to express these functions stochastically may cause various pathologies. For instance, stochastic decoding requires the computation of the function  . There is no single bit operation that can compute this function; the usual solution involves producing correlated output bits, which, as we have seen above, can cause a host of problems. Still other functions (such as the averaging operator  ) require stream decimation. Since decimation discards information, it leads to the problem of attenuation.

Stochastic Decoding

edit

Although stochastic computing has a number of defects when considered as a method of general computation, there are certain applications that highlight its strengths. One notable case occurs in the decoding of certain error correcting codes.

In developments unrelated to stochastic computing, highly effective methods of decoding LDPC codes using the belief propagation algorithm were developed. Belief propagation in this context involves iteratively reestimating certain parameters using two basic operations (essentially, a probabilistic XOR operation and an averaging operation).

In 2003, researchers realized that these two operations could be modeled very simply with stochastic computing.[11] Moreover, since the belief propagation algorithm is iterative, stochastic computing provides partial solutions that may lead to faster convergence. Hardware implementations of stochastic decoders have been built on FPGAs. [12] The proponents of these methods argue that the performance of stochastic decoding is competitive with digital alternatives.

Variants of Stochastic Computing

edit

There are a number of variants of the basic stochastic computing paradigm. Further information can be found in the referenced book by Mars and Poppelbaum.

Bundle Processing involves sending a fixed number of bits instead of a stream. One of the advantages of this approach is that the precision is improved. To see why, suppose we transmit   bits. In regular stochastic computing, we can represent a precision of roughly   different values, because of the variance of the estimate. In bundle processing, we can represent a precision of  . However, bundle processing retains the same robustness to error of regular stochastic processing.

Ergodic Processing involves sending a stream of bundles, which captures the benefits of regular stochastic and bundle processing.

Burst Processing encodes a number by a higher base increasing stream. For instance, we would encode 4.3 with ten decimal digits as

4445555555

since the average value of the preceding stream is 4.3. This representation offers various advantages: there is no randomization since the numbers appear in increasing order, so the PRNG issues are avoided, but many of the advantages of stochastic computing are retained (such as partial estimates of the solution). Additionally, it retains the linear precision of bundle and ergodic processing.

References

edit
  1. ^ von Neumann, J. (1963). "Probabilistic logics and the synthesis of reliable organisms from unreliable components". The Collected Works of John von Neumann. Macmillan. ISBN 978-0393051698.
  2. ^ Petrovic, R.; Siljak, D. (1962). "Multiplication by means of coincidence". ACTES Proc. of 3rd Int. Analog Comp. Meeting.
  3. ^ Afuso, C. (1964), Quart. Tech. Prog. Rept., Department of Computer Science, University of Illinois, Urbana, Illinois{{citation}}: CS1 maint: location missing publisher (link)
  4. ^ Poppelbaum, W.; Afuso, C.; Esch, J. (1967), "Stochastic computing elements and systems", Afips FJCC, 31: 635–644
  5. ^ Gaines, B. (1967), "Stochastic Computing", Afips SJCC, 30: 149–156
  6. ^ Mars, P.; Poppelbaum, W. (1981), Stochastic and deterministic averaging processors
  7. ^ Esch, J. (1969), RASCEL, a programmable analog computer based on a regular array of stochastic computing element logic, University of Illinois, Urbana, Illinois{{citation}}: CS1 maint: location missing publisher (link)
  8. ^ Proceedings of the first International Symposium on Stochastic Computing and its Applications, Toulouse, France, 1978{{citation}}: CS1 maint: location missing publisher (link)
  9. ^ Gaines, B. R. (1969), Stochastic Computing Systems, vol. 2 {{citation}}: Unknown parameter |book-title= ignored (help)
  10. ^ Winstead, C.; Rapley, A.; Gaudet, V.; Schlegel, C. (September 2005). "Stochastic iterative decoders". IEEE International Symposium on Information Theory. Adelaide Australia.{{cite journal}}: CS1 maint: date and year (link)
  11. ^ Gaudet, Vincent; Rapley, Anthony (February 2003). "Iterative decoding using stochastic computation". Electronic Letters. 39 (3): 299–301. doi:10.1049/el:20030217.{{cite journal}}: CS1 maint: date and year (link)
  12. ^ Gross, W.; Gaudet, V.; Milner, A. (2006). "Stochastic implementation of LDPC decoders". Conference Record of the Thirty-Ninth Asilomar Conference on Signals, Systems and Computers.