Stokastik hesaplama alternatifi olarak bit katarı hesaplama ile hatasız aritmetik işlem bloklarının tasarımı
Design of accurate arithmetic operation blocks via bit stream computing as an alternative to stochastic computing
Yazar: ENSAR VAHAPOĞLU
Danışman: DR. ÖĞR. ÜYESİ MUSTAFA ALTUN
İstanbul Teknik Üniversitesi / Fen Bilimleri Enstitüsü / Elektronik ve Haberleşme Mühendisliği Ana Bilim Dalı / Elektronik Mühendisliği Bilim Dalı
Derece: Yüksek Lisans, 2018
Konu: Elektrik ve Elektronik Mühendisliği = Electrical and Electronics Engineering
Dizin: Sayısal devreler = Digital circuits ; Sayısal entegre devre = Digital integrated circuit ; Çarpma devreleri = Multiplier circuits

Özet:
Stokastik hesaplama (SH), seri bit katarlarını olasılıksal olarak işleyen bir hesaplama paradigmasıdır. Aslen 1950'lerde teklif edilmesine karşın, halen kullanılan ikili hesaplamaya göre doğruluk konusunda geride kaldığı için gözden düşmüştür.

Son yıllarda entegre devre tasarımının fiziksel sınırlarına yaklaşmasıyla birlikte, hatırı sayılır derecede alan tasarrufu sağlayan stokastik hesaplama yeniden gündeme gelmiştir. Özellikle kesin doğruluk gerektirmeyen (işaret işleme, yapay sinir ağları vb.) uygulamalarda sıklıkla kullanılmaya başlamıştır. Ancak, doğruluk problemi stokastik hesaplamanın kullanımını sınırlamaya devam etmektedir. 

Bu çalışmada, stokastik hesaplama ile aynı mantığı kullanan ``Bit Katarı Hesaplama" adlı yeni bir hesaplama paradigması teklif edilmiştir. Bit Katarı Hesaplama, temel olarak stokastik hesaplamanın alan avantajı ile geleneksel ikili hesaplamanın doğruluk avantajını birleştirir. Stokastik hesaplamadaki gibi rastgele veya Binom dağılımlı katarlar kullanılmasına ihtiyaç duymaz. Geleneksel ikili hesaplamadaki gibi bilgiyi paralel bitlerle işlemek yerine seri bit katarları kullanarak devrelerin alan maliyetini önemli derecede düşürür. Neticede, bu paradigma ile üretilen tasarımlar düşük alan maliyeti, yüksek doğruluk gibi modern ihtiyaçlara cevap verebilecek kapasitededir.

Geleneksel hesaplamanın temel aritmetik işlem blokları toplayıcı ve çarpıcı devrelerdir. Bu çalışmada da Bit Katarı Hesaplama ile toplayıcı ve çarpıcı devreler teklif edilmiştir. Ancak, yapılan tasarımların stokastik veya bit katarı hesaplama ile elde edilebilecek optimum sonuçlara ne kadar yakın olduğunu anlamak amacıyla, öncelikle bu paradigmaların giriş/çıkış bit katarı uzunluğu, doğruluk, devre karmaşıklığı gibi ölçütler açısından sınırları belirlenmiştir. 

Farklı ihtiyaçlar için seçenekleri arttırmak amacıyla hem asenkron hem de senkron tasarımlara yer verilmiştir. Ayrıca ardışık katarları işleyebilen tasarımlar da teklif edilmiştir. Bütün tasarımların doğruluk ve alan karmaşıklığı sonuçları, stokastik/bit katarı hesaplama ile elde edilebilecek optimum sınırlara oldukça yakındır. 

Bit katarı hesaplama kullanılarak teklif edilen toplayıcı ve çarpıcı devreler, geleneksel ikili veya stokastik hesaplama ile tasarlanan literatürdeki benzerleri ile alan, gecikme ve doğruluk yönünden karşılaştırılmıştır. Bu çalışmanın özgün yanlarından bir diğeri, karşılaştırma için yapılan benzetimlerin transistör seviyesinde olmasıdır. Böylece kapı veya sistem seviyelerindeki benzetimlerde ortaya çıkmayan zamanlama problemleri de incelenmiştir. 

Benzetimler Cadence ortamında AMS 0.35um CMOS teknolojisinde transistör ve kapı seviyesinde yapılmıştır. Yapılan karşılaştırmalarda, teklif edilen toplayıcı ve çarpıcı devrelerin stokastik benzerlerine her açıdan üstünlük sağladığı görülmüştür. Geleneksel ikili devreler ise sadece gecikme konusunda geride bırakılamamıştır ki, gecikme seri katarlar kullanan herhangi bir devre için katlanılması gereken bir sorundur.

Karşılaştırmalar ayrıca basit bir yapay sinir ağları uygulamasında da yapılmıştır. Bu uygulamada da, teklif edilen devrelerin doğruluktan neredeyse hiç feragat etmeyerek büyük ölçüde alan tasarrufu yaptığı görülmüştür. 

Sonuç olarak, bu çalışma ile geleneksel ikili veya stokastik hesaplama ile üretilenlere göre çok daha küçük ve yüksek doğruluklu aritmetik işlemler gerçekleyebilen hesaplamalar için yeni ufuklar açıldığına inanılmaktadır.

