UNIVERSITY OF WISCONSIN–MADISON

End-to-End Stochastic
ComputingMikko Lipasti and Carly Schulz
February 4, 2017

STOCHASTIC COMPUTING / EXECUTIVE SUMMARY

Executive Summary• In systems with sigma-delta modulated sensors, increase
performance by operating directly on data instead of converting(End-to-end)• Stochastic computing has advantages in end-to-end systems while ithas challenges that prevent it from being used in other applications• We implement a prototype audio mixer system2

STOCHASTIC COMPUTING / BACKGROUNDBackground• Stochastic representation• Represent the number, n, you are trying to send bysending a 1 with probability n for a set bit stream• 0011011001 would be a representation of 5
• Probabilistic Calculus introduced in 1960s by Von Neumann• Trivial implementation of multiplication using AND gates• Bernstein polynomials – any finite interval function thatmaps to another finite interval• Can implement the polynomials with a series of adders
and multiplexers

3

STOCHASTIC COMPUTING / BACKGROUND

Advantages of StochasticComputing• Error Tolerant• Soft errors (bit flips) are tolerated well, no bit is more
important than another• Smaller circuit size
• Simple logic makes the gate cost low• Shorter critical paths• Simpler logic allows higher clock frequencies

4STOCHASTIC COMPUTING / BACKGROUND

Traditional Challenges• Representation costs in terms of bits due to precision requirements• Generating the stochastic numbers has high energy costs• Possible increases in length of computation due to length of bit
stream, gate invocations are higher• Function mapping errors because the Bernstein Polynomial is anapproximation

5

STOCHASTIC COMPUTING / IMPLEMENTATIONImplementation
Audio system using pulsedensity modulatedrepresentation.
Altera Cyclone IV FPGA

6

STOCHASTIC COMPUTING / IMPLEMENTATION

Pulse Density Modulated(PDM) Signals
Sample PDM encoded sinewaves.
Blue represents a 1 while thewhite represents a 0.

Images from https://en.wikipedia.org/wiki/File:Pulse-density_modulation_1_period.gif
https://en.wikipedia.org/wiki/File:Pulse-density_modulation_2_periods.gif

7

STOCHASTIC COMPUTING / IMPLEMENTATION

Traditional Implementation Block
Diagram

PDM Signal PDM to PCM
converter

SystemComputations

PCM to PDM
converter8STOCHASTIC COMPUTING / IMPLEMENTATIONPDM Block Diagram

9

STOCHASTIC COMPUTING / IMPLEMENTATION

Prototype’s Advantages• Does not have any conversion costs• Simplified datapath• More energy efficient (estimated)

10

STOCHASTIC COMPUTING / EVALUATION

Evaluation
Synthesized PDM design on board and also created a pulsecode modulated (PCM) based design that is synthesizable on

the same board.

PCM Model• Downsample signal from 3 MHz to 24 KHz• Filtering is performed on the PCM data
• Converts back to PDM through sigma-delta modulation
11STOCHASTIC COMPUTING / EVALUATIONEvaluation• PDM to PCM conversion – Cascaded integrator-comb• Biquad filters – PDM integrates and delays through RAM for128 steps, PCM keeps conventional implementation• PCM to PDM conversion – 128x interpolation with 3stage

filter cascade of 3rd order CIC to a second order sigma-delta
modulator

12

STOCHASTIC COMPUTING / EVALUATION

Biquad Filter• In the PDM implementation,
there is a 128 bit buffer in thefilter to match the sampling rate

Image from: https://en.wikipedia.org/wiki/File:Biquad_filter_DF-I.svg

13

STOCHASTIC COMPUTING / EVALUATION

Area Comparison
Logic Elements
3000

Area Cost

2500
2000
PCM

1500

PDM

1000
500
0
PDMtoPCM

Biquads

PCMtoPDM

Misc
14

STOCHASTIC COMPUTING / EVALUATION

Area Comparison
RAM18000

16000

Area Cost

14000

12000
10000

PCM

8000

PDM

6000
4000
2000
0
Biquads

Misc
15

STOCHASTIC COMPUTING / CONCLUSIONConclusion
Stochastic computing can work well for single-bit stream inputs
and outputs

There are two other prototypes in our lab that this would makesense in practice:• Drone with an onboard homing program• Robotic arm using visual input to calculate
kinematics equations
16

STOCHASTIC COMPUTING / ACKOWLEDGEMENTS

Acknowledgements
Thanks to Eric Hoffman who designed and built the demo board
Supported in part by NSF grant CCF-1615014

17

Questions?
February 4, 2017