skip to main content
research-article

Probabilistic transfer matrices in symbolic reliability analysis of logic circuits

Published: 06 February 2008 Publication History

Abstract

We propose the probabilistic transfer matrix (PTM) framework to capture nondeterministic behavior in logic circuits. PTMs provide a concise description of both normal and faulty behavior, and are well-suited to reliability and error susceptibility calculations. A few simple composition rules based on connectivity can be used to recursively build larger PTMs (representing entire logic circuits) from smaller gate PTMs. PTMs for gates in series are combined using matrix multiplication, and PTMs for gates in parallel are combined using the tensor product operation. PTMs can accurately calculate joint output probabilities in the presence of reconvergent fanout and inseparable joint input distributions. To improve computational efficiency, we encode PTMs as algebraic decision diagrams (ADDs). We also develop equivalent ADD algorithms for newly defined matrix operations such as eliminate_variables and eliminate_redundant_variables, which aid in the numerical computation of circuit PTMs. We use PTMs to evaluate circuit reliability and derive polynomial approximations for circuit error probabilities in terms of gate error probabilities. PTMs can also analyze the effects of logic and electrical masking on error mitigation. We show that ignoring logic masking can overestimate errors by an order of magnitude. We incorporate electrical masking by computing error attenuation probabilities, based on analytical models, into an extended PTM framework for reliability computation. We further define a susceptibility measure to identify gates whose errors are not well masked. We show that hardening a few gates can significantly improve circuit reliability.

References

