skip to main content
10.1145/1228784.1228842acmconferencesArticle/Chapter ViewAbstractPublication PagesglsvlsiConference Proceedingsconference-collections
Article

Probabilistic maximum error modeling for unreliable logic circuits

Published: 11 March 2007 Publication History

Abstract

Reliability modeling and evaluation is expected to be one of the major issues in emerging nano-devices and beyond 22nm CMOS. Such devices would have inherent propensity for gate failures due to the underlying device variabilities. Many of these failures would be transient in nature, necessitating the need for probabilistic logic base danalysis. Current research in this area is concerned with computing error bounds, but they do not account for circuits structures or are usually derived for specific logic gate types. In addition, the usual focus is on computing the average error behavior. In this work, we propose an exact probabilistic error model to compute the maximum error in a circuit-specific manner and can handle various types of logical components in the same circuit. We model the error estimation problem as a maximum a posteriori estimate (MAP) over the joint error probability function of the entire circuit. Using this model, we can not only compute the maximum error, but can also identify the input vector that cause the maximum output error. We demonstrate this model using MCNC and ISCAS circuits. We observe that for some circuits, maximum error probabilities are significantly larger than the average likelihood error, thus making acase for the consideration of maximum error metric as an essential design guideline rather than just average-case estimates. We also find that the error estimates depend on the specific circuit structure. Lastly, we observe that the maximum error probabilities are sensitive to the individual gate failure probabilities.

References

[1]
J. von Neumann, "Probabilistic logics and the synthesis of reliable organisms from unreliable components," in Automata Studies (C. E. Shannon and J. McCarthy, eds.), pp. 43--98, Princeton Univ. Press, Princeton, N.J., 1954.
[2]
"Sensitivity Analysis, Modeling, Inference and More" URL http://reasoning.cs.ucla.edu/samiam/
[3]
K. Nikolic, A. Sadek, and M. Forshaw, "Fault-tolerant techniques for nanocomputers," Nanotechnology, vol. 13, pp. 357--362, 2002.
[4]
S. Krishnaswamy, G. S. Viamontes, I. L. Markov, and J. P. Hayes, "Accurate Reliability Evaluation and Enhancement via Probabilistic Transfer Matrices," Design Automation and Test in Europe (DATE), March 2005.
[5]
R. Iris Bahar, J. Mundy, and J. Chan, "A Probabilistic Based Design Methodology for Nanoscale Computation", International Conference on Computer Aided Design, 2003.
[6]
G. Noman, D. Parker, M. Kwiatkowska and S. K. Shukla, "Evaluating the reliability of defect-tolerant architectures for nanotechnology with probabilistic model checking", International Conference on VLSI Design, 2004.
[7]
T. Rejimon and S. Bhanja, "Scalable Probabilistic Computing Models using Bayesian Networks," IEEE Midwest Symposium on Circuits and Systems, pp. 712--715, July 2005.
[8]
Z. Wang, K. Chakrabarty and M. Goessel, "Test Set Enrichment using a Probabilistic Fault Model and the Theory of Output Deviations," Design, Automation and Test in Europe(DATE), pp. 1--6, 2006.
[9]
W. Evans and N. Pippenger, "On the Maximum Tolerable Noise for Reliable Computation by Formulas" IEEE Transactions on Information Theory, vol. 44--3 pp. 1299--1305, 1998.
[10]
S. Roy and V. Beiu, "Majority Multiplexing-Economical Redundant Fault-tolerant Designs for Nano Architectures" IEEE Transactions on Nanotechnology, vol. 4-4 pp. 441--451, 2005.
[11]
J. Han, J. B. Gao, P. Jonker, Yan Qi and J.A.B. Fortes, "Toward hardware-Redundant Fault-Tolerant Logic for Nanoelectronics" IEEE Transactions on Design and Test of Computers, vol. 22--4 pp. 328--339, July-Aug. 2005.
[12]
R. G. Cowell, A. P. David, S. L. Lauritzen, D. J. Spiegelhalter, "Probabilistic Networks and Expert Systems," Springer-Verlag New York, Inc., 1999.
[13]
J. D. Park and A. Darwiche, "Solving MAP Exactly using Systematic Search," Proceedings of the 19th Annual Conference on Uncertainty in Artificial Intelligence, 2003.
[14]
J. D. Park and A. Darwiche, "Approximating MAP using Local Search," Proceedings of 17th Annual Conference on Uncertainty in Artificial Intelligence, pp. 403--410, 2001.

