Performing Stochastic Computation Deterministically

M. Hassan Najafi, Devon Jenson, David J. Lilja, Marc D. Riedel

Research output: Contribution to journalArticlepeer-review

23 Scopus citations


Stochastic logic performs computation on data represented by random bit-streams. The representation allows complex arithmetic to be performed with very simple logic, but it suffers from high latency and poor precision. Furthermore, the results are always somewhat inaccurate due to random fluctuations. In this paper, we show that randomness is not a requirement for this computational paradigm. If properly structured, the same arithmetical constructs can operate on deterministic bit-streams, with the data represented uniformly by the fraction of 1's versus 0's. This paper presents three approaches for the computation: relatively prime stream lengths, rotation, and clock division. Unlike stochastic methods, all three of our deterministic methods produce completely accurate results. The cost of generating the deterministic streams is a small fraction of the cost of generating streams from random/pseudorandom sources. Most importantly, the latency is reduced by a factor of (1/2n), where n is the equivalent number of bits of precision. When computing in unary, the bit-stream length increases with each level of logic. This is an inevitable consequence of the representation, but it can result in unmanageable bit-stream lengths. We discuss two methods for maintaining constant bit-streams lengths via approximations, based on low-discrepancy sequences. These methods provide the best accuracy and area × delay product. They are fast-converging and therefore offer progressive precision.

Original languageEnglish (US)
Article number8793244
Pages (from-to)2925-2938
Number of pages14
JournalIEEE Transactions on Very Large Scale Integration (VLSI) Systems
Issue number12
StatePublished - Dec 2019

Bibliographical note

Funding Information:
Manuscript received February 2, 2019; revised May 30, 2019; accepted June 26, 2019. Date of publication August 9, 2019; date of current version November 22, 2019. This work was supported in part by the National Science Foundation under Grant CCF-1408123 and Grant CCF-1438286. This paper was presented in part at the 35th IEEE/ACM International Conference on Computer Aided Design (ICCAD), Austin, TX, USA, November 7–10, 2016, in part at the 35th IEEE International Conference on Computer Design (ICCD), Boston, MA, USA, November 5–8, 2017, and in part at the 37th IEEE/ACM International Conference on Computer Aided Design (ICCAD), San Diego, CA, USA, November 5–8, 2018. (Corresponding author: M. Hassan Najafi.) M. Hassan Najafi is with the School of Computing and Informatics, University of Louisiana at Lafayette, Lafayette, LA 70504 USA (e-mail:

Publisher Copyright:
© 1993-2012 IEEE.


  • Deterministic computing
  • fast-converging process
  • low-discrepancy (LD) bit-streams
  • pseudorandomized bit-stream
  • stochastic computing
  • unary bit-streams


Dive into the research topics of 'Performing Stochastic Computation Deterministically'. Together they form a unique fingerprint.

Cite this