Tutors:

Pro. Olivier SENTIEYS

\label{pro.-olivier-sentieys}

September 10, 2014

\label{september-10-2014}
Contents
List of Figures
  1. General model of Stochastic computing system 2
  2. Digital to stochastic converter 2
  3. Stochastic sequence to binary number converter 3
  4. Error in SNG simulation and theoretical error versus the SN sequence length 6
  5. Max, Min, σ and mean of error in 1000 trials 7
  6. Influence of correlation on SC 7
  1. General model of LFSR used as PRNG 9
  2. Multiple LFSR configuration to generate m–bits at each clock cycle 10
  3. Leap–Ahead LFSR model 10
  4. A One–dimensional two–neighbor CA 11
  5. Behavior of the mixed rule CA in which each cell is considered including two virtual cells: Upper cell and Lower cell 13
  6. Histogram of three approaches of LFSR–based SNG with the expected probability 0.7 .14
  7. Empirical CDFs of three approaches of LFSR–based SNG corresponding to the expected probability 0.7 15
  8. Histogram of three implementation of CA–based SNG with the expected probability 0.715
  9. Histogram of three approaches of LFSR–based SNG with the expected probability 0.7 .16
  10. Empirical CDF of five SNGs relied on LFSR and CA 17
  11. Digital to stochastic converter 17
  12. Histogram and statistic parameters of the output when using Digital to Stochastic con- verter to generate the expected probability 0.625 18
  13. Binary to stochastic converter proposed using converters and NAND gates 19
  14. Histogram and statistic parameters of the output when using Variable probability gen- erator to generate the expected probability 0.625 20
  15. Multiplexer (MUX structure) includes two ANDs, one NOT and one OR gates 20
  16. 10–bit Weighted Binary SNG 21
  17. Apply 10–bit Weighted Binary SNG in stochastic computation 22
  18. Stochastic scale adder based on 10–bit Weighted Binary SNG in stochastic computation22
  19. State transition diagram of FSM based SNG 24
  20. State transition diagram of FSM based SNG after mapping transition probability into state of 3 − tuples 24
  21. Histogram and statistic parameters of the output value when using FSM to generate
the expected probability 0.7 25
  1. Generating stochastic constant using LFSR 26
  2. Emperical CDF function of SNGs using comparator and SNG based on Markov chain .26
  1. Two types of multiplier: (a) Unsigned multiplier and (b) Signed multiplier [6] 28
  2. Two types of multiplier: (a) Scaled addition and (b) Scaled subtraction in SC 29
  3. General diagram of linear state transition 29
  4. State transition diagram of Stochastic Tanh function 30
  5. State transition diagram of Stochastic Exponential function 30
  6. State transition diagram of Stochastic Absolute function 31
  7. State transition diagram of Stochastic Absolute Exponential function 31
  8. Simulation results of the Stochastic absolute function when consider different number
of states 32
  1. Simulation results of the Stochastic tanh function: (a) using 4–state FSM and (b) using 16–state FSM 33
  1. Implementation of M–order FIR filter using SC 35
  2. Input signal, frequency response and output signal in case of ideal filter 36
  3. The output in frequency domain after using FIR filter 36
  4. Implementation of Robert cross–gradient operators 37
  5. Design of Robert cross–gradient operators using SC 37
  6. Simulation results of edge detection based on Robert accross operator using: (a) con- ventional approach and (b) stochastic computing 38
  7. Implementation of Prewitt operators using a 3 × 3 2–D mask 39
  8. Design of Prewitt operators using SC 39
  9. Simulation results of edge detection based on Prewitt operator on (a) original image using: (b) conventional approach and stochastic computing of lengths (c) 2048 bits and
(d) 4096 bits 40
  1. Implementation of comparison network to get the median value 40
  2. Stochastic implementation of a node in the comparison network used for median filter .41
  3. Simulation results of noise reduction based on median filter using the conventional ap- proach and Stochastic computing with different lengths of bit sequence 42
  4. Soft error injection in the implementation of an 2–input operator 43
  5. Error comparison of the implemention of the multiplier between Stochastic and Con- ventional computing in case of having the injected soft error 43
  6. Evaluate the fault–tolerant capacity of SC (upper row) compared to conventional com- puting (lower row) in condition of injecting different soft error ratios 44
List of Tables
1.1 Three usual representation of a stochastic sequence of length N with N1 bits being logic
1 and N0 bits being logic 0 5
  1. Comparison of different method of LFSR–based SNG 13
  2. Comparison of two methods of CA–based SNG: single rule and mixed rule 16
  3. Examples for Stochastic scale adder based on 10–WBtt 23
  1. Evaluate the accuracy of stochastic FIR filter under different orders 35
  2. Comparison in terms of average error between conventional and stochastic approaches
