The Hypergeometric Distribution as a More Accurate Model for Stochastic Computing
Timothy J. Bakera and John P. Hayesb
Department of Electrical Engineering and Computer Science University of Michigan, Ann Arbor, 48109 USA
abakertim@umich.edu
bjhayes@umich.edu
ABSTRACT
A fundamental assumption in stochastic computing (SC) is that bit-streams are generally well-approximated by a Bernoulli process, i.e., a sequence of independent 0-1 choices. We show that this assumption is flawed in unexpected and significant ways for some bit-streams such as those produced by a typical LFSR-based stochastic number generator (SNG). In particular, the Bernoulli assumption leads to a surprising overestimation of output errors and how they vary with input changes. We then propose a more accurate model for such bit-streams based on the hypergeometric distribution and examine its implications for several SC applications. First, we explore the effect of correlation on a mux-based stochastic adder and show that, contrary to what was previously thought, it is not entirely correlation insensitive. Further, inspired by the hypergeometric model, we introduce a new mux tree adder that offers major area savings and accuracy improvement. The effectiveness of this study is validated on a large image processing circuit which achieves an accuracy improvement of 32%, combined with a reduction in overall circuit area.
Keywords: Approximate Computing, Stochastic Computing, Hypergeometric Distribution, Error Analysis