Cited By

View all
  • (2018)Towards Formal Evaluation and Verification of Probabilistic DesignIEEE Transactions on Computers10.1109/TC.2018.280743167:8(1202-1216)Online publication date: 1-Aug-2018
  • (2017)Fault Sensitive Neutralization of Hardware Trojans Using Multi-level Triple Modular Redundancy Scheme2017 IEEE International Symposium on Nanoelectronic and Information Systems (iNIS)10.1109/iNIS.2017.31(105-110)Online publication date: Dec-2017
  • (2013)Probabilistic modeling approaches for nanoscale devices2013 International Conference on Circuits, Power and Computing Technologies (ICCPCT)10.1109/ICCPCT.2013.6528997(720-724)Online publication date: Mar-2013
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
GLSVLSI '07: Proceedings of the 17th ACM Great Lakes symposium on VLSI
March 2007
626 pages
ISBN:9781595936059
DOI:10.1145/1228784
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

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 11 March 2007

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. MAP
  2. maximum error

Qualifiers

  • Article

Conference

GLSVLSI07
Sponsor:
GLSVLSI07: Great Lakes Symposium on VLSI 2007
March 11 - 13, 2007
Stresa-Lago Maggiore, Italy

Acceptance Rates

Overall Acceptance Rate 312 of 1,156 submissions, 27%

Upcoming Conference

GLSVLSI '25
Great Lakes Symposium on VLSI 2025
June 30 - July 2, 2025
New Orleans , LA , USA

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)4
  • Downloads (Last 6 weeks)0
Reflects downloads up to 27 Jan 2025

Other Metrics

Citations

Cited By

View all
  • (2018)Towards Formal Evaluation and Verification of Probabilistic DesignIEEE Transactions on Computers10.1109/TC.2018.280743167:8(1202-1216)Online publication date: 1-Aug-2018
  • (2017)Fault Sensitive Neutralization of Hardware Trojans Using Multi-level Triple Modular Redundancy Scheme2017 IEEE International Symposium on Nanoelectronic and Information Systems (iNIS)10.1109/iNIS.2017.31(105-110)Online publication date: Dec-2017
  • (2013)Probabilistic modeling approaches for nanoscale devices2013 International Conference on Circuits, Power and Computing Technologies (ICCPCT)10.1109/ICCPCT.2013.6528997(720-724)Online publication date: Mar-2013
  • (2013)Performance analysis on road sign detection, extraction and recognition techniques2013 International Conference on Circuits, Power and Computing Technologies (ICCPCT)10.1109/ICCPCT.2013.6528996(1167-1173)Online publication date: Mar-2013
  • (2011)Maximum error modeling for fault-tolerant computation using maximum a posteriori (MAP) hypothesisMicroelectronics Reliability10.1016/j.microrel.2010.07.15651:2(485-501)Online publication date: Mar-2011
  • (2009)An Error Model to Study the Behavior of Transient Errors in Sequential CircuitsProceedings of the 2009 22nd International Conference on VLSI Design10.1109/VLSI.Design.2009.73(485-490)Online publication date: 5-Jan-2009
  • (2007)Probabilistic error modeling for sequential logic2007 7th IEEE Conference on Nanotechnology (IEEE NANO)10.1109/NANO.2007.4601266(616-620)Online publication date: Aug-2007

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media