research-article

The synthesis of complex arithmetic computation on stochastic bit streams using sequential logic

Authors:

David J. Lilja,

Marc RiedelAuthors Info & Claims

ICCAD '12: Proceedings of the International Conference on Computer-Aided Design

Pages 480 - 487

https://doi.org/10.1145/2429384.2429483

Published: 05 November 2012 Publication History

Abstract

The paradigm of logical computation on stochastic bit streams has several key advantages compared to deterministic computation based on binary radix, including error-tolerance and low hardware area cost. Prior research has shown that sequential logic operating on stochastic bit streams can compute non-polynomial functions, such as the tanh function, with less energy than conventional implementations. However, the functions that can be computed in this way are quite limited. For example, high order polynomials and non-polynomial functions cannot be computed using prior approaches. This paper proposes a new finite-state machine (FSM) topology for complex arithmetic computation on stochastic bit streams. It describes a general methodology for synthesizing such FSMs. Experimental results show that these FSM-based implementations are more tolerant of soft errors and less costly in terms of the area-time product that conventional implementations.

References

[1]

N. Iqbal, M. Siddique, and J. Henkel, "Seal: soft error aware low power scheduling by monte carlo state space under the influence of stochastic spatial and temporal dependencies," in Design Automation Conference (DAC), 2011 48th ACM/EDAC/IEEE, pp. 134--139, IEEE, 2011.

Digital Library

[2]

X. Shih, H. Lee, K. Ho, and Y. Chang, "High variation-tolerant obstacle-avoiding clock mesh synthesis with symmetrical driving trees," in Proceedings of the International Conference on Computer-Aided Design, pp. 452--457, IEEE Press, 2010.

Digital Library

[3]

S. Rehman, M. Shafique, F. Kriebel, and J. Henkel, "Reliable software for unreliable hardware: embedded code generation aiming at reliability," in Proceedings of the seventh IEEE/ACM/IFIP international conference on Hardware/software codesign and system synthesis, pp. 237--246, ACM, 2011.

Digital Library

[4]

P. Li and D. J. Lilja, "A low power fault-tolerance architecture for the kernel density estimation based image segmentation algorithm," in IEEE International Conference on Application - specific Systems, Architectures and Processors, ASAP'11, 2011.

Digital Library

[5]

P. Li and D. J. Lilja, "Using stochastic computing to implement digital image processing algorithms," in IEEE International Conference on Computer Design, ICCD'11, 2011.

Digital Library

[6]

B. Gaines, "Stochastic computing systems," Advances in Information Systems Science, vol. 2, no. 2, pp. 37--172, 1969.

[7]

B. D. Brown and H. C. Card, "Stochastic neural computation I: Computational elements," IEEE Transactions on Computers, vol. 50, pp. 891--905, September 2001.

Digital Library

[8]

W. Qian and M. D. Riedel, "The synthesis of robust polynomial arithmetic with stochastic logic," in 45th ACM/IEEE Design Automation Conference, DAC'08, pp. 648--653, 2008.

Digital Library

[9]

A. A. Markov, "Extension of the limit theorems of probability theory to a sum of variables connected in a chain," reprinted in Appendix B of: R. Howard. Dynamic Probabilistic Systems, volume 1: Markov Chains. John Wiley and Sons, 1971.

[10]

G. Lorentz, Bernstein Polynomials. University of Toronto Press, 1953.

[11]

G. Golub and C. Van Loan, Matrix computations, vol. 3. Johns Hopkins Univ Pr, 1996.

[12]

P. Li, W. Qian, M. Riedel, K. Bazargan, and D. Lilja, "The synthesis of linear finite state machine-based stochastic computational elements," in Design Automation Conference (ASP-DAC), 2012 17th Asia and South Pacific, pp. 757--762, IEEE, 2012.

[13]

P. Li, D. J. Lilja, W. Qian, and K. Bazargan, "Using a two-dimensional finite-state machine for stochastic computation," in International Workshop on Logic and Synthesis, IWLS'12, 2012.

[14]

P. Li, W. Qian, and D. J. Lilja, "A stochastic reconfigurable architecture for fault-tolerant computation with sequential logic," in IEEE International Conference on Computer Design, ICCD'12, 2012.

Digital Library

[15]

W. Ryan, "An introduction to ldpc codess," 2003.

[16]

T. Richardson, M. Shokrollahi, and R. Urbanke, "Design of capacity-approaching irregular low-density parity-check codes," Information Theory, IEEE Transactions on, vol. 47, no. 2, pp. 619--637, 2001.

Digital Library

[17]

W. Qian, M. Riedel, K. Bazargan, and D. Lilja, "The synthesis of combinational logic to generate probabilities," in Proceedings of the 2009 International Conference on Computer-Aided Design, pp. 367--374, ACM, 2009.

Digital Library

Cited By

WAHO TKOYAMA AHAYASHI H(2024)Delta-Sigma Domain Signal Processing Revisited with Related Topics in Stochastic ComputingIEICE Transactions on Information and Systems10.1587/transinf.2023LOP0006E107.D:8(966-975)Online publication date: 1-Aug-2024
https://doi.org/10.1587/transinf.2023LOP0006
Stipčević M(2023)Biomimetic Random Pulse Computation or Why Do Humans Play Basketball Better than Robots?Biomimetics10.3390/biomimetics80805948:8(594)Online publication date: 7-Dec-2023
https://doi.org/10.3390/biomimetics8080594
Gupta SImani MSim JHuang AWu FKang JKim YRosing T(2022)COSMO: Computing with Stochastic Numbers in MemoryACM Journal on Emerging Technologies in Computing Systems10.1145/348473118:2(1-25)Online publication date: 12-Jan-2022
https://dl.acm.org/doi/10.1145/3484731
Show More Cited By

