Stochastic computing

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.

History

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. 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 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.

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] [10] Somewhat recently, interest has turned towards stochastic decoding, which applies stochastic computing to the decoding of error correcting codes.[11] More recently, stochastic circuits have been successfully used in image processing tasks such as edge detection [12] and image thresholding.[13]

Stochastic decoding

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.[17] 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. [18] The proponents of these methods argue that the performance of stochastic decoding is competitive with digital alternatives.

Deterministic Methods to Stochastic Computing

Deterministic methods of SC has been developed to perform completely accurate computation with SC circuits.[19] The essential principle of these methods is that every bit of one bit-streams interacts with every bit of the other bit-streams exactly once. To produce completely accurate result with these methods, the operation must run for the product of the length of input bit-streams. Deterministic methods are developed based on unary bit-streams,[20][21] pseudo-random bit-streams,[22] and low-discrepancy bit-streams.[23]

References

  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-0-393-05169-8.
  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
  4. ^Poppelbaum, W.; Afuso, C.; Esch, J. (1967). “Stochastic computing elements and systems”. Afips FJCC. 31: 635–644. doi:10.1145/1465611.1465696. ISBN 9781450378963. S2CID 8504153.
  5. ^Gaines, B. (1967). “Stochastic Computing”. Afips SJCC. 30: 149–156. doi:10.1145/1465482.1465505. ISBN 9781450378956. S2CID 832296.
  6. ^Mars, P.; Poppelbaum, W. (1981). Stochastic and deterministic averaging processors. P. Peregrinus. ISBN 978-0-906048-44-3.
  7. ^Esch, John W. (1969). RASCEL, a programmable analog computer based on a regular array of stochastic computing element logic (PhD). University of Illinois, Urbana, Illinois. AAI700084.
  8. ^Proceedings of the first International Symposium on Stochastic Computing and its Applications. Toulouse, France. 1978. OCLC 499229066.
  9. ^Gaines, B. R. (2013) [1969]. “Stochastic Computing Systems”. In Tou, Julius (ed.). Advances in Information Systems Science. 2. Springer. ISBN 9781489958433.
  10. ^van Daalen, M.; Jeavons, P.; Shawe-Taylor, J. (1993). “A stochastic neural architecture that exploits dynamically reconfigurable FPGAs”. FPGAs for Custom Computing Machines, Proceedings IEEE, NAPA. pp. 202–211. doi:10.1109/FPGA.1993.279462. ISBN 0-8186-3890-7.
  11. ^Gaudet, Vincent; Rapley, Anthony (February 2003). “Iterative decoding using stochastic computation”. Electronics Letters. 39(3): 299–301. Bibcode:2003ElL….39..299G. doi:10.1049/el:20030217.
  12. ^Alaghi, A.; Li, C.; Hayes, J. P. (2013). “Stochastic circuits for real-time image-processing applications”. Proceedings of the 50th Annual Design Automation Conference on – DAC ’13. p. 1. doi:10.1145/2463209.2488901. ISBN 9781450320719. S2CID 18174415.
  13. ^Najafi, M. H.; Salehi, M. E. (2016). “A Fast Fault-Tolerant Architecture for Sauvola Local Image Thresholding Algorithm Using Stochastic Computing”. IEEE Transactions on Very Large Scale Integration (VLSI) Systems – TVLSI ’16. IEEE Transactions on Very Large Scale Integration (VLSI) Systems. 24. pp. 808–812. doi:10.1109/TVLSI.2015.2415932. S2CID 6591306.

Ofer Abarbanel – Executive Profile

Ofer Abarbanel online library

Ofer Abarbanel online library

Ofer Abarbanel online library

Ofer Abarbanel online library