On the maximum function in stochastic computing

ABSTRACT

Stochastic circuits (SCs) offer significant area, power and energy benefits at the cost of computational inaccuracies. SCs have received particular attention recently in the context of neural networks (NNs). Many NNs use the maximum function, e.g., in the max-pooling layer of convolutional NNs. Currently, approximate workarounds are often employed for this function. We propose NMax, a new SC design for the maximum function that produces an exact result with latency similar to an approximate circuit. Furthermore, unlike most stochastic functions, NMax is correlation insensitive. We also observe that maximum calculations are subject to application-specific bias and analyze this bias.

References

1. Alaghi A. and J.P. Hayes. Exploiting correlation in stochastic circuit design. Proc. Intl. Conf. on Computer Design (ICCD), 39--46, 2013.
2. Alaghi A., C. Li and J.P. Hayes. Stochastic circuits for real-time image-processing applications. Proc. Design Automation Conf. (DAC), art. 136, 2013.
3. Alaghi A. and J.P. Hayes. STRAUSS: Spectral transfrom use in stochastic circuit synthesis. IEEE Trans. Computer-Aided Design, 34.11: 1770--1783, 2015.
4. Alaghi A. and J.P. Hayes. Survey of stochastic computing. ACM Trans. Embedded Comp. Syst., 12: art. 92, 2013.
5. Box G.E.P. and G. Jenkins. Time Series Analysis: Forecasting and Control, Holden-Day, 1976.
6. Brown B.D. and H.C. Card. Stochastic neural computation I: Computational elements. IEEE Trans. Computers, 50: 891--905, 2001.
7. Canals V., A. Morro, A. Oliver, M.L. Alomar and J.L. Rosselló. A new stochastic computing methodology for efficient neural network implementation. IEEE Trans. Neural Networks and Learning Systems 27.3: 551--564, 2016.
8. Chen T. and J.P. Hayes. Analyzing and controlling accuracy in stochastic circuits. Proc. Intl. Conf. on Computer Design (ICCD), 367--373, 2014.
9. Farmahini-Farahani A., H.J. Duwe, Michael J. Schulte and K. Compton. Modular design of high-throughput, low-latency sorting units. IEEE Trans. Computers, 62, 1389--1402, 2013.
10. Gaines B.R. Stochastic computing systems. Advances in Information Systems Science, 2: 37--172, 1969.
11. Gupta P.K. and R. Kumaresan, Binary multiplication with PN sequences, IEEE Trans. Acoustics, Speech and Signal Processing, 36, 603--606, 1988.
12. Ichihara H., T. Sugino, S. Ishii, T. Iwagaki and T. Inoue. Compact and accurate digital filters based on stochastic computing. IEEE Trans. Emerging Topics in Computing, 7, 31--43, 2019.
13. Li P. and D.J. Lilja. Using stochastic computing to implement digital image processing algorithms. Proc. Intl. Conf. on Computer Design (ICCD),: 154--161, 2011.
14. Naderi A., S. Mannor, M. Sawan and W.J. Gross. Delayed stochastic decoding of LDPC codes. IEEE Trans. Signal Processing, 59: 5617--5626, 2011.
15. Najafi M., D.J. Lilja, M.D. Riedel and K. Bazargan. Low-cost sorting network circuits using unary processing. IEEE Trans. VLSI Systems, 26, 1471--1480, 2018.
16. Neugebauer F., I. Polian and J.P. Hayes. S-Box-based random number generation for stochastic computing. Proc. Conf. on Digital System Design (DSD), 1--6, 2017.
17. Neugebauer F., I. Polian and J.P. Hayes. Framework for quantifying and managing accuracy in stochastic circuit design. Proc. DATE, 1--6, 2017.
18. Qian, W., X. Li, M.D. Riedel, K. Bazargan and D.J. Lilja. An architecture for fault-tolerant computation with stochastic logic. IEEE Trans. Computers 60, 93--105, 2011.
19. Ren A., Z. Li, C. Ding, Q. Qiu, Y. Wang, J. Li, X. Qian and B. Yuan. SC-DCNN: Highly scalable deep convolutional neural network using stochastic computing. Proc. ASPLOS, 405--418, 2017.
20. Stanford CS class, cs231n: Convolutional neural networks for visual recognition, 2016. http://cs231n.github.io/convolutional-networks/
21. Ting P-S and J.P. Hayes. Isolation-based decorrelation of stochastic circuits. Proc. Intl. Conf. on Computer Design (ICCD), 88--95, 2016.
22. van Daalen, M., P. Jeavons, J.Shawe-Taylor and Dave Cohen. Device for generating binary sequences for stochastic computing. Electronics Letters, 29: 80--81, 1993.
23. Wang R., J. Han, B.F. Cockburn and D.G. Elliot. Design, evaluation and fault-tolerance analysis of stochastic FIR filters. Microelectronics Reliability 57: 111--127, 2016.
24. Yu J., K. Kim, J. Lee and K. Choi. Accurate and efficient stochastic computing hardware for convolutional neural networks. Proc. Intl. Conf. on Computer Design (ICCD), 104--112, 2017.

Index Terms

• Hardware

  • Emerging technologies

    • Analysis and design of emerging devices and systems

      • Emerging architectures

• Mathematics of computing

  • Probability and statistics

    • Stochastic processes