Reliability Evaluation of Digital Circuits Using Probabilistic Signal Flow Graphs

Document Type : Original Article

Authors

1 Department of ICT, Niroo Research Institute, Tehran, Iran

2 Faculty of Engineering, Ferdowsi University of Mashhad, Mashhad, Iran

Abstract

Although reducing the size of transistors increased their capabilities considerably, but also resulted in more susceptibility to transient errors. Thus, detecting the sensitive nodes of digital circuits is essential for designing digital circuits at few nanometers. On the other hand, increasing the number of logic gates, transient error types and several error propagation mechanisms in digital circuits, results in considerable complexity in reliability evaluation. Thus, scalability, computational complexity, runtime, accuracy and memory consumption should be taken into account for such evaluation. In this paper, using the concept of the probabilistic signal flow graphs, a new approach is proposed to evaluate the reliability of digital circuits which demonstrates good accuracy, runtime and high level of scalability. Probabilistic evaluation of re-convergent paths, using fixed point theorem and using the sparsity of matrices are features of the proposed approach. Using the proposed approach, the reliability of circuits with feedback and sequential circuits is also evaluated. Simulation results show that the computational complexity of the proposed approach for a combinational and sequential circuit with N nodes is O(N0.85) and O(N0.99) respectively.

Keywords

References