in case of injecting different ratios of soft errors 44
Abstract
Although there are critical requirements in terms of the development of CMOS technology such as high fault-tolerance possibility, low-cost implementation, conventional computing is sensitive to meet these constraints. As a result, an unconventional computing method was proposed as a solution called Stochastic computing (SC) which is a novel way of doing computation and representing numbers. Basically, the bit sequences, which are used to represent information, are expressed under a probabilistic
form. This form, interpreted by the conventional number p (0 ≤ p ≤ 1), is a probability of observing
logic 1 in the bit sequences.
Theoretically, stochastic numbers (SNs) are considered as a Bernoulli random process [19] which has the probability of a bit being logic 1 is independent from the values of any previous bits. Furthermore, the information that SN carries only depends on the number of bit 1, not on position as conventional binary number. It is consequently different from traditional ways to express a number.
It’s important to note that SC was initially introduced as a low cost alternative in comparison with conventional computing as arithmetic operation (addition, subtraction, multiplication, division, etc.) can be simply implemented. Beside that, it also was seen as a method of high fault–tolerance, especially for soft error come from process variations. Despite being a reasonable solution for development of current technology, SC still confronts some drawbacks such as low accuracy and very long computation time. Consequently, studies or applications relying on this technique will deal with the trade–off between the accuracy and processing time. In addition, it must be considered other problems of SC, such as stochastic number generator (SNG), stochastic arithmetic, etc.
SC has been studied significantly in many domains, e.g, neural computation, digital filter, image processing for its potential capacity to deal with incident defects in nano scale device. Since this approach has received some initially reliable results, it promises to be an appealing concern for future research.
The main objective of this Master thesis is to study and design computing architecture paradigms following the concepts of stochastic computing. Besides the related concepts will be conducted on, the basic components will be designed as a VHDL library for FPGA and ASIC. Considering this unconventional computing, we expect to achieve an ameanable solution for the issues of the current CMOS technology.
Our work in this thesis is organized as follows. Chapter 1 gives an overview of stochastic system: related concepts, main components, principal issues, exist works and recent studies as well as its promised applications. After that, the most important part in SC, Stochastic Number Generator (SNG), will be discussed in Chapter 2 by using various approaches based on Linear Feedback Shift Register (LFSR) and One–Dimensional Cellular Automata (1–D CA). Chapter 3 continues focusing on the stochastic operators which are relied on both combinational logic and sequential logic. About the stochastic applications, edge detection and median filter in image processing will be considered as case studies in Chapter 4. Eventually, chapter 5 gives conclusions and perspectives.
Acknowledgement
I would like to express my deep gratitude to Professor Olivier SENTIEYS, my research supervisor, for his patient guidance, enthusiastic encouragement and useful critiques of this research work. Fur- thermore, I would also like to thank Professor Arnaud TISSERAND, for his useful and constructive recommendations in understanding on random number generators. My grateful thanks are also ex- tended to Professor Weikang QIAN and Professor Peng LI for their help in implementing stochastic functions based on Finite State Machine, and to David H.K. Hoe, who helped me studying on Stochas- tic Number Generator using Cellular Automata.
I would also like to extend my thanks to the technicians of CAIRN Laboratory, especially to Raphael BARDOUX for his assistance on FPGA implementation and to Nicolas VEYRAT-CHARVILLON for his help on the idea to stochastic constant generator based on Linear Feedback Shift Register.
My completion of this project could not have been accomplished without the support of my classmates, Minh, Tin, Hung, Nejla; and my vietnamese friends in Lannion. To Benjamin, Albert and Guillaume for helping me in understanding more french language and for the trips to Rennes in the master course work.
Finnaly, I wish to thank my family for their support and encouragement throughout my study in France.
Chapter 1
State of the art in Stochastic computing
Stochastic Computing (SC) was firstly introduced by Gaines [8] in 1967 as a promissed alternative in
comparison with conventional computing. In this new way of computation, any quantity is mapped into the interval [0, 1] or [−1, 1] by using two mappings Unipolar and Bipolar which are of particular interest
because they lead to computations similar to those of the conventional computing. SC’s operators are
also early proposed by using basic logic elements [8], [9], [19]: AND gate for Multiplication, NOT gate for Invertor, Multiplexer (MUX) for Addition/Subtraction, etc. A stochastic computer model was equally introduced, however, it was seen as impractical approach because SC requires a very long computation time and causes relatively low accuracy. Nevertheless, the probability in computation has recently been considered since the current technology trends, in particular CMOS technology, tend to increase uncertainty in circuit behavior. Therefore, SC has lately gained attention from reseachers due to its benefits over conventional computing [4]:
This part will continue to provide an overview with respect to SC: related concepts, exist works, as well as recent studies on SC.
1