S. Rasoul Faraji
ABSTRACT
Stochastic computing has been used in recent years to create designs with significantly smaller area by harnessing unary encoding of data. However, the low area advantage comes at an exponential price in latency, making the area x delay cost unattractive. In this paper, we present a novel method which uses a hybrid binary / unary representation to perform computations. We first divide the input range into a few sub-regions, perform unary computations on each sub-region individually, and finally pack the outputs of all sub-regions back to compact binary. Moreover, we propose a synthesis methodology and a regression model to predict an optimal or sub-optimal design in the design space. The proposed method is especially well-suited to FPGAs due to the abundant availability of routing and flip-flop resources. To the best of our knowledge, we are the first to show a scalable method based on the principles of stochastic computing that can beat conventional binary in terms of a real cost, i.e., area x delay. Our method outperforms the binary and fully unary methods on a number of functions and on a common edge detection algorithm. In terms of area x delay cost, our cost is on average only 2.51% and 10.2% of the binary for 8- and 10-bit resolutions, respectively. These numbers are 2--3 orders of magnitude better than the results of traditional stochastic methods. Our method is not competitive with the binary method for high-resolution oscillating functions such as sin(15x).
- B. R. Gaines, Stochastic computing systems. in Advances in Information Systems Science, vol. 2, J. T. Tou, Ed. New York, NY, USA:Plenum, 1969, ch. 2, pp. 37172.Google Scholar
- B. Brown and H. Card, Stochastic neural computation I: Computational elements. IEEE Trans. Comput., vol. 50, no. 9, pp. 891--905, 2001. Google ScholarDigital Library
- W., X. Li, M. Riedel, K. Bazargan, and D. Lilja, An Architecture for Fault-Tolerant Computation with Stochastic Logic. IEEE Trans. Comput., Vol. 60, No. 1, pp. 93105, 2011. Google ScholarDigital Library
- M. H. Najafi and D. Lilja, High Quality Down-Sampling for Deterministic Approaches to Stochastic Computing. Emerging Topics in Computing, PP(99):11, 2018.Google Scholar
- W. Qian, M. Riedel, and I. Rosenberg, Uniform Approximation and Bernstein Polynomials with Coefficients in the Unit Interval. European Journal of Combinatorics, Vol. 32, No. 3, pp. 448463, 2011. Google ScholarDigital Library
- S. Rasoul Faraji, M. Hassan Najafi, Bingzhe Li, Kia Bazargan, and David J. Lilja, Energy-Efficient Convolutional Neural Networks with Deterministic Bit-Stream Processing. Design, Automation, and Test in Europe (DATE), March, 2019.Google Scholar
- Z. Wang, N. Saraf, K. Bazargan, and A. Scheel, Randomness meets feedback: Stochastic implementation of logistic map dynamical system. Design Automation Conference (DAC), June 2015. Google ScholarDigital Library
- D. Jenson and M. Riedel, A Deterministic Approach to Stochastic Computation. In Proceedings of the 35th International Conference on Computer-Aided Design (ICCAD), Nov, 2016. Google ScholarDigital Library
- S. Mohajer, Z. Wang, and K. Bazargan, Routing Magic: Performing Computations Using Routing Networks and Voting Logic on Unary Encoded Data. International Symposium on Field Programmable Gate Arrays (FPGA), pp. 77--86, 2018. Google ScholarDigital Library
- S. A. Salehi, Y. Liu, M. D. Riedel, and K. K. Parhi, Computing Polynomials with Positive Coecients using Stochastic Logic by Double-NAND Expansion. Proc. of the on Great Lakes Symposium on VLSI, pp. 471474, 2017. Google ScholarDigital Library
- P. Li, D. Lilja, W. Qian, M. D. Riedel, and K. Bazargan, Logical Computation on Stochastic Bit Streams with Linear Finite State Machines. IEEE Trans. Comput., Vol. 63, No. 6, pp. 14731485, June 2014. Google ScholarDigital Library
Recommendations
Approximate Hybrid Binary-Unary Computing with Applications in BERT Language Model and Image Processing
FPGA '23: Proceedings of the 2023 ACM/SIGDA International Symposium on Field Programmable Gate ArraysWe propose a novel method for approximate hardware implementation of univariate math functions with significantly fewer hardware resources compared to previous approaches. Examples of such functions include exp(x) and the activation function GELU(x), ...
Parallel Unary Computing Based on Function Derivatives
The binary number representation has dominated digital logic for decades due to its compact storage requirements. An alternative representation is the unary number system: We use N bits, from which the first M are 1 and the rest are 0 to represent the ...
Routing Magic: Performing Computations Using Routing Networks and Voting Logic on Unary Encoded Data
FPGA '18: Proceedings of the 2018 ACM/SIGDA International Symposium on Field-Programmable Gate ArraysThe binary number representation has dominated digital logic for decades due to its compact storage requirements. However, since the number system is positional, it needs to "unpack»» bits, perform computations, and repack the bits back to binary (\...
Comments