Toward Energy-Efficient, Dynamic Stochastic Computing

• Author / Creator

  Liu, Siting

• Stochastic computing (SC) is an alternative computing paradigm originally proposed to reduce the size of digital arithmetic circuits. In SC, a number is encoded and represented by a stream of random bits or stochastic sequence (e.g., a Bernoulli sequence). Computations
  can be performed by bit-wise operations on the bit streams. Due to the long sequences required for accurate computation, however, the long latency and low energy efficiency present significant challenges for SC.
  In this work, quasirandom numbers are used to generate the sequences for energy-efficient implementation of SC circuits. Specifically, the quasirandom numbers that lead
  to the Sobol sequence are introduced for the first time for use in SC. Compared to the use of pseudorandom numbers generated by a linear-feedback shift register (LFSR), using
  Sobol sequences improves the computation accuracy of a stochastic circuit with a reduced sequence length. A hardware Sobol sequence generator is proposed; its parallelization is implemented with a few extra XOR gates by exploiting the inherent parallelism of the Sobol sequence generation algorithm. In terms of energy consumption, throughput per area and computation time, the circuits that use parallel Sobol sequence generators outperform conventional SC circuits using LFSRs.
  To further improve the energy efficiency, dynamic stochastic computing (DSC) is proposed. In DSC, a digital signal is encoded by a stochastic sequence with consistently varying probabilities. This sequence is referred to as a dynamic stochastic sequence
  (DSS). DSC is then used in digital signal processing (DSP), hardware ordinary differential equation (ODE) and partial differential equation (PDE) solvers and stochastic
  computing-based gradient descent circuits (SC-GDCs).
  In these applications, each bit in the DSS is used to encode one sample from a signal or function. For DSP, the definition of a DSS is provided; the generation and the
  reconstruction of a DSS are explicitly discussed and analyzed to obtain the optimal signal generation and reconstruction parameters. Experimental results show that an oversampling is required for DSP applications as in a D − S modulator to produce relatively high-quality results. Different DSC circuits are then devised to implement frequency mixing, function estimation, an infinite impulse response (IIR) filter and numerical integration. The simulation results show that up to 60% time and energy savings are achieved using DSC compared to a fixed-point binary implementation with a
  similar accuracy for function estimation when processing the same oversampled signals. However, a fixed-width binary circuit still has a higher energy efficiency and speed when processing signals sampled at the Nyquist rate compared to a DSC-based frequency mixer using oversampled signals at a similar accuracy. Using Sobol sequences to generate a DSS encoding a continuous signal improves the accuracy of the computed result compared to the use of conventional LFSR-generated sequences.
  In the proposed stochastic ODE/PDE solvers using DSS’s, we showed that a stochastic integrator produces an unbiased estimate of the Euler solution. Different stochastic ODE solvers are designed for a nonhomogeneous ODE, a set of ODEs and a second-order
  ODE. Moreover, an array of stochastic Laplacian circuits is proposed to solve a larger-scale problem, i.e., a steady-state heat equation. Each stochastic Laplacian circuit is
  used to produce the numerical solution for one discretized point in a squared area, as described by one differential equation in the heat equation. Additionally, three error
  reduction schemes are considered to reduce the variation in the computed result, including the use of Sobol sequences. The simulation results show that these designs achieve a higher energy and hardware efficiency than their fixed-point binary counterparts with a limited loss of accuracy.
  In the SC-GDC, the DSS is used to encode the gradient information of a cost function in a machine learning model. A gradient descent algorithm is then performed by using
  stochastic integrators to accumulate the gradients. Optimal weights or parameters are then obtained for a particular machine learning model. An array of SC-GDCs is used to update the weights for an adaptive filter, softmax regression and to train a fully connected neural network. The gradient information is encoded by the DSS’s, which are then accumulated and converted to a fixed-point number by a stochastic integrator. The SC-GDC achieves
  a higher or similar accuracy and a significant improvement in hardware efficiency over a conventional SC design and a 16-bit fixed-point implementation.

• Subjects / Keywords

  • Stochastic Computing

• Graduation date

  Fall 2019

• Type of Item

  Thesis

• Degree

  Doctor of Philosophy

• DOI

  https://doi.org/10.7939/r3-p2vw-yy63

• License

  Permission is hereby granted to the University of Alberta Libraries to reproduce single copies of this thesis and to lend or sell such copies for private, scholarly or scientific research purposes only. Where the thesis is converted to, or otherwise made available in digital form, the University of Alberta will advise potential users of the thesis of these terms. The author reserves all other publication and other rights in association with the copyright in the thesis and, except as herein before provided, neither the thesis nor any substantial portion thereof may be printed or otherwise reproduced in any material form whatsoever without the author's prior written permission.