Probabilistic maximum error modeling for unreliable logic circuits

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: Smita Krishnaswamy , George F. Viamontes , Igor L. Markov , John P. Hayes, Accurate Reliability Evaluation and Enhancement via Probabilistic Transfer Matrices, Proceedings of the conference on Design, Automation and Test in Europe, p.282-287, March 07-11, 2005 [doi>10.1109/DATE.2005.47]
• 5: R. Iris Bahar , Joseph Mundy , Jie Chen, A Probabilistic-Based Design Methodology for Nanoscale Computation, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.480, November 09-13, 2003 [doi>10.1109/ICCAD.2003.17]
• 6: Gethin Norman , David Parker , Marta Kwiatkowska , Sandeep K. Shukla, Evaluating the Reliability of Defect-Tolerant Architectures for Nanotechnology with Probabilistic Model Checking, Proceedings of the 17th International Conference on VLSI Design, p.907, January 05-09, 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: Zhanglei Wang , Krishnendu Chakrabarty , Michael Goessel, Test set enrichment using a probabilistic fault model and the theory of output deviations, Proceedings of the conference on Design, automation and test in Europe: Proceedings, March 06-10, 2006, Munich, Germany
• 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: Jie Han , Jianbo Gao , Yan Qi , Pieter Jonker , Jose A. B. Fortes, Toward Hardware-Redundant, Fault-Tolerant Logic for Nanoelectronics, IEEE Design & Test, v.22 n.4, p.328-339, July 2005 [doi>10.1109/MDT.2005.97]
• 12: Robert G. Cowell , Steffen L. Lauritzen , A. Philip David , David J. Spiegelhalter , V. Nair , J. Lawless , M. Jordan , David J. Spiegelhater, Probabilistic Networks and Expert Systems, Springer-Verlag New York, Inc., Secaucus, NJ, 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: James D. Park , Adnan Darwiche, Approximating MAP using Local Search, Proceedings of the 17th Conference in Uncertainty in Artificial Intelligence, p.403-410, August 02-05, 2001

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Reliability, availability, and serviceability

General Terms:
Reliability

Keywords:
MAP, maximum error