[1]  H. T. Nguyen, Y. Yagil, N. Seifert and M. Reitsma, “Chip-level soft error estimation method,” IEEE Device and Materials Reliability, vol. 5, no. 3, pp. 365-381, Sep. 2005.
[2]  S. Borkar, “Designing reliable systems from unreliable components: the challenge of transistor variability and degradation,” IEEE Micro., vol. 25, no. 6, pp. 10–16, 2005.
[3]  R. D. Schrimpf and et al, “Reliability and radiation effects in IC technologies,” IEEE 46th Int. Reliability Physics Symp (IRPS 2008), Phoenix, pp. 97-106, May 2008.
[4]  P. Shivakumar, M. Kistler, S. W. Keckler, D. Burger and L. Alvisi,  “Modeling the effect of technology trends on the soft error rate of combinational logic,” IEEE Int. conf. on Dependable Systems and Networks (DSN 2002), Bethesda, MD, USA, pp. 389-398, June 2002.
[5]  K. Parker and E. McCluskey, “Probabilistic treatment of general combinational networks,” IEEE Trans. on Electronic Computers, vol. C-24, no. 6,  pp. 668–670, 1975.
[6]  K. N. Patel, I .L. Markov and J. P. Hayes, “Evaluating circuit reliability under probabilistic gate-level fault models,” in Int. Workshop on Logic and Synthesis (IWLS), pp. 59-64, 2003.
[7]  S. Krishnaswamy, G. F. Viamonte, I. L. Markov and J. P. Hayes, “Accurate reliability evaluation and enhancement via probabilistic transfer matrices,” in Proc. of Design Automation and Test in Europe (DATE 2005), Munich, Germany, pp. 282–287, March 2005.
[8]  S. Krishnaswamy, I. L. Markov and J. P. Hayes, “Tracking uncertainty with probabilistic logic circuit testing,” IEEE Design and Test of Computers, vol. 24, no. 4, pp. 312-321, 2007.
[9]  S. Krishnaswamy, G.F. Viamontes, I.L. Markov and J.P. Hayes, “Probabilistic transfer matrices in symbolic reliability analysis of logic circuits,” ACM Trans. Design Automation of Electronic Systems, vol. 13, no. 1, Article 8, 2008.
[10]  C. C. Yu and J. P. Hayes, “Scalable and accurate estimation of probabilistic behavior in sequential circuits,” in Proc. 28th VLSI Test Symposium (VTS 2010), Santa Cruz, CA, pp. 165-170, April 2010.
[11]  R. I. Bahar, J. Chen and J. Mundy, “A probabilistic-based design methodology for nanoscale computation,” in Proc. IEEE/ACM Int. Conf. on Computer Aided Design (ICCAD’03), San Jose, CA, pp. 480–486, Nov. 2003.
[12]  G. Norman, D. Parker, M. Kwiatkowska and S. Shukla, “Evaluating the reliability of NAND multiplexing with PRISM,” IEEE Trans. CAD of Integrated Circuits and Systems, vol. 24, no. 10, pp. 1629-1637, 2005.
[13]  N. M. Zivanov and D. Marculescu, “Multiple transient faults in combinational and sequential circuits: a systematic approach,” IEEE Trans. CAD, vol. 29, no. 10, pp. 1614-27, 2010.
[14]  N. M. Zivanov and D. Marculescu, “Circuit reliability analysis using symbolic techniques,” IEEE Trans. CAD Integrated Circuits Syst., vol. 25, no. 12, pp. 2638–2649, 2006.
[15]  N. M. Zivanov and D. Marculescu, “Modeling and optimization for soft-error reliability of sequential circuits,” IEEE Trans. CAD Integrated Circuits Syst. vol. 27, no. 5, pp. 803-816, 2008.
[16]  N. M. Zivanov and D. Marculescu, “Soft error rate analysis for sequential circuits,” in Proc. IEEE Design, Automation and Test in Europe (DATE 2007), Nice Acropolis, France, pp. 1436-1441, April 2007.
[17]  T. Rejimon and S. Bhanja, “Scalable probabilistic computing models using Bayesian networks,” in Proc. 48th Int. Midwest Symp. Circuits Syst., vol. 1, CovingtonKY, pp. 712–715, Aug. 2005.
[18]  T. Rejimon and S. Bhanja, “Probabilistic error model for unreliable nano-logic gates,” in Proc. 6th IEEE Conf. Nanotechnology, Cincinnati, Ohio, pp. 47-50, July. 2006.
[19]  T. Rejimon, K. Lingasubramanian and S. Bhanja,” Probabilistic error modeling for nano-domain logic circuits,” IEEE Trans. VLSI, vol. 17, no. 1, pp. 55–65, 2009.
[20]  H. Asadi, M. B. Tahoori, M. Fazeli and S. G. Miremadi “Efficient algorithms to accurately compute derating factors of digital circuits,” Microelectronics Reliability, vol. 52, no. 6, pp. 1215-1226, 2012.
[21]  G. Asadi and M. B. Tahoori, “An analytical approach for soft error rate estimation in digital circuits,” in Proc. Int. Symp. Circuits and Systems (ISCAS 2005), vol. 3, Kobe, Japan, pp. 2991-2994, May 2005.
[22]  H. Asadi and M. B. Tahoori, “Soft error derating computation in sequential circuits,” in Proc. Int. Conf. CAD (ICCAD’06), San Jose, CA,  pp. 497-501, Nov. 2006.
[23]  H. Asadi and M. B. Tahoori, “Soft error modeling and remediation techniques in ASIC designs,” Microelectronic, vol. 41, no. 8, pp. 506-522, 2010.
[24]  M. Fazeli, S. N. Ahmadian, S. G. Miremadi, H. Asadi and M. B. Tahoori, “Soft error rate estimation of digital circuits in the presence of multiple event transients (METs),” Proc. IEEE/ACM Int. Conf. Design Automation and Test in Europe (DATE 2011), Grenoble, France, pp. 70-75, March 2011.
[25]  N. Mohyuddin, E. Pakbaznia and M. Pedram, “Probabilistic error propagation in logic circuits using the Boolean difference calculus,” ,” in Proc. 26th Int. Conf. Computer Design (ICCD 2008), Lake Tahoe, CA, pp. 7-13, Oct. 2008.
[26]  S. Gupta, A. J. C. Gemund and R. Abreu, “Probabilistic error propagation modeling in logic circuits,” in Proc. 4th Software Testing, Verification and Validation Workshops (ICSTW 2011), Berlin, Germany, pp. 617-623, March 2011.
[27]  A. Abdollahi, “Probabilistic decision diagrams for exact probabilistic analysis,” Int. conf. on CAD (ICCAD'07), San Jose, California, pp. 266-272, Nov. 2007.
[28]  G. B. Hamad, S. R. Hasan, O. A. Mohamed and Y. Savaria, “Characterizing, modeling, and analyzing soft error propagation in asynchronous and synchronous digital circuits,” Microelectronics Reliability, vol. 55, no. 1, pp. 238-250, 2015.
[29]  J. Han, E. Taylor, J. Gao and J. Fortes, “Towards accurate and efficient reliability modeling of nanoelectronic circuits,” in Proc. 6th IEEE Conf. Nanotechnology, Cincinnati, Ohio, pp. 395-398, July 2006.
[30]  J. Han, H. Chen, E. Boykin and J. Fortes, “Reliability evaluation of logic circuits using probabilistic gate models,” Microelectronics Reliability, vol. 51, no. 2, pp. 468-476, 2011.
[31]  D. T. Franco, M. C. Vasconcelos, L. Naviner and J-F. Naviner, “Signal probability for reliability evaluation of logic circuits,” Microelectronics Reliability, vol. 48, no. 8-9, pp. 1586–1591, 2008.
[32]  J. T. Flaquer, J. M. Daveau, L. Naviner and P. Roche, “Fast  reliability analysis of combinatorial logic circuits using conditional probabilities,” Microelectronics Reliability, vol. 50, no. 9-11, pp. 1215-1218, 2010.
[33]  J. T. Flaquer, J. M. Daveau, L. Naviner and P. Roche, “An approach to reduce computational cost in combinatorial logic netlist reliability analysis using circuit clustering and conditional probabilities,” in Proc. 17th IEEE Int. On-line Testing Symposium (IOLTS 2011), Athens, pp. 98-103, July 2011.
[34]  S. Krishnaswamy, S. M. Plaza, I. L. Markov and J. P. Hayes, “Signature-based SER analysis and design of logic circuits,” IEEE Trans. CAD Integrated Circuits Syst., vol. 28, no. 1, pp. 74–86, 2009.
[35]  H. Chen, J. Han and F. Lombardi, “A transistor-level stochastic approach for evaluating the reliability of digital nanometric CMOS circuits,”IEEE Int. Symp. Defect and Fault Tolerance in VLSI and Nanotechnology Systems (DFT 2011), Vancouver, BC, Canada, pp. 60-67, Oct. 2011.
[36]  J. Han, H. Chen, J. Liang, P. Zhu, Z. Yang and F. Lombardi, “A stochastic computational approach for accurate and efficient reliability evaluation,” IEEE Trans. Computers, vol. 63, no. 6, pp. 1336–1350, 2014.
[37]  M. R. Choudhury and K. Mohanram, “Reliability analysis of logic circuits,” IEEE Trans. CAD. Integrated Circuits Syst., vol. 28, no. 3, pp. 392-405, 2009.
[38]  S. J. S. Mahdavi and K. Mohammadi, “SCRAP: sequential circuits reliability analysis program,” Microelectronics Reliability, vol. 49, no. 8, pp. 924–933, 2009.
[39]  C. C. Yu and J. P. Hayes, “Trigonometric method to handle realistic error probabilities in logic circuits,” in Proc. IEEE Design, Automation and Test in Europe (DATE 2011), Grenoble, France, pp. 64-69, March 2011.
[40]  B. Liu and L. Cai, “Reliability evaluation for single event transients on digital circuits,” IEEE Trans. Reliability, vol. 61, no. 3, pp. 687-691, 2012.
[41]  L. Chen and M. B. Tahoori, “An efficient probability framework for error propagation and correlation estimation,” 18th IEEE Int. On-Line Testing Symposium (IOLTS 2012), Sitges, Spain, pp. 170-175, June 2012.
[42]  L. Chen, M. Ebrahimi and M.B. Tahoori, “CEP: Correlated error propagation for hierarchical soft error analysis,” J Electron Testing, Springer, vol. 29, pp. 143–158, 2013.
[43]  R. R. Rao, K. Chopra, D. T. Blaauw and D. M. Sylvester, “Computing the soft error rate of combinational logic circuit using parameterized descriptors,” IEEE Trans. CAD Integrated Circuits Syst., vol. 26, no. 3, pp. 468-479, 2007.
[44]  C. Zhao, X. Bai and S. Dey, “Evaluating transient error effects in digital nanometer circuits,” IEEE Trans. Reliability, vol. 56, no. 3, pp. 381-391, 2007.
[45]  R. Rajaraman, J. S. Kim, N. Vijaykrishnan, Y. Xie and M. J. Irwin, “SEAT-LA: a soft error analysis tool for combinational logic,” Proc. 19th Int. Conf. on VLSI Design, Hyderabad, India, pp. 499-502, Jan. 2006.
[46]  M. Omana, G. Papasso, D. Rossi and C. Metra, “A model for transient fault propagation in combinatorial logic,” in Proc. 9th Int. On-Line Testing Symp. (IOLTS 2003), Bologna, Italy, pp. 111-115, July 2003.
[47]  B. S. Gill, C. Papachristou, F. G. Wolff and N. Seifert, “Node sensitivity analysis for soft errors in CMOS logic,” Proc. Test Conf. (ITS 2005), Austin, Tx, pp. 984–972, Nov. 2005.
[48]  S. Gangadhar and S. Tragoudas, “A probabilistic approach to diagnose SETs in sequential circuits,” Electron Testing, Springer, vol. 29, no. 3, pp 317-330, 2013.
[49]  S. Rezaei, S. G. Miremadi, H. Asadi and M. Fazeli, “Soft error estimation and mitigation of digital circuits by characterizing input patterns of logic gates,” Microelectronics Reliability, vol. 54, no. 6-7, pp 1412-1420, 2014.
[50]  M. S. Ansari, A. Mahani, J. Han and B. F. Cockburn, “A novel gate grading approach for soft error tolerance in combinational circuits,” IEEE Canadian Conference on Electrical and Computer Engineering Conf. (CCECE 2016), Vancouver, Canada, pp. 1-4, May 2016.
[51]  B. Farahani, S. Habibi and S. Safari, “A cross-layer SER analysis in the presence of PVTA variations,” Microelectronics Reliability, vol. 55, no. 7, pp. 1013-1027, 2015.F. K. Lodhi, S. R. Hasan, O. Hasan and F. Awwad, “Analyzing Vulnerability of Asynchronous Pipeline to Soft Errors: Leveraging Formal Verification,” Electronic Testing, vol. 32, no. 5, pp. 569-586, 2016.
[52]  M. Ebrahimi, H. Asadi, R. Bishnoi and M. B. Tahoori, “Layout-based modeling and mitigation of multiple event transients,” IEEE Trans. on CAD. Integrated Circuits Syst., vol. 35, no. 3, pp. 367-379, 2016.
[53]  Y. Du and S. Chen, “A novel layout-based single event transient injection approach to evaluate the soft error rate of large combinational circuits in complimentary metal-oxide-semiconductor bulk technology,” IEEE Trans. on Reliability, vol. 65, no. 1, pp. 248-255, 2016.
[54]  M. Raji, H. Pedram and B. Ghavami, “Soft error rate estimation of combinational circuits based on vulnerability analysis,” IET Computers & Digital Techniques, vol. 9, no. 6, pp. 311-320, 2015.
[55]  محمدامین ثابت سروستانی، بهنام قوامی، محسن راجی، «کاهش نرخ خطای نرم چندگانه مدارهای ترکیبی مبتنی بر اندازه‌گذاری دروازه‌ها بر مبنای پارامتر حساسیت»، مجله مهندسی برق دانشگاه تبریز، دوره 47، شماره 2، صفحات 445 تا 454، تابستان 1396.
[56]  سعیده نبی‌پور، جواد جاویدان، غلامرضا زارع فتین، «طراحی یک دیکدر BCH  بهینه جهت افزایش اطمینان در ذخیره‌سازی اطلاعات و تصحیح خطا در حافظه‌های فلش»، مجله مهندسی برق دانشگاه تبریز، دوره 46، شماره 3، صفحات 319 تا 331، پاییز 1396.
[57]  V. H. Vaghef and A. Peiravi, “A graph based approach for reliability analysis of nano-scale VLSI logic circuits,” Microelectronics Reliability, vol. 54, no. 6-7, pp. 1299-1306, 2014.
[58]  V. H. Vaghef and A. Peiravi, “Node-to-node error sensitivity analysis using a graph based approach for VLSI logic circuits,” Microelectronics Reliability, vol. 55, no. 1, pp. 264-271, 2015.
[59]  T.A. Davis, “Direct methods for sparse linear systems,” Philadelphia, SIAM, 2006.
[60]  J. V. Neumann, “Probabilistic logics and the synthesis of reliable organisms from unreliable components,” In: Shannon CE, McCarthy J, editors. Automata studies. Princeton (NJ): PrincetonUniversity Press, pp. 43–98, 1956.
[61]  M. E. Van Valkenburg, “Network analysis,” Englewood Cliffs, NJ, Prentice-Hall, 1974.
[62]  S. J. Mason, “Feedback theory – some properties of signal flow graphs,” in Proc. of IRE, vol. 41, no.9, New York, pp. 1144-1156, 1953.
[63]  S. J. Mason, “Feedback theory: further properties of signal flow graphs,” in Proc. IRE, vol. 44, no.7, New York, pp. 920-926, 1956.
[64]  L. E. J. Brouwer, “Ueber eineindeutige, stetige transformationen von flachen in sich,” in Springer Mathematische Annalen, vol. 69, no. 2, pp. 176-180, 1910.
[65]  S. Banach, “Sur les opérations dans les ensembles abstraits et leur application aux équations integrals,” Fundamenta Mathematicae, vol. 3, no.1, pp. 133-181, 1922.

Files

Share

How to cite

Statistics