Index Terms

The synthesis of complex arithmetic computation on stochastic bit streams using sequential logic
1. Applied computing
  1. Arts and humanities
    1. Architecture (buildings)
      1. Computer-aided design
  2. Physical sciences and engineering
    1. Engineering
      1. Computer-aided design
2. Hardware
  1. Integrated circuits
    1. Logic circuits
      1. Arithmetic and datapath circuits

Recommendations

Polynomial Arithmetic Using Sequential Stochastic Logic
GLSVLSI '16: Proceedings of the 26th edition on Great Lakes Symposium on VLSI

We present the design of stochastic computing systems based on sequential logic to implement arbitrary polynomial functions. Stochastic computing is an emerging alternative computing paradigm that performs arithmetic operations on real-valued data ...
The synthesis of robust polynomial arithmetic with stochastic logic
DAC '08: Proceedings of the 45th annual Design Automation Conference

As integrated circuit technology plumbs ever greater depths in the scaling of feature sizes, maintaining the paradigm of deterministic Boolean computation is increasingly challenging. Indeed, mounting concerns over noise and uncertainty in signal values ...
A Canonical Bit-Sequential Multiplier
Lecture notes in computer science Vol. 174

A serial multiplier suitable for VLSI implementation is discussed. The multiplier accepts binary operands supplied in a serial fashion, least significant bits first. The multiplier uses a canonical cell which allows calculation of a 2k length product ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ICCAD '12: Proceedings of the International Conference on Computer-Aided Design

November 2012

781 pages

ISBN:9781450315739

DOI:10.1145/2429384

General Chair:
Alan J. Hu
Univ. of British Columbia, Vancouver, BC, Canada

Copyright © 2012 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGDA: ACM Special Interest Group on Design Automation
IEEE CEDA

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 05 November 2012

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article

Funding Sources

Division of Computing and Communication Foundations

Conference

ICCAD '12

Sponsor:

SIGDA

ICCAD '12: The International Conference on Computer-Aided Design

November 5 - 8, 2012

California, San Jose

Acceptance Rates

Overall Acceptance Rate 457 of 1,762 submissions, 26%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

48
Total Citations
View Citations
241
Total Downloads

Downloads (Last 12 months)13
Downloads (Last 6 weeks)4

Reflects downloads up to 03 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

WAHO TKOYAMA AHAYASHI H(2024)Delta-Sigma Domain Signal Processing Revisited with Related Topics in Stochastic ComputingIEICE Transactions on Information and Systems10.1587/transinf.2023LOP0006E107.D:8(966-975)Online publication date: 1-Aug-2024
https://doi.org/10.1587/transinf.2023LOP0006
Stipčević M(2023)Biomimetic Random Pulse Computation or Why Do Humans Play Basketball Better than Robots?Biomimetics10.3390/biomimetics80805948:8(594)Online publication date: 7-Dec-2023
https://doi.org/10.3390/biomimetics8080594
Gupta SImani MSim JHuang AWu FKang JKim YRosing T(2022)COSMO: Computing with Stochastic Numbers in MemoryACM Journal on Emerging Technologies in Computing Systems10.1145/348473118:2(1-25)Online publication date: 12-Jan-2022
https://dl.acm.org/doi/10.1145/3484731
He XChu Z(2022)Stochastic circuit synthesis via satisfiabilityIntegration10.1016/j.vlsi.2021.11.00384(84-91)Online publication date: May-2022
https://doi.org/10.1016/j.vlsi.2021.11.003
Hedayatpour MKarami MShamsi J(2022)Implementation of Izhikevich neuron based on stochastic computing using a novel inspired Omega‐Flip stochastic number generatorInternational Journal of Circuit Theory and Applications10.1002/cta.332250:9(3104-3118)Online publication date: 25-May-2022
https://doi.org/10.1002/cta.3322
Feng XHu KHan K(2021)MM-FSM: A High-Efficiency General Nonlinear Function Generator for Stochastic ComputationIEEE Transactions on Computers10.1109/TC.2021.3117127(1-1)Online publication date: 2021
https://doi.org/10.1109/TC.2021.3117127
Nguyen VLuong TPopovici ETrinh QZhang RNakashima Y(2021)An Accurate and Compact Hyperbolic Tangent and Sigmoid Computation Based Stochastic Logic2021 IEEE International Midwest Symposium on Circuits and Systems (MWSCAS)10.1109/MWSCAS47672.2021.9531838(386-390)Online publication date: 9-Aug-2021
https://doi.org/10.1109/MWSCAS47672.2021.9531838
Nobari MJahanirad H(2021)A Fast Approach for Deep Neural Network Implementation on FPGA2021 29th Iranian Conference on Electrical Engineering (ICEE)10.1109/ICEE52715.2021.9544450(89-93)Online publication date: 18-May-2021
https://doi.org/10.1109/ICEE52715.2021.9544450
Feng XHu KHan K(2021)A High-Efficiency General Nonlinear Function Generator for Stochastic Computation2021 IEEE 3rd International Conference on Circuits and Systems (ICCS)10.1109/ICCS52645.2021.9697288(150-155)Online publication date: 29-Oct-2021
https://doi.org/10.1109/ICCS52645.2021.9697288
Wang XChu ZQian W(2021)MinSC: An Exact Synthesis-Based Method for Minimal-Area Stochastic Circuits under Relaxed Error Bound2021 IEEE/ACM International Conference On Computer Aided Design (ICCAD)10.1109/ICCAD51958.2021.9643580(1-9)Online publication date: 1-Nov-2021
https://doi.org/10.1109/ICCAD51958.2021.9643580
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents