A very fast algorithm for path delay fault simulation of digital circuit based on parallel critical path tracing

Document Type : Original Article

Authors

1 Faculty of Engineering, Department of Electrical Engineering, Isfahan Branch (Khorasgan), Islamic Azad University, Isfahan, Iran

2 Faculty of Electrical and Computer Engineering, Department of Computer Engineering, University of Kashan, Kashan, Iran

3 Faculty of Electrical and Computer Engineering, Department of Electrical Engineering, Kashan Branch, Islamic Azad University, Kashan, Iran

4 Faculty of Computer Engineering, Department of Electrical Engineering, Sharif University of Technology, Tehran, Iran

Abstract

Path delay simulation is a method of assessing the quality of a test in which the number of paths detected by a given test set is determined. The execution time of the path delay fault simulation depends on the total number of paths in the circuit. Increasing the size and complexity of digital circuits and the exponential relationship between the number of paths and the number of gates in the today’s circuits has made path delay fault simulation a time-consuming operation. Hence, high speed algorithms are extremely desirable. Existing methods of path delay fault simulation suffer from long execution time, inaccuracy or the need for special hardware. This paper proposes a very fast algorithm to simulate path delay faults, which improves the speed while maintaining its accuracy, and on the other hand does not require special hardware to run. This method concurrently uses a couple of different techniques to increase the speed. Some of these techniques like critical path interception (for reducing the search space), simplification of the conditions of propagation of path delay, (for reducing computations), and creation of checklist array (for removing comparison and search operations in merging recognized paths) are considered as our contributions. Applying such techniques alongside other well-known techniques like path indexing (to prevent full path extraction) and 32-bit parallelism (to concurrently employ 32 test vectors) led to increase the speed. The proposed method was applied to a number of ISCAS85 and ITC99 benchmark circuits, and the results of combining different techniques were compared with a number of previous studies. The obtained outcomes denote the impact of the applied techniques and 186-fold improvement.

Keywords

References

[1] Aguiar Y.Q., Zimpeck A.L., Meinhardt C., and Reis R., “Permanent and single event transient faults reliability evaluation EDA tool”, Microelectronics Reliability, 64: 63-67, 2016.
[2] Shojiro A., VLSI Design and Test for Systems Dependability, Japan, Springer, 2019
[3] Parhami B., Dependable Computing: A Multilevel Approach, forthcoming book whose draft is available:https://web.ece.ucsb.edu/~parhami/text_dep_comp.htm.
[4] Bushnell M.L. and Agrawal V.D., Essentials of Electronic Testing for Digital, Memory & Mixed-Signal VLSI Circuits, Kluwer Academic Publishers, 2002.
[5] Krstic A. and Cheng K.-T., Delay Fault Testing for VLSI Circuits, US, Springer, 1998.
[6] Ehteram A., Sabaghian-Bidgoli H., Ghasvari H., and Hessabi S., “A Simple and Fast Solution for Fault Simulation Using Approximate Parallel Critical Path Tracing,” in Canadian Journal of Electrical and Computer Engineering, 43(2): 100-110, 2020.
[7] Liu X., Hsiao M.S., Chakravarty S., and Thadikaran P.J., “Efficient transition fault ATPG algorithms based on stuck-at test vectors,” J. Electronic Testing: Theory and Applic., 19(4):437–445, 2003.
[8] Liu T., Zhou Y., Liu Y., and Cai S., “Harzard-based ATPG for improving delay test quality,” J. Electronic Testing: Theory and Applic., 31(1): 27–34, 2015.
[9] Jayanthy S. and Bhuvaneswari M.C., “Delay Fault Testing of VLSI Circuits”, Test Generation of Crosstalk Delay Faults, pp. 15-35, 2019.
[10] Pomeranz I., “Non-Masking Non-Robust Tests for Path Delay Faults,” 2020 IEEE 38th VLSI Test Symposium (VTS), San Diego, CA, USA, pp. 1-6, 2020.
[11] Smith G.L., “Model for delay faults based upon paths,” Proc. Int. Test Conf., pp. 342-349, 1985.
[12] Fink F., Fuchs K., and Schulz M.H., “Robust and nonrobust path delay fault simulation by parallel processing of patterns,” in IEEE Transactions on Computers, 41(12): 1527-1536, 1992.
[13] Majhi A.K., Jacob J., and Patnaik L.M., “A Novel Path Delay Fault Simulator using Binary Logic,” VLSI Design, 4: 167-179, 1996.
[14] Chakraborty T.J., Agrawal V.D., and Bushnell M.L., “Path delay fault simulation of sequential circuits,” in IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 8(2): 223-228, 2000.
[15] Jayanthy S., Bhuvaneswari M.C., and Kavitha T., “Simulation based ATPG for path delay faults in digital circuits using genetic algorithm,” in Proceedings of the National Conference on Adaptive Sensors and Intelligent Systems, pp. 80–84, 2008.
[16] Pomeranz I. and Reddy S.M., “An efficient non-enumerative method to estimate path delay fault coverage,” IEEE/ACM International Conference on Computer-Aided Design, Santa Clara, CA, USA, pp. 560-567, 1992.
[17] Pomeranz I. and Reddy S.M., “An efficient nonenumerative method to estimate the path delay fault coverage in combinational circuits,” in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 13(2): 240-250, 1994.
[18] Heragu K., Agrawal V.D., and Bushnell M.L., “Statistical methods for delay fault coverage analysis,” Proceedings of the 8th International Conference on VLSI Design, New Delhi, India, pp. 166-170, 1995.
[19] Ali Y., Yamato Y., Yoneda T., Hatayama K., and Inoue M., “Parallel Path Delay Fault Simulation for Multi/Many-Core Processors with SIMD Units,” IEEE 23rd Asian Test Symposium, Hangzhou, China, pp. 292-297, 2014.
[20] Schneider E., Holst S., Kochte M.A., Wen X., and Wunderlich H., “GPU-accelerated small delay fault simulation,” Design, Automation & Test in Europe Conference & Exhibition (DATE), Grenoble, France, pp. 1174-1179, 2015.
[21] Schneider E., Kochte M.A., Holst S., Wen X., and Wunderlich H.-J., “GPU-accelerated simulation of small delay faults,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 36(5): 829–841, 2017.
[22] Gharaybeh M.A., Agrawal V.D., and Bushnell M.L., “False-path removal using delay fault simulation,” Proceedings Seventh Asian Test Symposium (ATS'98), Singapore, pp. 82-87, 1998.
[23] Gjermandez O., “Exploiting arithmetic built-in self-test techniques for path delay fault testing,” Ph.D. dissertation, Norwegian University of Science and Technology, Trondheim, Norway, 2006.
[24] Manikandan P., Larsen B.B., and Aas E.J., “An Enhanced Path Delay Fault Simulator for Combinational Circuits,” 14th Euromicro Conference on Digital System Design, Oulu, Finland, pp. 375-381, 2011.

Files

History

  • Receive Date: 09 April 2021
  • Accept Date: 21 May 2021

Share

How to cite

Statistics