Stokastik Hesaplamada Hata Oranlarını Azaltmak İçin Yeni Yöntemler

Abstract

Günümüzde hesaplama yapması için tasarlanan devreler küçük boyut ve düşük güç tüketimi gibi konuları dikkate alır. Üretim sürecindeki hatalar olasılıksal terimlerle ifade edilebilir. Bu nedenle bu hatalarla ilgili geleneksel olmayan yöntemler tercih edilmeye başlanmıştır. Stokastik hesaplama, bu geleneksel olmayan yöntemlerden biridir. Stokastik hesaplama, rastgele bit dizileriyle zamanda kesintisiz değerleri temsil eden teknikler topluluğudur ve ilk olarak 1953 yılında John von Neumann tarafından hazırlanan bir makale ile takdim edilmiştir. Bu kesintisiz değerler olasılıklar olarak değerlendirilir. Dolayısıyla geçerli aralık [0,1] aralığıdır. Stokastik hesaplama devrelerini gerçeklemek kolaydır (çarpma için tek bir VE kapısı). Diğer bir deyişle düşük maliyetli gerçeklemeler yapılabilmektedir. İlave olarak, tek bir bit değeri değişimi stokastik sayının temsil ettiği değerde küçük bir değişime neden olacaktır. Bir bit değeri değişimi gerçekleşirse temsil edilen değerin paydası 1 artacak veya azalacaktır. Stokastik hesaplamanın sahip olduğu etkileyici avantajların yanısıra dezavantajları da vardır. Bunlar temelde süre ve hata oranlarıdır. Aynı olasılık değerleri farklı permütasyonlarla da elde edilebileceği için beklenen sonuçlar her zaman elde edilemeyebilir. Bu durum hatalı bir değer elde edilmesine yol açabilir. Kısa bit dizileri için bu hata oranları oldukça yüksektir. Hata oranlarını azaltmak için, dizilerin uzunluklarının arttırılması gerekmektedir. Ancak, uzun bit dizileri işlem süresini arttırmaktadır. Stokastik hesaplama alanındaki araştırmalar hata oranlarını göz ardı etmektedir. Yüksek hata oranları stokastik hesaplamanın uygulama alanlarını daraltmaktadır. Bu problem bu tezi yazmada temel motivasyonumuz olmuştur. Çarpma ve ölçekli toplama stokastik hesaplamanın temel aritmetik işlemleridir. Çarpma giriş dizisinin uzunluğundan bağımsız olarak tek bir VE kapısı ile gerçeklenebilmektedir. Geleneksel yöntem ile uzun bit dizilerini çarpmak için fazla sayıda eleman içeren bir devre kullanılmalıdır. [0,1] kapalı aralığında kalma zorunluluğu olduğu için toplama işlemi stokastik hesaplamada kullanılamaz. Onun yerine ölçekli toplama tanımlanmıştır. Ölçekli toplama yapmak için çoklayıcı kullanılır. Stokastik devrelerde çıkış deterministiktir. Çünkü çıkıştaki değer, çıkış dizisinin içerdiği lojik 1’ler sayılarak elde edilir. Ancak, rastgele bit atama yönteminde girişler olasılıksaldır. Bu yüzden hata oranları bu yöntemde yüksek çıkmaktadır. Hata oranlarını azaltmak amacıyla girişlerin de deterministik olduğu rastgele bit karıştırma yöntemi önerilmiştir. Geleneksel stokastik hesaplamada Bernoulli dağılımına sahip bit dizileri birbirinden bağımsızdır. Bağımsız bit dizileri ile girişlerin tüm kombinasyonları için hatasız çıkış elde etmek mümkün değildir. Eğer giriş dizileri bağımlı hale gelirse beklenen çıkış değeri de değişir. Bağımlılık kullanılarak hatasız çıkışlar elde etmek mümkündür. Bir girişin değili ikinci giriş olarak uygulanırsa çıkışta 0 değeri elde edilir. Ayrıca iki girişe de aynı dizi uygulanırsa, çıkışta da aynı dizi elde edilir. Ancak çıkışta elde edilmesi beklenen değerler elde edilen değerler değildir. Bu bağımlılığın sonucudur. Bu tezde, ilk bölümde hata oranlarını azaltmak amacıyla, adını rastgele bit karıştırma yöntemi koyduğumuz yeni bir yöntem önerdik. Bu yöntem, stokastik hesaplamada geleneksel olarak kullanılan rastgele bit üreteçleri ile oluşturulan bit dizileri ile (bu yönteme de rastgele bit atama yöntemi adını koyduk), lojik kapılar ve bunlardan oluşan devreler kullanılarak hata oranları üzerinden karşılaştırılmıştır. İki yöntemin arasındaki fark giriş dizileri aynı değerleri temsil etse de dizilerin fiziksel olarak farklılık göstermesidir. Karşılaştırma yapmak için çeşitli giriş kombinasyonları ile hatayı veren iki ve üç boyutlu grafikler çıkarılmış, bit dizilerinin değişik uzunlukları dikkate alınmış, lojik kapılar için genel hata denklemleri oluşturulmuş, yazılımlar yardımıyla oluşturulan algoritmalar gerçeklenmiştir. Elde edilen veriler ışığında, önerilen rastgele bit karıştırma yöntemi, temel lojik kapılar için geleneksel yöntemden daha iyi hata oranları vermiştir. Bağımlılık kullanılarak hatasız çıkışlar elde etmek mümkündür sonucuna vardıktan sonra bağımlılığı kullanarak hatasız çıkış değerleri elde etmeye çalıştık. Bağımlılığı kullandığımız devre yapılarında rastgele bit karıştırma yöntemi kullanılmalıdır. Rastgele bit atama yöntemi ile hatasız sonuçlar elde edilemez. Giriş dizilerini iyileştirme çalışmalarından sonra devre yapısını iyileştirmeye çalıştık. 3. kısımda 0.5 ile hatasız çarpma yapan bir blok ve hatasız çarpma için iki yöntem önerdik. 0.5 ile çarpma bloğunu herhangi bir olasılık değerini hatasız elde etmek için uyarladık. Önerdiğimiz iki yönteme de bit bit kaydırma ve dizi klonlama yöntemi adını verdik. Bilgisayar programları ile yaptığımız simülasyonlarda önerdiğimiz bloğun ve yöntemlerin hatasız sonuçlar verdiğini doğruladık. 4. kısımda, çalışmamız sonucunda elde ettiğimiz sonuçları yorumladık ve gelecekte uygulanabileceği çalışma alanlarından da bahsettik.

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.