Abstract:
Stochastic computing is a computing paradigm that process serial bit streams probabilistically. It uses randomly generated streams and stores the information in them as probability of 1s. Despite its initial emergence at 1950s, it loses favor since it got behind in still-used binary computing in terms of accuracy.

Recently, mostly because integrated circuit design has been approaching its physical limits, stochastic computing, providing substantial amount of area savings, has been brought to agenda. It started to be used frequently especially on the applications not requiring perfect accuracy like signal processing, artificial neural networks, etc. Nevertheless, accuracy problem still continues to limit stochastic computing.

In this work, a new computing paradigm ``Bit Stream Computing" that is constructed on the logic used in stochastic computing has been proposed. Bit Stream Computing can be considered as a generalized version of stochastic computing. It mainly combines the area advantage of stochastic computing with accuracy advantage of conventional binary computing. It does not need to employ randomly generated or Binomially distributed streams. It decreases the area cost of the circuits by processing the information with serial bits instead of using parallel bits as in conventional binary computing. As a result, the circuits produced via this paradigm has the potential to satisfy the current needs such as low cost and high accuracy.

A computing paradigm primarily needs arithmetic operations. The main arithmetic operation blocks of conventional computing are addition and multiplication circuits. Likewise, this work proposes addition and multiplication circuits with bit stream computing to lay a foundation. However, as a  beginning, it is preferred to determine the limits of stochastic or bit stream computing in terms of the metrics like input/output stream length, accuracy, circuit complexity. This determination facilitates to check any proposed design whether its results are close to optimum ones. 

The determination of the limits of stochastic/bit stream computing also reveals some interesting outcomes:

- Randomly generated or binomially distributed streams are not be able to produce 100\% accurate results, i.e. perfect accuracy needs deterministic streams.
- Addition and multiplication operations also require longer output streams than of inputs for perfect accuracy.
- 100\% accurate stochastic/bit stream computing circuits are not compatible with successive stream processing.

These outcomes have given reasons to branch the circuits proposed with bit stream computing. Both synchronous and asynchronous designs are proposed to satisfy various requirements. For instance, generally asynchronous designs are more cost effective than synchronous ones in cases of shorter bit streams. Synchronous designs are also classified as two subgroups named constant stream and increased stream designs. The former group is suitable for successive stream processing while the latter has \%100 accuracy. The proposed asynchronous designs are also perfectly accurate, therefore they are not suitable for successive stream processing. The reason why any asynchronous design that suitable for successive stream processing is not proposed has also been explained. The accuracy and area complexity results of all proposed designs are quite close to the optimum limits which can be achieved via stochastic/bit stream computing. 

Adder and multiplier circuits proposed with bit stream computing are compared with their conventional binary and stochastic predecessors in the literature in terms of area, delay, and accuracy. One of the distinctive features of this work is its that simulations carried out for comparisons are in transistor level. Nearly all previous works in stochastic computing do not have any transistor level simulations which results in to overlook some drawbacks that can be only noticed in this simulations such as time alignment problems. On the other hand, the proposed circuits and their predecessors are also examined in this simulations and they are tried to be optimized to get rid of this unnoticed problems.

Simulations are carried out in both transistor and gate level with AMS \SI{}{0.35\micro m} CMOS technology in Cadence environments. Accuracy comparisons with transistor level simulations are made with two novel metrics suitable for stochastic/bit stream computing: integrity and correctness. These metrics pave the way to examine any stochastic/bit stream computing design with regards to the drawbacks coming to existence in transistor level simulations.

Delay comparisons are also made by dividing the delay results into two metrics: inherent circuit delay and stream delay. The results have shown that the proposed circuits outperform any former stochastic design. Another outcome of these comparisons is that the delay amounts stochastic/bit stream computing designs are mainly comes from stream delay instead of inherent circuit delay so that considering only stream delay for these designs is a quite rational simplification.

Area comparisons prove that our proposed designs are most area-efficient ones among all compared designs. One of them (Synchronous Constant Stream Adder) has even $ O(1) $ complexity with respect to bit lengths, i.e. it is completely scalable. With zero or tiny sacrifice from accuracy, proposed designs provide substantial amount of area savings. Out of these designs, asynchronous ones have low cost for smaller bit lengths, while synchronous ones are more area-friendly for longer.

Lastly, a simple neural network is implemented with all compared designs to show our designs' supremacy in an application. Comparisons are also classified with regard to input/output signal format (analog, binary and bit stream). The implementations are compared in terms of area (number of transistors) and accuracy (misclassification rate). Our perfectly accurate designs generally have better area performance than other binary or stochastic designs. On the other hand, the area results of our semi-accurate (constant stream/suitable for successive processing) designs have the lowest area cost in exchange for an insignificant accuracy lost.

To sum up, this work proposes a novel computing paradigm ``Bit Stream Computing" which has the ability to realize the main arithmetic operations more efficiently than previous computing paradigms. It is believed that this work opens up new horizons for computing paradigms that is capable of realizing much smaller and  more accurate arithmetic operations than conventional binary or stochastic computing.