Automatic Test Pattern Generation for Digital Combinational Circuits Using an Approximate Parallel Pattern Critical Path Tracing Index
Subject Areas : مهندسی برق و کامپیوترZ. Moradi Gheisvandi 1 , A. Kamran 2 *
1 - Elec. and Comp. Eng. Dept., Razi University, Kermanshah, Iran
2 - Elec. and Comp. Eng. Dept., Razi University, Kermanshah, Iran
Keywords: Fault simulation, automatic test pattern generation, fault coverage, test pattern, approximate critical path tracing,
Abstract :
In this study, we propose a test generation method for combinational digital circuits that leverages an index derived from an approximate critical path tracing technique to identify effective test vectors. Evaluation on benchmark circuits shows that this approximate index strongly correlates with the exact fault coverage index while requiring significantly lower computational effort. Using the proposed method, test sets were generated for several benchmark circuits and compared with other test generation approaches that employ either the exact fault coverage index or alternative approximate indices, such as probabilistic indices or simulation-based indices obtained via fault sampling. The results demonstrate that the proposed method efficiently achieves high fault coverage, reduces the number of test vectors, and lowers test generation time.
[1] H. Fujiwara and Toida, "The complexity of fault detection Problems for combinational logic circuits," IEEE Trans. on Computers, vol. 31, no. 6, pp. 555-560, Jun. 1982.
[2] J. P. Roth, W. G. Bouricius, and P. R. Schneider, "Programmed algorithms to compute tests to detect and distinguish between failures in logic lircuits," IEEE Trans. on Electronic Computers, vol. 16, no. 5, pp. 567-580, Oct. 1967.
[3] H. Fujiwara, "Fan: A fanout-oriented test pattern generation algorithm," in Proc. IEEE Int. Symp. on Circuits and Systems, pp. 671-674, Kyoto, Japan, 5-7 Jun.1985.
[4] M. H. Schulz, E. Trischler, and T. M. Sarfert, "SOCRATES: A highly efficient automatic test pattern generation system," IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, vol. 7, no. 1, pp. 126-137, Jan. 1988.
[5] Goel, "An implicit enumeration algorithm to generate tests for combinational logic circuits," IEEE Trans. on Computers, vol. \30, no. 3, pp. 215-222, Mar. 1981.
[6] E. O. Osimiry, R. Ubar, S. Kostin, and J. Raik, "A novel random approach to diagnostic test generation," in Proc. 2016 IEEE Nordic Circuits and Systems Conf., 4 pp., Copenhagen, Denmark, 1-2 Nov. 2016.
[7] A. Kamran, M. S. Jahangiry, and Z. Navabi, "Merit based directed random test generation (MDRTG) scheme for combinational circuits," in Proc. 2010 East-West Design & Test Symp., pp. 416-419, St. Petersburg, Russia, 17-20 Sept. 2010.
[8] E. M. Rudnick, J. H. Patel, G. S. Greenstein, and T. M. Niermann, "A genetic algorithm framework for test generation," IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, vol. 16, no. 9, pp. 1034-1044, Sept. 1997.
[9] E. M. Rudnick, J. G. Holm, D. G. Saab, and J. H. Patel, "Application of simple genetic algorithms to sequential circuit test generation," in Proc. of European Design and Test Conference EDAC-ETC-EUROASIC, pp. 40-45, Paris, France, 28 Feb.-3 Mar. 1994.
[10] H. Harmanani and B. Karablieh, "A hybrid distributed test generation method using deterministic and genetic algorithms," in Proc. 5th. Int. Workshop on System-on-Chip for Real-Time Applications, pp. 317-322, Banff, Canada, 20-24 Jul. 2005.
[11] M. Fooladi and A. Kamran, "Speed-Up in test Methods Using Probabilistic Merit Indicators," Journal of Electronic Testing, vol. 36, no. 2, pp. 285-296, Apr. 2020.
[12] M. Azimipour, M. r. Bonyadi, and M. Eshghi, "Using immune genetic algorithm in ATPG," Australian Journal of Basic and Applied Sciences, vol. 2, no. 4, pp. 920-928, Oct./Dec. 2008.
[13] J. P. Anita and P. T. Vanathi, "Genetic algorithm based test pattern generation for multiple stuck-at faults and test power reduction in VLSI circuits," in Proc. 2014 Int. Conf. on Electronics and Communication Systems, 6 pp., Coimbatore, India, 13-14 Feb. 2014.
[14] A. Bhar, S. Chattopadhyay, I. Sengupta, and R. Kapur, "GA based diagnostic test pattern generation for transition faults," in Proc. 19th Int. Symp. on VLSI Design and Test, 6 pp., Ahmedabad, India, 26-29 Jun 2015.
[15] A. N. Nagamani, S. N. Anuktha, N. Nanditha, and V. K. Agrawal, "A genetic algorithm-based heuristic method for test set generation in reversible circuits," IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, vol. 37, no. 2, pp. 324-336, Feb. 2018.
[16] R. Farah and H. M. Harmanani, "An ant colony optimization approach for test pattern generation," in Proc. 2008 Canadian Conf. on Electrical and Computer Engineering, pp. 001397-001402, Niagara Falls, Canada, 4-7 May 2008.
[17] Z. Jiali, Z. Lin, Y. Yun, N. Tianlin, Z. Long, and X. Xiaodong, "The test pattern generation for digital integrated circuits based on CA-IA-PSO algorithm," in Proc. 7th. Int. Conf. on Measuring Technology and Mechatronics Automation, pp. 1316-1320, Nanchang, China, 13-14 Jun. 2015.
[18] G. Yuan-Liang and X. Wen-Bo, "Study on Automatic test generation of digital circuits using particle swarm optimization," in Proc. 10th Int. Symp.on Distributed Computing and Applications to Business, Engineering and Science, pp. 324-328, Sydney, Australia, 14-17 Oct. 2011.
[19] M. M. Alateeq and W. Pedrycz, "Analysis of optimization algorithms in automated test pattern generation for sequential circuits," in Proc. 2017 IEEE Int. Conf. on Systems, Man, and Cybernetics, Banff, Canada, 5-8 Oct. 2017.
[20] P. Bhattacharya, R. Bhattacharya, and H. Deka, "MATLAB-open source tool based framework for test generation for digital circuits using evolutionary algorithms," Journal of Electronic Testing, vol. 39, no. 5-6, pp. 555-570, Dec. 2023.
[21] E. Haghparast, S. H. Zahiri, and A. Bijari, "An intelligent ATPG technique based on meta-heuristic algorithms," in Proc. 19th Iranian Conf. on Intelligent Systems, pp. 94-99, Sirjan, Iran, 23-24 Oct. 2024.
[22] E. Schneider and H. J. Wunderlich, "SWIFT: Switch-level fault simulation on GPUs," IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, vol. 38, no. 1, pp. 122-135, Jul. 2019.
[23] M. Li and M. S. Hsiao, "3-D parallel fault simulation with GPGPU," IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, vol. 30, no. 10, pp. 1545-1555, Oct. 2011.
[24] M. Beckler and R. D. Blanton, "Fault simulation acceleration for TRAX dictionary construction using GPUs," in Proc. 2017 IEEE Int. Test Conf., 9 pp., 31 Oct.-2 Nov. 2017 2017.
[25] M. H. Haghbayan, S. Teräväinen, A. M. Rahmani, P. Liljeberg, and H. Tenhunen, "Adaptive fault simulation on many-core microprocessor systems," in Proc. 2015 IEEE Int. Symp. on Defect and Fault Tolerance in VLSI and Nanotechnology Systems, pp. 151-154, Amherst, USA, 12-14 Oct. 2015.
[26] S. Hadjitheophanous, S. N. Neophytou, and M. K. Michael, "Scalable parallel fault simulation for shared-memory multiprocessor systems," in Proc. IEEE 34th VLSI Test Symp., 6 pp., Las Vegas, NV, USA, 25-27 Apr. 2016.
[27] M. Karami, M. H. Haghbayan, M. Ebrahimi, A. Miele, H. Tenhunen, and J. Plosila, "Hierarchical fault simulation of deep neural networks on multi-core systems," in Proc. 2021 IEEE European Test Symp., 2 pp. Bruges, Belgium, 24-28 May 2021.
[28] P. R. Maier, U. Sharif, D. Mueller-Gritschneder, and U. Schlichtmann, "Efficient fault injection for embedded systems: As fast as possible but as accurate as necessary," in Proc. IEEE 24th Int. Symp. on On-Line Testing And Robust System Design, pp. 119-122, Costa Brava, Spain, 2-4 Jul. 2018.
[29] J. T. Xiao, et al., "An ISA-level accurate fault simulator for system-level fault analysis," in Proc. IEEE 29th Asian Test Symp., 6 pp., Penang, Malaysia, 23-26 Nov. 2020.
[30] L. Kafka and O. Novak, "FPGA-based fault simulator," in Proc. 9th IEEE Design and Diagnostics of Electronic Circuits and Systems, pp. 272-276, Prague, Czech Republic, 18-21 Apr. 2006.
[31] F. Ferlini, et al., "A methodology for accelerating FPGA fault injection campaign using ICAP," Electronics, vol. 12, no. 4, ArticleID: 807, Feb.-2 2023.
[32] P. Bhattacharya, A. Shakeel, and R. Bhattacharya, "Fault emulation in digital circuits using FPGA based software-hardware co-simulation," in Proc. 11th Int. Conf. on Signal Processing and Integrated Networks, pp. 355-360, Noida, India, 21-22 Mar. 2024.
[33] F. M. Goncalves, M. B. Santos, I. C. Teixeira, and J. P. Teixeira, "Self-checking and fault tolerance quality assessment using fault sampling," in Proc. 17th IEEE Int. Symp. on Defect and Fault Tolerance in VLSI Systems, pp. 216-224, 6-8 Nov. 2002.
[34] M. Fooladi and A. Kamran, "Speed-Up in Test Methods Using Probabilistic Merit Indicators," Journal of Electronic Testing, vol. 36, no. 2, pp. 285-296, Apr. 2020
[35] S. Mirkhani, J. A. Abraham, T. Vo, H. Jun, and B. Eklow, "FALCON: Rapid statistical fault coverage estimation for complex designs," in Proc. 2012 IEEE Int. Test Conf., 10 pp., 5-8 Nov. 2012.
[36] Z. Navabi, Digital System Test and Testable Design: Using HDL Models and Architectures, Springer, 2011.
[37] A. Ehteram, H. Sabaghian-Bidgoli, H. Ghasvari, and S. Hessabi, "A simple and fast solution for fault simulation using approximate parallel critical path tracing," Canadian Journal of Electrical and Computer Engineering, vol. 43, no. 2, pp. 100-110, Spring 2020.