Stochastic computing: Difference between revisions

Revision as of 20:30, 14 June 2020

Revision as of 11:37, 25 August 2020

Line 38:

}}</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 | booktitle =ACTES Proc. of 3rd Int. Analog Comp. Meeting |url=https://books.google.com/books?id=94BQAAAAMAAJ}}</ref>

Multiplication by means of coincidence | year = 1962 | booktitle =

ACTES Proc. of 3rd Int. Analog Comp. Meeting}}</ref>

<ref>

{{citation

Line 58 ⟶ 56:

| first3=J.

| title=Stochastic computing elements and systems

| journal=Afips FjccFJCC

| volume=31

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

| year=1967

| s2cid=8504153

}}</ref>

and the UK.<ref>

Line 68 ⟶ 67:

| first=B.

| title=Stochastic Computing

| journal=Afips SjccSJCC

| 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 81:

| first2=W.

| title=Stochastic and deterministic averaging processors

| year=1981 |publisher=P. Peregrinus |isbn=978-0-906048-44-3

| year=1981

}}

</ref>

Line 87:

{{cite thesis

| last=Esch

| first=JJohn W.

| 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

| year=1969

| ___locationpublisher=University of Illinois, Urbana, Illinois

}}

</ref>

Line 102:

| title=Proceedings of the first International Symposium on Stochastic Computing and its Applications

| ___location= Toulouse, France

| year=1978 |oclc=499229066

}}

</ref>

Line 119:

| editor-last=Tou

| editor-first=Julius

| publisher=Plenum Press

| volume=2

| origyear=1969 |publisher=Springer |year=2013 |isbn=9781489958433

| year=1969

}}

</ref>

Line 128 ⟶ 127:

| booktitle=FPGAs for Custom Computing Machines, Proceedings IEEE, NAPA

| 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

| last=van Daalen, M. R.| year=1993

}}

|display-authors=etal}}

</ref>

Somewhat recently, interest has turned towards stochastic

Line 146 ⟶ 145:

|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 | pmids2cid = | pmc =18174415 }}</ref> and [[Thresholding (image processing)|image thresholding]].<ref>{{Cite book | last1 = Najafi| first1 = M. H. | last2 = Salehi | first2 = M. E. | doi = 10.1109/TVLSI.2015.2415932 | chapter = A Fast Fault-Tolerant Architecture for Sauvola Local Image Thresholding Algorithm Using Stochastic Computing | title = IEEE Transactions on Very Large Scale Integration (VLSI) Systems - TVLSI '16 | journal = IEEE Transactions on Very Large Scale Integration (VLSI) Systems | volume = 24 | issue = 2 | pages = 808–812 | year = 2016 | pmids2cid = | pmc =6591306 }}</ref>

== Strengths and weaknesses ==

Line 181:

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 book | last1 = Najafi | first1 = M. H. | last2 = Lilja | first2 = D. J. | last3 = Riedel| first3 = M. D. | last4 = Bazargan | first4 = K. | doi = 10.1109/ASPDAC.2016.7428060 | title = Polysynchronous stochastic circuits | journal = 2016 21st Asia and South Pacific Design Automation Conference (ASP-DAC) | pages = 492–498 | year = 2016 | pmid = | pmc = | isbn = 978-1-4673-9569-4 | s2cid = 8973285 }}</ref>

Finally, stochastic computing provides an estimate of the solution

Line 188:

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 | pmid = | pmc = | citeseerx = 10.1.1.296.4448 | s2cid = 4689958 }}</ref>

It is as if the [[most significant bit]]s of the number

arrive before its [[least significant bit]]s; unlike the

Line 242:

| ___location=Adelaide Australia

|date=September 2005

| pages=1116–1120

| arxiv=cs/0501090

| arxiv=cs/0501090 |doi=10.1109/ISIT.2005.1523513 |isbn=0-7803-9151-9

| s2cid=16390484

}}

</ref>

Line 290 ⟶ 292:

|date=February 2003

| doi=10.1049/el:20030217

| bibcode=2003ElL....39..299G

}}

</ref>

Line 314 ⟶ 317:

== Deterministic Methods to Stochastic Computing ==

Deterministic methods of SC has been developed to perform completely accurate computation with SC circuits.<ref>{{Cite journal|lastlast1=Najafi|firstfirst1=M. Hassan|last2=Jenson|first2=Devon|last3=Lilja|first3=David J.|last4=Riedel|first4=Marc D.|date=December 2019|title=Performing Stochastic Computation Deterministically|url=http://dx.doi.org/10.1109/tvlsi.2019.2929354|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}}</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 journal|lastlast1=Jenson|firstfirst1=Devon|last2=Riedel|first2=Marc|date=2016-11-07|title=A deterministic approach to stochastic computation|url=http://dx.doi.org/10.1145/2966986.2966988|journal=Proceedings of the 35th International Conference on Computer-Aided Design|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|lastlast1=Najafi|firstfirst1=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|url=http://dx.doi.org/10.1109/tvlsi.2016.2645902|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}}</ref> pseudo-random bit-streams,<ref>{{Cite journal|lastlast1=Najafi|firstfirst1=M. Hassan|last2=Lilja|first2=David|date=2018|title=High Quality Down-Sampling for Deterministic Approaches to Stochastic Computing|url=http://dx.doi.org/10.1109/tetc.2017.2789243|journal=IEEE Transactions on Emerging Topics in Computing|pages=1–11|doi=10.1109/tetc.2017.2789243|issn=2168-6750}}</ref> and low-discrepancy bit-streams.<ref>{{Cite journal|lastlast1=Najafi|firstfirst1=M. Hassan|last2=Lilja|first2=David J.|last3=Riedel|first3=Marc|date=2018-11-05|title=Deterministic methods for stochastic computing using low-discrepancy sequences|url=http://dx.doi.org/10.1145/3240765.3240797|journal=Proceedings of the International Conference on Computer-Aided Design|pages=1–8|___location=New York, NY, USA|publisher=ACM|doi=10.1145/3240765.3240797|isbn=978-1-4503-5950-4|s2cid=53236540}}</ref>

== Variants of stochastic computing ==

Line 351 ⟶ 354:

==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|accessdate=2013-11-11}}

* {{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|accessdate=2013-11-11|doi=10.1145/2465787.2465794|citeseerx=10.1.1.296.4448|s2cid=4689958}}

[[Category:History of computing hardware]]