Armin Alaghi
John P. Hayes
Skip Abstract Section
Abstract
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.
- Akgul, B. E. S., Chakrapani, L. N, Korkmaz, P., and Palem, K. V. 2006. Probabilistic CMOS technology: A survey and future directions. In Proceedings of the IFIP Conference on VLSI. 1--6.Google Scholar
- Aliee, H. and Zarandi, H. R. 2011. Fault tree analysis using stochastic logic: A reliable and high speed computing. In Proceedings of the Reliability and Maintainability Symposium. 1--6.Google Scholar
- Alt, R., Lamotte, J.-L., and Markov, S. 2006. On the solution to numerical problems using stochastic arithmetic. In Proceedings of the Symposium on Scientific Computing, Computer Arithmetic and Validated Numerics. 6.Google Scholar
- Brown, B. D. and Card, H. C. 2001. Stochastic neural computation I: Computational elements. IEEE Trans. Comput. 50, 891--905. Google ScholarDigital Library
- Chen, H. and Han, J. 2010. Stochastic computational models for accurate reliability evaluation of logic circuits. In Proceedings of the Great Lakes Symposium on VLSI. 61--66. Google ScholarDigital Library
- Dickson, J. A., McLeod, R. D., and Card, H. C. 1993. Stochastic arithmetic implementations of neural networks with in situ learning. In Proceedings of the International Conference on Neural Networks. 711--716.Google Scholar
- Dinu, A., Cirstea, M. N., and McCormick, M. 2002. Stochastic implementation of motor controllers. In Proceedings of the IEEE Symposium on Industrial Electronics. 639--644.Google ScholarCross Ref
- ETSI. 2005. European telecommunications standards Institute Standard TR 102 376 V1.1.1: Digital video broadcasting (DVB). User guidelines for the second generation system for broadcasting, interactive services, news gathering and other broadband satellite applications. http://www.etsi.org.Google Scholar
- Gaines, B. R. 1967. Stochastic computing. In Proceedings of the AFIPS Spring Joint Computer Conference. 149--156. Google ScholarDigital Library
- Gaines, B. R. 1969. Stochastic computing systems. Adv. Inform. Syst. Sci. 2, 37--172.Google ScholarCross Ref
- Gallager, R. G. 1962. Low-density parity-check codes. IRE Trans. Inform. Theory 8, 21--28.Google ScholarCross Ref
- Gaudet, V. C. and Rapley, A. C. 2003. Iterative decoding using stochastic computation. Electron. Lett. 39, 299--301.Google ScholarCross Ref
- Golomb, S. W. 1982. Shift Register Sequences (Rev. Ed.). Aegean Park Press, Laguna Hills, CA.Google Scholar
- Gross, W. J., Gaudet, V. C., and Milner, A. 2005. Stochastic implementation of LDPC decoders. In Proceedings of the Asilomar Conference on Signals, Systems and Computers. 713--717.Google Scholar
- Gupta, P. K. and Kumaresan, R. 1988. Binary multiplication with PN sequences. IEEE Trans. Acoustics Speech Signal Process. 36, 603--606.Google ScholarCross Ref
- Hammadou, T., Nilson, M., Bermak, A., and Ogunbona, P. 2003. A 96 × 64 intelligent digital pixel array with extended binary stochastic arithmetic. In Proceedings of the International Symposium on Circuits and Systems. IV-772--IV-775.Google Scholar
- IEEE. 2009. IEEE Standards Association Standard. IEEE. 802.11n for information technology-telecommunications and information exchange between systems-local and metropolitan area networks. http://standards.ieee.org.Google Scholar
- Jeavons, P., Cohen, D. A., and Shawe-Taylor, J. 1994. Generating binary sequences for stochastic computing. IEEE Trans. Inform. Theory 40, 716--720. Google ScholarDigital Library
- Keane, J. F. and Atlas, L. E. 2001. Impulses and stochastic arithmetic for signal processing. In Proceedings of the International Conference on Acoustics, Speech and Signal Processing. 1257--1260. Google ScholarDigital Library
- Kim, Y-C. and Shanblatt, M. A. 1995. Architecture and statistical model of a pulse-mode digital multilayer neural network. IEEE Trans. Neural Netw. 6, 1109--1118. Google ScholarDigital Library
- Krishnaswamy, S., Markov, I. M., and Hayes, J. P. 2007. Tracking uncertainty with probabilistic logic circuit testing. IEEE Design Test Comput. 24, 312--321. Google ScholarDigital Library
- Kschischang, F. R., Frey, B. J., and Loeliger, H.-A. 2001. Factor graphs and the sum-product algorithm. IEEE Trans. Inform. Theory 47, 498--519. Google ScholarDigital Library
- Li, X., Qian, W., Riedel, M. D., Bazargan, K., and Lilja, D. J. 2009. A reconfigurable stochastic architecture for highly reliable computing. In Proceedings of the Great Lakes Symposium on VLSI. 315--320. Google ScholarDigital Library
- Lorentz, G. G. 1986. Bernstein Polynomials 2nd Ed., Chelsea Publishing Co., New York, NY.Google Scholar
- MacKay D. J. C. and Neal, R. M. 1996. Near Shannon limit performance of low density parity check codes. Electron. Lett. 32, 1645.Google ScholarCross Ref
- McClennan, B. J. 2009. Analog computation. In Encyclopedia of Complexity and System Science, Springer. 271--294.Google Scholar
- Mansinghka, V. 2009. Natively probabilistic computation. Ph.D. dissertation, Massachusetts Institute of Technology, Department of Brain and Cognitive Sciences, Cambridge, MA. Google ScholarDigital Library
- Marin, S. L. T., Reboul, J. M. Q., and Franquelo, L. G. 2002. Digital stochastic realization of complex analog controllers. IEEE Trans. Industrial Electron. 49, 1101--1109.Google ScholarCross Ref
- Mars, P. and McLean, H. R. 1976 High-speed matrix inversion by stochastic computer. Electron. Lett. 12, 457--459.Google ScholarCross Ref
- Naderi, A., Mannor, S., Sawan, M., and Gross, W. J. 2011. Delayed stochastic decoding of LDPC codes. IEEE Trans. Signal Process. To appear. Google ScholarDigital Library
- Nepal, K., Bahar, R. I., Mundy, J., Patterson, W. R., and Zaslavsky, A. 2005. Designing logic circuits for probabilistic computation in the presence of noise. In Proceedings of the Design Automation Conference. 485--490. Google ScholarDigital Library
- Paler, A., Alaghi, A., Polian, I., and Hayes, J. P. 2011. Tomographic testing and validation of probabilistic circuits. In Proceedings of the European Test Symposium. 63--68. Google ScholarDigital Library
- Pejic, D. and Vujicic, V. 1999. Accuracy limit of high precision stochastic watt-hour meter. IEEE Trans. Instrum. Meas. 49, 617--620.Google ScholarCross Ref
- Petriu, E. M., Zhao, L., Das, S. R., Groza, V. Z., and Cornell, A. 2003. Instrumentation applications of multibit random-data representation. IEEE Trans. Instrum. Meas. 52, 175--181.Google ScholarCross Ref
- Poppelbaum, W. J. 1976. Statistical processors. Adv. Computers 14, 187--230.Google ScholarCross Ref
- Poppelbaum, W. J., Afuso, C., and Esch, J. W. 1967. Stochastic computing elements and systems. In Proceedings of the AFIPS Fall Joint Computer Conference. 635--644. Google ScholarDigital Library
- Qian, W. and Riedel, M. D. 2008. The synthesis of robust polynomial arithmetic with stochastic logic. In Proceedings of the Design Automation Conference. 648--653. Google ScholarDigital Library
- Qian, W., Li, X., Riedel, M. D., Bazargan, K., and Lilja, D. J. 2011. An architecture for fault-tolerant computation with stochastic logic. IEEE Trans. Comput. 60, 93--105. Google ScholarDigital Library
- Quero, J. M., Toral, S. L., Carrasco, J. M., Ortega, J. G., and Franquelo, L. G. 1999. Continuous time controllers using digital programmable devices. In Proceedings of the 25th IECON, 1, 210--215.Google Scholar
- RAND Corp. 1955. A Million Random Digits with 100,000 Normal Deviates. Free Press, Glencoe, IL.Google Scholar
- Ribeiro, S. T. 1967. Random-pulse machines. IEEE Trans. Electron. Comput. 16, 261--276.Google ScholarCross Ref
- Shanbhag, N. R., Abdallah, R. A., Kumar, R., and Jones, D. L. 2010. Stochastic computation. In Proceedings of the Design Automation Conference. 859--864. Google ScholarDigital Library
- Singhee, A. and Rutenbar, R. A. 2009. Novel Algorithms for Fast Statistical Analysis of Scaled Circuits. Lecture Notes in Electrical Engineering, vol. 46, Springer.Google Scholar
- Tehrani, S. S., Naderi, A., Kamendje, G. A., Hemati, S., Mannor, S., and Gross, W. J. 2010. Majority-based tracking forecast memories for stochastic LDPC decoding. IEEE Trans. Signal Processing 58, 4883--4896. Google ScholarDigital Library
- Toral, S. L., Quero, J. M., and Franquelo, L. G. 1999. Stochastic pulse coded arithmetic. In Proceedings of ISCAS 1, 599--602.Google Scholar
- Van Daalen, M., Jeavons, P., Shawe-Taylor, J., and Cohen, D. 1993. Device for generating binary sequences for stochastic computing. Electron. Lett. 29, 80.Google ScholarCross Ref
- Vigoda, B. 2003. Analog logic: Continuous-time analog circuits for statistical signal processing, Ph.D. dissertation, Massachusetts Institute of Technology, Cambridge, MA. Google ScholarDigital Library
- von Neumann, J. 1956. Probabilistic logics and the synthesis of reliable organisms from unreliable components. In Automata Studies, Princeton University Press, 43--98.Google Scholar
- Zelkin, B. 2004. Arithmetic unit using stochastic data processing. U.S. Patent 6,745,219 B1.Google Scholar
- Zhang, D. and Li, H. 2008. A stochastic-based FPGA controller for an induction motor drive with integrated neural network algorithms. IEEE Trans. Industrial Electron. 55, 551--561.Google ScholarCross Ref
- Zhang, Z., Anantharam, V., Wainwright, M. J., and Nikolic, B. 2010. An efficient 10GBASE-T Ethernet LDPC decoder design with low error floors. IEEE J. Solid-State Circuits 45, 843--855.Google ScholarCross Ref
Index Terms
- Survey of Stochastic Computing
Recommendations
Linear-Phase Lattice FIR Digital Filter Architectures Using Stochastic Logic
This paper presents novel architectures for linear-phase FIR digital filters using stochastic computing. Stochastic computing systems require fewer logic gates and are inherently fault-tolerant. Thus, these structures are well suited for nanoscale CMOS ...
Computing Polynomials Using Unipolar Stochastic Logic
Special Issue on Hardware and Algorithms for Learning On-a-chip and Special Issue on Alternative Computing SystemsThis article addresses subtraction and polynomial computations using unipolar stochastic logic. Stochastic computing requires simple logic gates, and stochastic logic--based circuits are inherently fault tolerant. Thus, these structures are well suited ...
Reversible stochastic computing in ratioed, unsigned extended and signed extended stochastic logic formats
AbstractStochastic computing is a promising technique for addressing the problems of increase in leakage current, increased sensitivity to soft errors etc. in today's semiconductor industry. Stochastic computing has been presented in open ...
Comments