[1]
Alexandrescu, D., Anghel, L., and Nicolaidis, M. 2002. New methods for evaluating the impact of single event transients in VDSM ICs. In Proceedings of the IEEE Symposium on Defect and Fault Tolerance in VLSI Systems. 99--107.
[2]
Bahar, R. I., Mundy, J., and. Chan, J. 2003. A probabilistic-based design methodology for nanoscale computation. In Proceedings of the International Conference on Computer-Aided Design. 480--486.
[3]
Bahar, R. I., Frohm, E. A., Gaona, C. M., Hachtel, G. D., Macii, E., Pardo, A. and Somenzi, F. 1993. Algebraic decision diagrams and their applications. In Proceedings of the International Conference on Computer-Aided Design. 188--191.
[4]
Brglez, F., Pownall, P., and Hum, R. 1984. Applications of testability analysis: From ATPG to critical delay path tracing. In Proceedings of the International Test Conference. 705--712.
[5]
Bryant, R. E. 1986. Graph-based algorithms for Boolean function manipulation. IEEE Trans. Comput. 35, 677--691.
[6]
Chow, C. and Liu, C. 1968. Approximating discrete probability distributions with dependence trees. IEEE Trans. Inform. Theo. 14, 11, 462--467.
[7]
Clarke, E., Fujita, M., and Zhao, X. 1996. Multi-terminal binary decision diagrams and hybrid decision diagrams. In Representations of Discrete Functions, T. Sasao and M. Fujita, Eds., Kluwer Academic Publishers, 93--108.
[8]
Cormen, T., Lieserson, C., Rivest, R., and Stein, C. 2001. Introduction to Algorithms. MIT Press, 331--338.
[9]
Dhillon, Y. S., Diril, A. U., and Chatterjee, A. 2005. Soft-error tolerance analysis and optimization of nanometer circuits. In Proceedings of the Conference on Design and Test in Europe. 288--293.
[10]
Egner, S., Püschel, M., and Beth, T. 1997. Decomposing a permutation into a conjugated tensor product. In Proceedings of the International Symposium on Symbolic and Algebraic Computation. 101--108.
[11]
Ercolani, S., Favalli, M., Damiani, M., Olivio, P., and Rico, B. 1989. Estimate of signal probability in combinational logic networks. In Proceedings of the European Test Conference. 132--38.
[12]
Hachtel, G. and Somenzi, F. 1996. Logic Synthesis and Verification Algorithms. Kluwer Academic Publishers, Boston, MA.
[13]
Han, J. and. Jonker, P. 2002. A system architecture solution for unreliable nanoelectronic devices. IEEE Trans. Nanotech. 1, 201--208.
[14]
Hinton, A. and Kwiatkowska, M. 2006. PRISM: A tool for automatic verification of probabilistic systems. Lecture Notes in Computer Science. vol. 3920, 441--444.
[15]
Jain, J., Bitner, J., Fussell, D. S., and Abraham, J. A. 1992. Functional partitioning for verification and related problems. In Proceedings of the Brown MIT VLSI Conference. 210--226.
[16]
Jain, J., Bitner, J., Abadir, M. S., Abraham, J. A., and Fussel, D. S. 1997. Indexed BDDs: Algorithmic advances in techniques to represent and verify Boolean functions. IEEE Trans. Comput. 46, 11, 1230--1245.
[17]
Krishnaswamy, S., Markov, I. L., and Hayes, J. P. 2005. Testing logic circuits for transient faults. In Proceedings of the European Test Symposium. 102--107.
[18]
Krishnaswamy, S., Viamontes, G. F., Markov, I. L., and Hayes, J. P. 2005. Accurate reliability evaluation and enhancement via probabilistic transfer matrices. In Proceedings of the Conference on Design Automation and Test in Europe. 282--287.
[19]
S. Kullback, S. and Leibler, R. A. 1951. On information and sufficiency. Annals of Math. Stat. 22, 1, 79--86.
[20]
Levin, V. L. 1964. Probability analysis of combination systems and their reliability. Engin. Cybern. 6, 78--84.
[21]
Malvestuto, F. M. 1991. Approximating discrete probability distributions with decomposable models. IEEE Trans. Syst. Man, Cybern. 21, 5, 1287--1894.
[22]
Miskov-Zivanov, N. and Marculescu, D. 2006. MARS-C: Modeling and reduction of soft errors in combinational circuits. In Proceedings of the Design Automation Conference. 767--772.
[23]
Mohanram, K. and Touba, N. A. 2003. Cost-effective approach for reducing soft error failure rate in logic circuits. In Proceedings of the International Test Conference. 893--901.
[24]
Mohanram, K. 2005. Simulation of transients caused by single-event upsets in combinational logic. In Proceedings of the International Test Conference.
[25]
Norman, G., Parker, D., Kwiatkowska, M., and Shukla, S. 2005. Evaluating the reliability of NAND multiplexing with PRISM. IEEE Trans. Comput.-Aid. Des. Integ. Circ. Sys. 24, 10, 1629--1637.
[26]
Omana, M., Papasso, G., Rossi, D., and Metra, C. 2003. A model for transient fault propagation in combinatorial logic. In Proceedings of the International Online Testing Symposium. 111--115.
[27]
Parker, K. P. and McCluskey, E. J. 1975. Probabilistic treatment of general combinational networks. IEEE Trans. Comput. 24, 6, 668--670.
[28]
Patel, K. N., Hayes, J. P., and Markov, I. L. 2003. Evaluating circuit reliability under probabilistic gate-level fault models. In Proceedings of the International Workshop on Logic and Synthesis. 59--64.
[29]
Pippenger, N. 1998. Reliable computation by formulas in the presence of noise. IEEE Trans. Inform. Theo. 34, 2, 194--197.
[30]
Savir, J., Ditlow, G., and Bardell, P. H. 1983. Random pattern testability. In Proceedings of the IEEE Symposium on Fault Tolerant Computing. 80--89.
[31]
Shivakumar, P., Kistler, M., Keckler, S. W., Burger, D., and Alvisi, L. 2002. Modeling the effect of technology trends on soft error rate of combinational logic. In Proceedings of the International Conference on Dependable Systems and Networks. 389--398.
[32]
Srinivasan, R., Gupta, S. K., and Breuer, M. A. 1993. An efficient partitioning strategy for pseudo-exhaustive testing. In Proceedings of the Design Automation Conference. 242--248.
[33]
Viamontes, G. F., Markov, I. L., and Hayes, J. P. 2003. Improving gate-level simulation of quantum circuits. Quant. Inform. Proces. 2, 5, 347--380.
[34]
Viamontes, G. F., Rajagopalan, M., Markov, I. L., and Hayes, J. P. 2003. Gate-level simulation of quantum circuits. In Proceedings of the Asia and South Pacific Design Automation Conference. 295--301.
[35]
von Neumann, J. 1956. Probabilistic logics and synthesis of reliable organisms from unreliable components. In Automata Studies, C.E. Shannon and J. McCarthy Eds., Princeton University Press, 43--98.
[36]
Zhang, B., Wang, W. S., and Orshansky, M. 2006. FASER: Fast analysis of soft error susceptibility for cell-based designs. In Proceedings of the International Symposim on Quality Electronic Design. 755--760.
[37]
Zhang, M. and Shanbhag, N. R. 2004. A soft error rate analysis (SERA) methodology. In Proceedings of the International Conference on Computer Aided Design. 111--118.
[38]
Zhao, C., Bai, X., and Dey, S. 2004. A scalable soft spot analysis methodology for compound noise effects in nano-meter circuits. In Proceedings of the Design Automation Conference. 894--899.

