Stochastic computing: Difference between revisions

Revision as of 04:51, 9 August 2023

Latest revision as of 06:07, 5 November 2024

(10 intermediate revisions by 6 users not shown)

Line 1:

{{Short description|Computing using random bit streams}}

'''Stochastic computing''' is a collection of techniques that represent continuous values by streams of random bits. Complex computations can then be computed by simple bit-wise operations on the streams. Stochastic computing is distinct from the study of [[randomized algorithm]]s.

== Motivation and a simple example ==

Suppose that <math>p,q \in [0,1]</math> is given, and we wish to compute <math>p \times q</math>. Stochastic computing performs this operation using probability instead of arithmetic.

Specifically, suppose that there are two random, independent bit streams called ''stochastic number''s (i.e. [[Bernoulli process]]es), where the probability of a one1 in the first stream is <math>p</math>, and the probability in the second stream is <math>q</math>. We can take the [[Logical and#Applications in computer programming|logical AND]] of the two streams.

{| class="wikitable" style="text-align:left;"

Line 17:

| 1 || 0 || 0 || 1 || 0 || 0 || ...

|}

The probability of a one1 in the output stream is <math>pq</math>. By observing enough output bits and measuring the frequency of ones1s, it is possible to estimate <math>pq</math> to arbitrary accuracy.

The operation above converts a fairly complicated computation (multiplication of <math>p</math> and <math>q</math>) into a series of very simple operations (evaluation of <math>a_i \land b_i</math>) on random bits.

To put in another perspective, assuming the truth table of an AND gate. Conventional interpretation is that the output is true if and only if input A and B are true. However, if the table is interpreted vertically, (0011) AND (0101) is (0001), i.e., 1/2 x 1/2 = 1/4, which is exactly an arithmetic multiplication. As the information is presented in probability distribution, probability multiplication is literally an AND operation.

{| class="wikitable"

|+

!A

!B

!Out

|-

|0

|0

|0

|-

|0

|1

|0

|-

|1

|0

|0

|-

|1

|1

|1

}|}

More generally speaking, stochastic computing represents numbers as streams of random bits and reconstructs numbers by calculating frequencies. The computations are performed on the streams and translate complicated operations on <math>p</math> and <math>q</math> into simple operations on their stream representations. (Because of the method of reconstruction, devices that perform these operations are sometimes called stochastic averaging processors.) In modern terms, stochastic computing can be viewed as an interpretation of calculations in probabilistic terms, which are then evaluated with a [[Gibbs sampling|Gibbs sampler]]. It can also be interpreted as a hybrid [[Analog computer|analog]]/[[Computer|digital]] computer.

Line 47 ⟶ 69:

}}</ref>

mostly through a series of simultaneous and parallel efforts in the US<ref>

{{cite journalbook

| last1=Poppelbaum

| first1=W.

Line 54 ⟶ 76:

| last3=Esch

| first3=J.

| title=Proceedings of the November 14-16, 1967, fall joint computer conference on - AFIPS '67 (Fall)

| titlechapter=Stochastic computing elements and systems

| journal=Afips FJCC

| volume=31

| pages=635–644 |doi=10.1145/1465611.1465696 |isbn=9781450378963

Line 62 ⟶ 84:

}}</ref>

and the UK.<ref>

{{cite journalbook

| last=Gaines

| first=B.

| title=Proceedings of the April 18-20, 1967, spring joint computer conference on - AFIPS '67 (Spring)

| titlechapter=Stochastic Computingcomputing

| journal=Afips SJCC

| year=1967

| volume=30

Line 123 ⟶ 145:

</ref>

<ref>

{{cite conferencebook

|first1=M. |last1=van Daalen |first2=P. |last2=Jeavons |first3=J. |last3=Shawe-Taylor |title=&#91;1993&#93; Proceedings IEEE Workshop on FPGAs for Custom Computing Machines |chapter=A stochastic neural architecture that exploits dynamically reconfigurable FPGAs | year=1993 |isbn=0-8186-3890-7 |pages=202–211 |doi=10.1109/FPGA.1993.279462

| book-title=FPGAs for Custom Computing Machines, Proceedings IEEE, NAPA

|s2cid=14929278 }}

| title=A stochastic neural architecture that exploits dynamically reconfigurable FPGAs

|first1=M. |last1=van Daalen |first2=P. |last2=Jeavons |first3=J. |last3=Shawe-Taylor | year=1993 |isbn=0-8186-3890-7 |pages=202–211 |doi=10.1109/FPGA.1993.279462

}}

</ref>

Somewhat recently, interest has turned towards stochastic

Line 147 ⟶ 167:

}}

</ref> More recently, stochastic circuits have been successfully used in [[image processing]] tasks such as [[edge detection]]

<ref>{{Cite book | last1 = Alaghi | first1 = A. | last2 = Li | first2 = C. | last3 = Hayes | first3 = J. P. | doi = 10.1145/2463209.2488901 | chapter = Stochastic circuits for real-time image-processing applications | title = Proceedings of the 50th Annual Design Automation Conference on - DAC '13 | pages = 1 | year = 2013 | isbn = 9781450320719 | s2cid = 18174415 }}</ref> and [[Thresholding (image processing)|image thresholding]].<ref>{{Cite bookjournal | last1 = Najafi| first1 = M. H. | last2 = Salehi | first2 = M. E. | doi = 10.1109/TVLSI.2015.2415932 | chaptertitle = A Fast Fault-Tolerant Architecture for Sauvola Local Image Thresholding Algorithm Using Stochastic Computing | titlejournal = IEEE Transactions on Very Large Scale Integration (VLSI) Systems - TVLSI '16 | journaldoi = IEEE Transactions on Very Large Scale Integration (VLSI) Systems10.1109/TVLSI.2015.2415932 | volume = 24 | issue = 2 | pages = 808–812 | year = 2016 | s2cid = 6591306 }}</ref> Recent advancement in stochastic circuits also shows promising speed and energy efficiency advantages in artificial intelligence (AI) hardware acceleration on edge computing.

== Strengths and weaknesses ==

Line 169 ⟶ 189:

computer only requires an [[And gate|AND gate]]. Additionally,

a digital multiplier would naively require <math>2n</math> input wires,

whereas a stochastic multiplier would only require 2two input wires{{citation needed|date=October 2014}}.

(If the digital multiplier serialized its output, however, it would also

require only 2two input wires.)

Additionally, stochastic computing is robust against noise; if a few