Content deleted Content added
Marcocapelle (talk | contribs) removed Category:Stochastic algorithms; added Category:Statistical randomness using HotCat |
No edit summary |
||
| (30 intermediate revisions by 18 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
{| class="wikitable" style="text-align:left;"
Line 19 ⟶ 17:
| 1 || 0 || 0 || 1 || 0 || 0 || ...
|}
The probability of a
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 29 ⟶ 49:
[[Image:RASCEL stochastic computer 1969.png|thumb|alt=A photograph of the RASCEL stochastic computer.|The RASCEL stochastic computer, circa 1969]]
Stochastic computing was first introduced in a pioneering paper by [[John von Neumann]] in 1953.<ref>{{cite conference |last = von Neumann
|first = J.
|publisher = Macmillan
|year = 1963
|isbn = 978-0-393-05169-8
}}</ref> However, the
theory could not be fully developed until advances in computing of the 1960s,<ref>{{cite conference
| last1 = Petrovic | first1= R. | last2=Siljak | first2=D. | title=Multiplication by means of coincidence | year = 1962 | book-title =ACTES Proc. of 3rd Int. Analog Comp. Meeting |url=https://books.google.com/books?id=94BQAAAAMAAJ}}</ref>
<ref>
{{citation
Line 46 ⟶ 69:
}}</ref>
mostly through a series of simultaneous and parallel efforts in the US<ref>
{{cite
| last1=Poppelbaum
| first1=W.
Line 53 ⟶ 76:
| last3=Esch
| first3=J.
| title=Proceedings of the November 14-16, 1967, fall joint computer conference on - AFIPS '67 (Fall)
|
| volume=31
| pages=635–644 |doi=10.1145/1465611.1465696 |isbn=9781450378963
| year=1967
| s2cid=8504153
}}</ref>
and the UK.<ref>
{{cite
| last=Gaines
| first=B.
| title=Proceedings of the April 18-20, 1967, spring joint computer conference on - AFIPS '67 (Spring)
|
| year=1967
| volume=30
| pages=149–156 |doi=10.1145/1465482.1465505 |isbn=9781450378956
| s2cid=832296
}}</ref>
By the late 1960s, attention turned to the design of
Line 77 ⟶ 102:
| first2=W.
| title=Stochastic and deterministic averaging processors
| year=1981 |publisher=P. Peregrinus |isbn=978-0-906048-44-3
}}
</ref>
Line 83 ⟶ 108:
{{cite thesis
| last=Esch
| first=
| title=RASCEL, a programmable analog computer based on a regular array of stochastic computing element logic
| year=1969 |id=AAI700084 |type=PhD |url=https://dl.acm.org/doi/book/10.5555/904878
|
}}
</ref>
Line 98 ⟶ 123:
| title=Proceedings of the first International Symposium on Stochastic Computing and its Applications
| ___location= Toulouse, France
| year=1978 |oclc=499229066
}}
</ref>
Line 109 ⟶ 134:
control.<ref>
{{cite conference
|
| title=Stochastic Computing Systems
| last=Gaines
Line 115 ⟶ 140:
| editor-last=Tou
| editor-first=Julius
| volume=2
| orig-year=1969 |publisher=Springer |year=2013 |isbn=9781489958433
}}
</ref>
<ref>
{{cite
|first1=M. |last1=van Daalen |first2=P. |last2=Jeavons |first3=J. |last3=Shawe-Taylor |title=[1993] 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
|s2cid=14929278 }}
</ref>
Somewhat recently, interest has turned towards stochastic
Line 131 ⟶ 153:
correcting codes.<ref>
{{cite journal
| title=Iterative decoding
| last1=Gaudet
| first1=Vincent
| last2=Rapley
| first2=Anthony
| journal=
| volume=39
| number=3
| pages=299–301
|date=February 2003
| doi=10.1049/el:20030217
| bibcode=2003ElL....39..299G
}}
</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 |
== Strengths and weaknesses ==
Line 165 ⟶ 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
(If the digital multiplier serialized its output, however, it would also
require only
Additionally, stochastic computing is robust against noise; if a few
Line 176 ⟶ 200:
Circuits work properly even when the inputs are misaligned temporally. As a result, stochastic
systems can be designed to work with inexpensive locally generated clocks instead of using a global clock and
an expensive clock distribution network.<ref>{{Cite
Finally, stochastic computing provides an estimate of the solution
Line 183 ⟶ 207:
referred to as ''progressive precision'', which suggests that the precision
of stochastic numbers (bit streams) increases as computation proceeds.
<ref>{{Cite journal | last1 = Alaghi | first1 = A. | last2 = Hayes | first2 = J. P. | doi = 10.1145/2465787.2465794 | title = Survey of Stochastic Computing | journal = ACM Transactions on Embedded Computing Systems | volume = 12 | issue = 2s | pages = 1 | year = 2013 |
It is as if the [[most significant bit]]s of the number
arrive before its [[least significant bit]]s; unlike the
Line 208 ⟶ 232:
Second, stochastic computing requires a method of generating random
biased bit streams. In practice, these streams are generated with
[[
(pseudo-)random bits is fairly costly (compared to the expense of,
e.g., a full adder). Therefore, the gate-level advantage of
Line 224 ⟶ 248:
''latching'', where feedback between different components can achieve
a deadlocked state.<ref>
{{cite
| last1=Winstead
| first1=C.
Line 233 ⟶ 257:
| last4=Schlegel
| first4=C.
|
▲| journal=IEEE International Symposium on Information Theory
| ___location=Adelaide Australia
|date=September 2005
| pages=1116–1120
| arxiv=cs/0501090 |doi=10.1109/ISIT.2005.1523513 |isbn=0-7803-9151-9
| s2cid=16390484
}}
</ref>
Line 251 ⟶ 278:
a host of problems.
Other functions (such as the averaging operator <math>f(p,q)\rightarrow (p+q)/2</math>
either stream decimation or inflation. Tradeoffs between precision and memory
can be challenging.
Line 273 ⟶ 300:
modeled very simply with stochastic computing.<ref>
{{cite journal
| title=Iterative decoding
| last1=Gaudet
| first1=Vincent
| last2=Rapley
| first2=Anthony
| journal=
| volume=39
| number=3
| pages=299–301
|date=February 2003
| doi=10.1049/el:20030217
| bibcode=2003ElL....39..299G
}}
</ref>
Line 298 ⟶ 327:
| last3=Milner
| first3=A.
|
| year=2006
}}
Line 304 ⟶ 333:
The proponents of these methods argue that the performance of stochastic decoding is
competitive with digital alternatives.
== Deterministic Methods to Stochastic Computing ==
Deterministic methods of SC has been developed to perform completely accurate computation with SC circuits.<ref>{{Cite journal|last1=Najafi|first1=M. Hassan|last2=Jenson|first2=Devon|last3=Lilja|first3=David J.|last4=Riedel|first4=Marc D.|date=December 2019|title=Performing Stochastic Computation Deterministically|journal=IEEE Transactions on Very Large Scale Integration (VLSI) Systems|volume=27|issue=12|pages=2925–2938|doi=10.1109/tvlsi.2019.2929354|s2cid=201888463|issn=1063-8210|doi-access=free}}</ref> The essential principle of these methods is that every bit of one bit-streams interacts with every bit of the other bit-streams exactly once. To produce completely accurate result with these methods, the operation must run for the product of the length of input bit-streams. Deterministic methods are developed based on unary bit-streams,<ref>{{Cite book|last1=Jenson|first1=Devon|last2=Riedel|first2=Marc|title=Proceedings of the 35th International Conference on Computer-Aided Design |chapter=A deterministic approach to stochastic computation |date=2016-11-07|pages=1–8|___location=New York, NY, USA|publisher=ACM|doi=10.1145/2966986.2966988|isbn=978-1-4503-4466-1|s2cid=11281124}}</ref><ref>{{Cite journal|last1=Najafi|first1=M. Hassan|last2=Jamali-Zavareh|first2=Shiva|last3=Lilja|first3=David J.|last4=Riedel|first4=Marc D.|last5=Bazargan|first5=Kia|last6=Harjani|first6=Ramesh|date=May 2017|title=Time-Encoded Values for Highly Efficient Stochastic Circuits|journal=IEEE Transactions on Very Large Scale Integration (VLSI) Systems|volume=25|issue=5|pages=1644–1657|doi=10.1109/tvlsi.2016.2645902|s2cid=5672761|issn=1063-8210|doi-access=free}}</ref> pseudo-random bit-streams,<ref>{{Cite journal|last1=Najafi|first1=M. Hassan|last2=Lilja|first2=David|date=2018|title=High Quality Down-Sampling for Deterministic Approaches to Stochastic Computing|journal=IEEE Transactions on Emerging Topics in Computing|volume=9|pages=7–14|doi=10.1109/tetc.2017.2789243|issn=2168-6750|doi-access=free}}</ref> and low-discrepancy bit-streams.<ref>{{Cite book|last1=Najafi|first1=M. Hassan|last2=Lilja|first2=David J.|last3=Riedel|first3=Marc|title=Proceedings of the International Conference on Computer-Aided Design |chapter=Deterministic methods for stochastic computing using low-discrepancy sequences |date=2018-11-05|pages=1–8|___location=New York, NY, USA|publisher=ACM|doi=10.1145/3240765.3240797|isbn=978-1-4503-5950-4|s2cid=53236540|doi-access=free}}</ref>
== Variants of stochastic computing ==
Line 334 ⟶ 367:
solution). Additionally, it retains the linear precision of bundle
and ergodic processing.
==See also==
* [[Unconventional computing]]
==References==
Line 339 ⟶ 375:
==Further reading==
* {{cite journal|url=http://pages.cpsc.ucalgary.ca/~gaines/reports/COMP/IdentSC/IdentSC.pdf|title=Techniques of Identification with the Stochastic Computer|last=Gaines|first=Brian R. |journal=Proceedings IFAC Symposium on "The Problems of Identification in Automatic Control Systems", Section 6 Special Identification Instruments, Prague June 12–19, 1967|year=1967|
* {{cite journal|url=http://homes.cs.washington.edu/~armin/ACM_TECS_2013.pdf|title=Survey of Stochastic Computing|last1=Alaghi|first1=Armin|last2=Hayes|first2=John P.|journal=ACM Transactions on Embedded Computing Systems|volume=12|issue=2s|pages=1–19|year=2013|
[[Category:History of computing hardware]]
| |||