Design of Accurate Stochastic Number Generators with Noisy Emerging
Devices for Stochastic Computing
Meng Yang
1
, John P. Hayes
2
, Deliang Fan
3
, and Weikang Qian
4
1,4
University of Michigan-Shanghai Jiao Tong University Joint Institute, Shanghai Jiao Tong University, Shanghai, China
2
Department of Electrical Engineering and Computer Science, University of Michigan, Ann Arbor, U.S.A.
3
Department of Electrical and Computer Engineering, University of Central Florida, Orlando, U.S.A.
Email: {
1
yangm.meng,
4
qianwk}@sjtu.edu.cn,
2
jhayes@eecs.umich.edu,
3
dfan@ucf.edu
Abstract—Stochastic computing (SC) is an unconventional com-
puting paradigm that operates on stochastic bit streams. It has
gained attention recently because of the very low area and power
needs of its computing core. SC relies on stochastic number gener-
ators (SNGs) to map input binary numbers to stochastic bit
streams. A conventional SNG comprises a random number source
(RNS), typically an LFSR, and a comparator. It needs far more
area and power than the SC core, offsetting the latter’s main ad-
vantages. To mitigate this problem, SNGs employing emerging na-
noscale devices such as memristors and spintronic devices have
been proposed. However, these devices tend to have large errors
in their output probabilities due to unpredictable variations in
their fabrication processes and noise in their control signals. We
present a novel method of exploiting such devices to design a
highly accurate SNG. It is built around an RNS that generates uni-
formly distributed random numbers under ideal (nominal) condi-
tions. It also has a novel error-cancelling probability conversion
circuit (ECPCC) that guarantees very high accuracy in the output
probability under realistic conditions when the RNS is subject to
errors. An ECPCC can also be used to generate maximally corre-
lated stochastic streams, a useful property for some applications.
I. I
NTRODUCTION
Stochastic computing (SC) was introduced in 1960s as an
unconventional computing paradigm [1]. Its main difference from
traditional “binary” computing is that it operates on stochastic bit
streams that encode data values as the probabilities of 1’s occurring in
the bit streams. For example, the bit stream “01001100” represents 3/8.
Due to this uniformly weighted encoding, SC is very tolerant of bit-flip
errors. Moreover, its probabilistic nature allows very simple circuits to
realize complex arithmetic operations. A notable example is multipli-
cation, which can be realized by an AND gate, as shown in Fig. 1(a).
Arithmetic circuits like this with stochastic bit streams as inputs and
outputs are referred to here as the SC core. Because of the core’s low
area and power requirements, SC has been applied successfully in sev-
eral application domains, including image processing [5], low-density
parity-check (LDPC) decoding [2], and artificial neural networks [4].
SC relies on stochastic number generators (SNGs) to generate input
stochastic bit streams of the desired probabilities. A widely used SNG
is composed of a random number source (RNS) and a comparator, as
shown in Fig. 2(a). (More details will be given in Section II.) This SNG
has a linear feedback shift register (LFSR) as its RNS, and usually con-
sumes far more area and power than the SC core. Furthermore, to guar-
Fig. 1. Examples of stochastic computing elements: (a) An AND gate used to
multiply two numbers encoded by stochastic bit streams; (b) A 2-to-1 multi-
plexer (MUX) implementing scaled addition.
LFSR
Comparator
4
0 1 0 ...
c/2
4
4
r
c
RNS
c
3
c
0
c
2
c
1
Target
bits
r
1
c
1
2
2
Random
bit
sources
Target
bits
r
c
r
0
c
0
RNS
<
<
(a) (b)
Fig. 2. Stochastic number generators composed of an RNS and a comparator:
(a) the RNS is an LFSR; (b) the RNS is composed of =2 random bit sources.
antee the SC core’s correct functionality, its input bit streams should be
mutually independent or uncorrelated, which means the number of
SNGs must equal the number of inputs to the core.
To reduce the area and power needs of the SNGs in a stochastic cir-
cuit, several solutions have been proposed. One proposal is to share a
single LFSR among multiple SNGs. For example, circular shifting of
the output bits of the LFSR is suggested in [6] to produce stochastic bit
streams with low correlation. In [7], the insertion of delay elements into
the circuit is proposed to decorrelate the stochastic bit streams. How-
ever, these solutions cannot guarantee perfect mutual independence
among the input streams; hence, errors may remain in the final result.
A deterministic method for SC is proposed in [8] to reduce the cost of
generating input streams. However, it is only applicable when the input
precision is low.
A very different approach is to exploit the special properties of
emerging technologies such as memristors [9][10] and spintronic de-
vices [13][14]. These nanoscale devices have two different stable states
that can be mapped into binary values. For example, a memristor has
high- and low-impedance states, which can be switched by applying a
programming pulse. Recent studies showed that the state switching can
be random and the switching probability can be controlled by an input
signal [9]. For example, the switching probability of a memristor is
(
)
=1−
/
,
(1)
where is the width of the programming pulse and is a constant de-
termined by the device itself and the amplitude of the programming
pulse. Therefore, by changing the value of , a stochastic bit stream of
arbitrary probability can be generated. Previous studies show that SNGs
based on these emerging devices have much smaller area and power
consumption than conventional CMOS-based SNGs. For example, the
power needed by a memristor-based design can be 16x lower than that
of a CMOS SNG [9], while a design based on spintronic devices can
achieve a 7x power reduction [13].
However, these emerging devices are nanoscale and subject to noise
due to manufacturing parameter variations and run-time signal varia-
tions. They may also be subject to quantum-mechanical effects like tun-
neling that are inherently probabilistic [11]. In the memristor case, for
example, Eq. (1) implies that its switching probability is vulnerable to
noise in the programming pulse [12] and variations in its device param-
eters. Consequently, the bit streams produced by conventional SNG de-
signs that employ such devices may have probability values that deviate
significantly from the expected ones. To take advantage of these noisy