Cited By

View all
  • (2025)Fanout-Based Reliability Model for SER Estimation in Combinational CircuitsIEEE Transactions on Circuits and Systems I: Regular Papers10.1109/TCSI.2024.345886472:1(228-240)Online publication date: Jan-2025
  • (2024)An Effective Fanout-Based Method for Improving Error Propagation Probability Estimation in Combinational CircuitsIEEE Access10.1109/ACCESS.2024.336851212(35172-35183)Online publication date: 2024
  • (2024)Fault Tolerant ArchitecturesHandbook of Computer Architecture10.1007/978-981-97-9314-3_11(277-320)Online publication date: 21-Dec-2024
  • Show More Cited By

Index Terms

  1. Probabilistic transfer matrices in symbolic reliability analysis of logic circuits

        Recommendations

        Comments

        Information & Contributors

        Information

        Published In

        cover image ACM Transactions on Design Automation of Electronic Systems
        ACM Transactions on Design Automation of Electronic Systems  Volume 13, Issue 1
        January 2008
        496 pages
        ISSN:1084-4309
        EISSN:1557-7309
        DOI:10.1145/1297666
        Issue’s Table of Contents
        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]

        Publisher

        Association for Computing Machinery

        New York, NY, United States

        Journal Family

        Publication History

        Published: 06 February 2008
        Accepted: 01 July 2007
        Revised: 01 March 2007
        Received: 01 June 2006
        Published in TODAES Volume 13, Issue 1

        Permissions

        Request permissions for this article.

        Check for updates

        Author Tags

        1. Symbolic analysis
        2. fault tolerance

        Qualifiers

        • Research-article
        • Research
        • Refereed

        Funding Sources

        Contributors

        Other Metrics

        Bibliometrics & Citations

        Bibliometrics

        Article Metrics

        • Downloads (Last 12 months)15
        • Downloads (Last 6 weeks)0
        Reflects downloads up to 15 Feb 2025

        Other Metrics

        Citations

        Cited By

        View all
        • (2025)Fanout-Based Reliability Model for SER Estimation in Combinational CircuitsIEEE Transactions on Circuits and Systems I: Regular Papers10.1109/TCSI.2024.345886472:1(228-240)Online publication date: Jan-2025
        • (2024)An Effective Fanout-Based Method for Improving Error Propagation Probability Estimation in Combinational CircuitsIEEE Access10.1109/ACCESS.2024.336851212(35172-35183)Online publication date: 2024
        • (2024)Fault Tolerant ArchitecturesHandbook of Computer Architecture10.1007/978-981-97-9314-3_11(277-320)Online publication date: 21-Dec-2024
        • (2023)Logic Circuits Reliability Analysis using Signal Probability and Bayesian Network ConceptsRecent Advances in Electrical & Electronic Engineering (Formerly Recent Patents on Electrical & Electronic Engineering)10.2174/235209651566622092912072116:1(66-77)Online publication date: Feb-2023
        • (2023)A Framework for Reliability Analysis of Combinational Circuits Using Approximate Bayesian InferenceIEEE Transactions on Very Large Scale Integration (VLSI) Systems10.1109/TVLSI.2023.323788531:4(543-554)Online publication date: 1-Apr-2023
        • (2023)Mitigating the Correlation Problem in Multi-Layer Stochastic Circuits2023 IEEE International Conference on Rebooting Computing (ICRC)10.1109/ICRC60800.2023.10386939(1-10)Online publication date: 5-Dec-2023
        • (2023)A Model For Probabilistic Fault Propagation with the Approach of Effective Fanouts in the Logic Circuits2023 31st International Conference on Electrical Engineering (ICEE)10.1109/ICEE59167.2023.10334701(1-6)Online publication date: 9-May-2023
        • (2023)Fault Tolerant ArchitecturesHandbook of Computer Architecture10.1007/978-981-15-6401-7_11-1(1-44)Online publication date: 17-Feb-2023
        • (2022)Multibit Full Comparator Logic in Quantum-Dot Cellular AutomataIEEE Transactions on Circuits and Systems II: Express Briefs10.1109/TCSII.2022.319356169:11(4508-4512)Online publication date: Nov-2022
        • (2022)Probability Distribution Calculations with Stochastic Circuits2022 56th Asilomar Conference on Signals, Systems, and Computers10.1109/IEEECONF56349.2022.10052003(1-5)Online publication date: 31-Oct-2022
        • Show More Cited By

        View Options

        Login options

        Full Access

        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