New methods for reducing error rates in stochastic computing

Today circuits which are designed on the purpose of computing, care about small size, low power consumption and high reliability. Manufacturing process's defects can be described in probabilistic terms. For this reason unconventinal methods which are related with this defects are being preferred. Stochastic computing is one of these unconventional methods. Stochastic computing was first presented in a paper written by John von Neumann in 1953. In stochastic computing, numbers stand for probability values (with or without error) are represented by random bit streams. Therefore, the available range is [0,1] interval. It is easy to realise the circuits of stochastic computing (e.g. one AND gate for multiplication). In other words low cost implementations can be realised . Moreover, a single bit flip will cause a small change in the value of the stochastic numbers. The value of the nominator will be increased or decreased by 1 if a single bit flip happens. Along the great advantages, stochastic computing has disadvantages. These are mainly time and error rates. Different combination of streams represent same values and this yields error rates in stochasting computing. These error rates are extremely high for short bit streams. To reduce error rates, longer bit streams should be used. But these longer streams extend the operation time. Research about stochastic computing in literature has not mentioned about error rates before. The high error rates narrows down the application field of stochastic computing. This problem becomes our motivation to write this thesis. Complicated stream operations can be performed with simple circuits in stochastic computing. Multiplication and scaled addition are basic arithmetic operation of stochasting computing. Multiplication can be realized with one AND gate independent from the input bit stream length. The circuit may be extremely large to multiply long bit streams with the conventional method. Due to the interval [0,1], addition cannot be performed in stochastic computing. Instead, scaled addition that guarantees to remain in the interval is described. MUX is used for scaled addition. The output in stochastic circuits is deterministic because it is obtained by counting 1s in the output stream. However, the inputs in the random bit assigning method are probabilistic. Therefore, error rates appear to be high in this method. In order to reduce the error rates, random bit shuffling method whose inputs are aslo deterministic was researched. In conventinal SC, bit streams which have Bernoulli distribution are independent from each other. With independent streams it is not possible to obtain error free outputs for all combination of inputs. If input streams become dependent, expected result for classical SC will change. By using dependency it is possible to obtain error free outputs. If the inverse of an input is applied as second input, 0 value will be obtained at output. It is expected that z = p * (1-p), but due to dependency this expectation fails. Morever, if the first input is applied also as a second input, the same input will be obtained at output. It acts like a buffer. It is expected that z = p * p, but due to dependency this expectation fails. In the first part of this thesis, we offer a method based on improving the generation of bit streams. In Section 2 detailed information about our method and the conventional one is given. This method has been compared with the bit sequence generated by random bit generators (we named it random bit assigning method) traditionally used in stochastic computing by using logic gates and circuits in terms of error rates. In order to compare, 2D and 3D graphs that shows the error were drawn by realising different combinations of two inputs, different length of bit streams were taken into consideration, general error equations for logic gates were obtained and algorithms were realised with the aid of softwares. In order to generate bit streams in SC, random bit generators are used. We named this bit stream generation technic as random bit assign method (RBAM). Let desired input probability value for RBAM be p1 and let random number generator generates values between [0-1] with binomial distribution. If the generated value is smaller than p1, logic 1 is added to the stream. If the generated value is bigger than p1 logic 0 is added to the stream. Therefore, there exists difference between the desired input value and the obtained input value. Let the input desired value for random bit shuffling method (RBSM) be p1. In this method, depending on the desired probability value (p1) and the length of the bit stream (n), a bit stream containing n*p1 1s is generated. Fisher-Yates shuffling algorithm, adapted to the computers by Durstenfeld is applied. In this way, it is guaranteed that the desired and the generated input values are probabilistically same. With this approach output error rates will be downgraded. The difference between two methods is that the input streams shows differences physically although input bit streams represent same values. We worked on basic logic gates to make comparison between two methods. The results were obtained by fixing the two inputs, changing the inputs between [0, 1] interval and using different bit length. We benefit from the Monte Carlo analysis to obtain the equations. This analysis is a generic name given to obtaining the solution of the problem by using random numbers. In the light of obtained data, the random bit shuffling method that is recommended, has given better error rates that traditional method for main logic gates. After the research on generating the input stream for reducing the error rates, we started working on circuitry. In Section 3 we show our works which are error free multiplication by 0.5 block, obtaining any probability value without an error, and two method for error free multiplication. We present a block for multiplication with 0.5 without an error. The block can also be used in generating probabilities. We also present new error free multiplication methods that we named it bitwise shifting method and stream cloning method. In the light of obtained data from computer programs, our block and method that is recommended, has given zero error rates. First, by keeping the input values, generated with RBSM, and expected output value same we tried to make changes with logic gates. During this study, we could not get the results we want with different circuits. The inputs had Gaussian distribution and output stream was having Gaussian distribution independent from the circuit we used. Therefore we could not obtain a change in error rates. Our research shows that with independency it is not possible to obtain error free circuitry. After facing this result, we decide to use dependency to obtain error free circuitry as a next step. In order to obtain error free circuitry, RBSM must be used. There is no way to get result without an error with RBAM. We suggest an error free block for multiplication by 0.5. With this block, the input stream is multiplied by 0.5 and zero error at output stream is achieved. However if the length of the input stream is n, the length of the output stream will be 2n because of merging operation. We design a circuit for this merge operation. Same block is working for OR gate. AND gates should substitute with OR gates. At the output 0.5 + 0.5 * p is obtained. OR gates can be used to obtain probability values. We adapt the block realizing the error free multiplication with 0.5 to Switch Circuits in order to obtain any probability value. Inputs are 0.5 (0.12=1/2). In order to shift the binary value one digit to right and add "0", the circuit block based on AND gate is used (0.012=1/4). In order to shift the binary value one digit to right and add "1", the circuit block based on OR gate is used (0.112=3/4). By cascading the blocks, any desired probability value can be obtained without error. At a later stage, we suggest Bitwise Shifting Method for multiplication. In this method one of the two inputs is kept, while shifting one bit of other input to the left. Shift operation is applied "the length of the input stream-1" times (e.g. if the input is 8 bit, shift operation will be applied 7 times). Bit streams obtained from the output gate are merged. This method will be implemented by changing the structure of "Binary to Stochastic Converter" part. We aim to get the manipulated stream we want with this philosophy. Also just one AND gate will be used. We are aware that randomness is destroyed with changing the generation of the input streams. We intend to multiply two probability values with using less transistors. We suggest another method for multiplication. In this method, cloning is the main idea. The philosophy of RBSM constitutes a basis for this method. We must generate the probability value without an error. One of the input is cloned up to the number of bits (p1=1/4 (0100010001000100)). The other input is re-prepared based on p2. In Section 4, we discuss the results which we obtained during our work. Also future works that we will apply our methods/circuits are considered.