TY - JOUR

T1 - Performing Stochastic Computation Deterministically

AU - Hassan Najafi, M.

AU - Jenson, Devon

AU - Lilja, David J.

AU - Riedel, Marc D.

PY - 2019/12

Y1 - 2019/12

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

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

KW - Deterministic computing

KW - fast-converging process

KW - low-discrepancy (LD) bit-streams

KW - pseudorandomized bit-stream

KW - stochastic computing

KW - unary bit-streams

UR - http://www.scopus.com/inward/record.url?scp=85075638174&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85075638174&partnerID=8YFLogxK

U2 - 10.1109/TVLSI.2019.2929354

DO - 10.1109/TVLSI.2019.2929354

M3 - Article

AN - SCOPUS:85075638174

VL - 27

SP - 2925

EP - 2938

JO - IEEE Transactions on Very Large Scale Integration (VLSI) Systems

JF - IEEE Transactions on Very Large Scale Integration (VLSI) Systems

SN - 1063-8210

IS - 12

M1 - 8793244

ER -