Reliability Analysis of Sequential Logic Circuits Using Signal Flow Graphs

Vahid Hamiyati Vaghef, Ali Peiravi

Abstract

As the transistor sizes shrunk in advanced VLSI circuits recently, their susceptibility to the transient faults significantly has been increased which makes the reliability analysis of logic circuits more important. However, the reliability analysis of logic circuits is high computational complexity, because of multiple simultaneous errors, propagating the errors, masking mechanisms, re-convergent paths, etc. This figure becomes even more complicated in sequential circuits due to the feedback loops, where errors may store in flip-flops and re-enter the circuit. Moreover, it is essential to consider the waveform of errors in sequential circuits into account, which makes it more complex. This paper proposes a fast and scalable approach using probabilistic signal flow graphs to analyze the reliability of sequential logic circuits in the presence of multiple event transients. The proposed approach is based on nonlinear probabilistic graphs to find the probability of error for each gate after passing the circuit for an infinite number of clock cycles. Also, the proposed approach introduces a probability distribution function model to propagate the waveform of errors in the circuit to consider all masking mechanisms. Also, the proposed approach benefits from scalable runtime and memory requirements. Based on the simulation results, the proposed approach exhibits the computational complexity of.

Keywords

Sequential logic circuits, Transient faults, Probabilistic signal flow graph, Matrix sparsity, Mason’s rule

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, NSP. 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] 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.
[4] 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.
[5] 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.
[6] 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.
[7] 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.
[8] 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.
[9] 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.
[10] B. S. Gill, C. Papachristou, F. G. Wolff and N. Seifert, “Node sensitivity analysis for soft errors in CMOS logic,” Proc. Test Conf, 2005 (ITS 2005), Austin, TX, pp. 984–972, Nov. 2005.
[11] 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.
[12] 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.
[13] T. Rejimon and S. Bhanja, “Scalable probabilistic computing models using Bayesian networks,” in Proc. 48th Int. Midwest Symp. Circuits Syst., vol. 1, Covington KY, pp. 712–715, Aug. 2005.
[14] T. Rejimon and S. Bhanja, “Probabilistic error model for unreliable nano-logic gates,” in Proc. 6th IEEE Nano., vol. 1, Cincinnati, Ohio, pp. 47-50, July. 2006.
[15] 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.
[16] 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, 2005.
[17] 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.
[18] 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, pp. 617-623, March 2011.
[19] M. Fazeli, S. N. Ahmadian, S. G. Miremadi, H. Asadi, 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.
[20] H. Asadi, M. B. Tahoori, “Soft error modeling and remediation techniques in ASIC designs,” Microelectronic, vol. 41, no. 8, pp. 506-522, 2010.
[21] 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.
[22] 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, 2006.
[23] 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.
[24] 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.
[25] 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.
[26] 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.
[27] 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.
[28] S. J. Seyyed Mahdavi and K. Mohammadi, “Improved single-pass approach for reliability analysis of digital combinational circuits,” Microelectronics Reliability, vol. 51, no. 2, pp. 477-484, 2011.
[29] 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.
[30] H. Chen and J. Han, “Stochastic computational models for accurate reliability evaluation of logic circuits,” in Proc. 20th Great Lakes Symp. VLSI (GLSVLSI 2010), vol. 10, Providence, Rhode Island, pp. 61–68, 2010.
[31] 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.
[32] 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.
[33] L. Chen, M. Ebrahimi, M.B. Tahoori, “CEP: Correlated error propagation for hierarchical soft error analysis,” J Electron Testing, Springer, vol. 29, pp. 143–158, 2013.
[34] 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.
[35] A. Evans, D. Alexandrescu, E. Costenaro, L. Chen, “Hierarchical RTL-based combinatorial SER estimation,” in Proc. 19th Int. On-Line Testing Symp. (IOLTS 2013), Crete, Greece, pp. 139-144, July 2013.
[36] S.N. Pagliarini, A. B. Dhia, L. A. B. Naviner and J.-F. Naviner, “Snap: A novel hybrid method for circuit reliability assessment under multiple faults,” Microelectronics Reliability, vol. 53, no. 911, pp. 1230–1234, 2013.
[37] 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.
[38] H. Pahlevanzadeh, Q. Yu, “A new analytical model of SET latching probability for circuits experiencing single or multiple-cycle single-event transients,” Electron Testing, Springer, vol. 30, no. 5, pp. 595-609, 2014.
[39] M. S. Ansari, A. Mahani, J. Han and B. F. Cockburn, “A novel gate grading approach for soft error tolerance in combinational circuits,” IEEE Conf. Electrical and Computer Engineering, Vancouver, Canada, pp. 1-4, May 2016.
[40] 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.
[41] 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.
[42] B. Ghavami, M. Raji, K. Saremi, H. Pedram, “An Incremental Algorithm for Soft Error Rate Estimation of Combinational Circuits,” IEEE Trans. on Device and Materials Reliability, vol. 18, no. 3, pp. 463-473, 2018.
[43] W. Ibrahim, H. Ibrahim, “Multithreaded and Reconvergent Aware Algorithms for Accurate Digital Circuits Reliability Estimation,” IEEE Trans. Reliability, vol. 68, no. 2, pp. 514-525, 2019.
[44] V. H. Vaghef, 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.
[45] V. H. Vaghef, 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.
[46] 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.
[47] 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, Apr. 2010.
[48] K. Lingasubramanian and S. Bhanja,"Probabilistic error modeling for sequential logic," in Proc. 7th IEEE Conf. Nanotechnology, Hong Kong, China, pp. 616-620, Aug. 2007.
[49] J. Monteiro, S. Devadas, B. Lin, “A methodology for efficient estimation of switching activity in sequential logic circuits,” in Proc. 31st Conf. Design Automation (DAC), San Diego, CA, pp. 12-17, June1994.
[50] J. Monteiro and S. Devadas “Power Estimation for Sequential Circuits,” Computer-aided design techniques for low power sequential logic circuits, Springer, pp. 35-80, 1997.
[51] C-Y Tsui, M. Pedram and A. M. Despain, “Exact and approximate methods for calculating signal and transition probabilities in FSMs,” in Proc. 31st Conf. Design Automation (DAC), San Diego, CA, USA, pp. 18-23, June1994.
[52] S. J. S. Mahdavi and K. Mohammadi, “SCRAP: sequential circuits reliability analysis program,” Microelectronics Reliability, vol. 49, no. 8, pp. 924–933, 2009.
[53] T.A. Davis, “Direct methods for sparse linear systems,” Philadelphia, SIAM, 2006.
[54] P. Shivakumar, M. Kistler, S. W. Keckler, D. Burger, L. Alvisi, “Modeling the effect of technology trends on the soft error rate of combinational logic,” Int. conf. on Dependable Systems and Networks (DSN 2002), Bethesda, MD, USA, pp. 389-398, June 2002.
[55] M. E. Van Valkenburg, “Network analysis,” Englewood Cliffs, NJ:Prentice-Hall, 1974.
[56] 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.
[57] S. J. Mason, “Feedback theory: further properties of signal flow graphs,” in Proc. IRE, vol. 44, no.7, New York, pp. 920-926, 1956.
[58] F. Firouzi, M. E. Salehi, F. Wang, S. M. Fakhraie, “An accurate model for soft error rate estimation considering dynamic voltage,” Microelectronics Reliability, vol. 51, no. 2, pp. 460–467, 2011.
[59] 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.
[60] F. Wang and V. D. Agrawal, “Soft error rate determination for nanoscale sequential logic,” in Proc. 11th Int. Symp. Quality Electronic Design (ISQED 2010), San Jose, CA, pp. 225–230, March 2010.
[61] http://www.si2.org/openeda.si2.org/projects/nangatelib, 2019.

Please sign in

The CSI Journal on Computer Science and Engineering

Reliability Analysis of Sequential Logic Circuits Using Signal Flow Graphs