نوع مقاله : علمی-پژوهشی

**نویسندگان**

Department of Computer Engineering and Information Technology, Razi University, Kermanshah, Iran

**چکیده**

Simulation-based test pattern generation methods are an interesting alternative to deterministic methods because of lower time complexity. In these methods, test patterns are evaluated and those with higher efficiency are selected. Traditionally, test pattern selection is based on fault coverage, which is an accurate merit indicator, but its calculation is time-consuming. Instead of fault coverage, approximate indicators can be used to assess efficiency of test patterns. In this paper, an approximate indicator called *APXD* is proposed, which is more efficient than existing approximate methods. Our experimental results show that *APXD* indicator has a strong correlation with fault coverage. In addition, *APXD* simulation is 1900x, 63x, and 56x faster than serial, sampling, and parallel fault simulation, respectively. Exploiting *APXD* indicator instead of fault coverage, in a pruning-based test generation method, leads to about 700x, 24.2x, and 18.4x speedup, respectively compared to pruning based methods that use serial, sampling, or parallel fault simulation for test pattern evaluation, at fault coverage of 80%. Speedup at fault coverage of 95% is about 111.3x, 11.1, and 3.6x, respectively. While, the use of *APXD* indicator instead of fault coverage increases the number of test vectors by 2% at most, confirming the efficiency of *APXD* indicator compared with probabilistic and statistical approximate indicators.

**کلیدواژهها**

**عنوان مقاله** [English]

**نویسندگان** [English]

- L. Khosravi
- A. Kamran

Department of Computer Engineering and Information Technology, Razi University, Kermanshah, Iran

Simulation-based test pattern generation methods are an interesting alternative to deterministic methods because of lower time complexity. In these methods, test patterns are evaluated and those with higher efficiency are selected. Traditionally, test pattern selection is based on fault coverage, which is an accurate merit indicator, but its calculation is time-consuming. Instead of fault coverage, approximate indicators can be used to assess efficiency of test patterns. In this paper, an approximate indicator called *APXD* is proposed, which is more efficient than existing approximate methods. Our experimental results show that *APXD* indicator has a strong correlation with fault coverage. In addition, *APXD* simulation is 1900x, 63x, and 56x faster than serial, sampling, and parallel fault simulation, respectively. Exploiting *APXD* indicator instead of fault coverage, in a pruning-based test generation method, leads to about 700x, 24.2x, and 18.4x speedup, respectively compared to pruning based methods that use serial, sampling, or parallel fault simulation for test pattern evaluation, at fault coverage of 80%. Speedup at fault coverage of 95% is about 111.3x, 11.1, and 3.6x, respectively. While, the use of *APXD* indicator instead of fault coverage increases the number of test vectors by 2% at most, confirming the efficiency of *APXD* indicator compared with probabilistic and statistical approximate indicators.

**کلیدواژهها** [English]

- Approximate fault simulation
- Test pattern generation
- Probabilistic fault simulation
- Fault sampling

[1] E. O. Osimiry, R. Ubar, S. Kostin, and J. Raik, "A novel random approach to diagnostic test generation," in 2016 IEEE Nordic Circuits and Systems Conference (NORCAS), 2016, pp. 1-4.

[2] A. Kamran, M. S. Jahangiry, and Z. Navabi, "Merit based directed random test generation (MDRTG) scheme for combinational circuits," in 2010 East-West Design & Test Symposium (EWDTS), 2010, pp. 416-419.

[3] A. Kamran, "HASTI: hardware-assisted functional testing of embedded processors in idle times," IET Computers & Digital Techniques, vol. 13, no. 3, pp. 198-205, 2019.

[4] S. Esfandyari, V. Rafe, “A Hybrid solution for Software testing to minimum test suite generation using hill climbing and bat search algorithms”, Tabriz Journal of Electrical Engineering, vol. 46, no. 3, pp. 25-35, 2016 (in persion).

[5] M. M. Dejam Shahabi, S. E. Beheshtian, P. Badiei, R. Akbari, S. M. R. Moosavi, “Adapting Swarm Intelligence Based Methods for Test Data Generation”, Tabriz Journal of Electrical Engineering, vol. 51, no. 2, pp. 183-193, 2021.

[6] E. M. Rudnick, J. G. Holm, D. G. Saab, and J. H. Patel, "Application of simple genetic algorithms to sequential circuit test generation," in Proceedings of European Design and Test Conference EDAC-ETC-EUROASIC, 1994, pp. 40-45.

[7] E. M. Rudnick, J. H. Patel, G. S. Greenstein, and T. M. Niermann, "A genetic algorithm framework for test generation," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 16, no. 9, pp. 1034-1044, 1997.

[8] H. Harmanani and B. Karablieh, "A hybrid distributed test generation method using deterministic and genetic algorithms," in Fifth International Workshop on System-on-Chip for Real-Time Applications (IWSOC'05), 2005, pp. 317-322.

[9] 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, 2008.

[10] 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 Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 37, no. 2, pp. 324-336, 2018.

[11] A. Bhar, S. Chattopadhyay, I. Sengupta, and R. Kapur, "GA based diagnostic test pattern generation for transition faults," in 2015 19th International Symposium on VLSI Design and Test, 2015, pp. 1-6.

[12] 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 2014 International Conference on Electronics and Communication Systems (ICECS), 2014, pp. 1-6.

[13] R. Farah and H. Harmanani, "An Ant Colony Optimization approach for test pattern generation," 2008 Canadian Conference on Electrical and Computer Engineering, pp. 001397-001402, 2008.

[14] M. M. Alateeq and W. Pedrycz, "Analysis of optimization algorithms in automated test pattern generation for sequential circuits," in 2017 IEEE International Conference on Systems, Man, and Cybernetics (SMC), 2017, pp. 1834-1839.

[15] G. Yuan-Liang and X. Wen-Bo, "Study on Automatic Test Generation of Digital Circuits Using Particle Swarm Optimization," in 2011 10th International Symposium on Distributed Computing and Applications to Business, Engineering and Science, 2011, pp. 324-328.

[16] 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 2015 Seventh International Conference on Measuring Technology and Mechatronics Automation, 2015, pp. 1316-1320.

[17] M. Santos, H. Braga, I. Teixeira, J. P. Teixeira, "Dynamic Fault Injection Optimization for FPGA-Based Harware Fault Simulation, " Design and Diagnostics of Electronic Circuits and Systems Workshop (DDECS), 2002, pp. 370-373.

[18] A. Parreira, J. P. Teixeira, A. Pantelimon, M. B. Santos, and J. T. de Sousa, "Fault Simulation Using Partially Reconfigurable Hardware," vol. 2778, pp. 839-848, 2003.

[19] L. Kafka and O. Novak, "FPGA-based fault simulator," in 2006 IEEE Design and Diagnostics of Electronic Circuits and systems, 2006, pp. 272-276.

[20] M. Haghbayan, S. Teräväinen, A. Rahmani, P. Liljeberg, and H. Tenhunen, "Adaptive fault simulation on many-core microprocessor systems," in 2015 IEEE International Symposium on Defect and Fault Tolerance in VLSI and Nanotechnology Systems (DFTS), 2015, pp. 151-154.

[21] S. Hadjitheophanous, S. N. Neophytou, and M. K. Michael, "Scalable parallel fault simulation for shared-memory multiprocessor systems," in 2016 IEEE 34th VLSI Test Symposium (VTS), 2016, pp. 1-6.

[22] M. Li and M. S. Hsiao, "3-D Parallel Fault Simulation With GPGPU," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 30, no. 10, pp. 1545-1555, 2011.

[23] M. Beckler and R. D. Blanton, "Fault simulation acceleration for TRAX dictionary construction using GPUs," in 2017 IEEE International Test Conference (ITC), 2017, pp. 1-9.

[24] E. Schneider and H. Wunderlich, "SWIFT: Switch-Level Fault Simulation on GPUs," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 38, no. 1, pp. 122-135, 2019.

[25] J. T. Xiao, T. S. Hsu, C. M. Fuchs, Y. T. Chang, J. J. Liou, and H. H. Chen, "An ISA-level Accurate Fault Simulator for System-level Fault Analysis," in 2020 IEEE 29th Asian Test Symposium (ATS, pp. 1-6), 2020.

[26] 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 2021 IEEE European Test Symposium (ETS), pp. 1-2, 2021.

[27] 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 2018 IEEE 24th International Symposium on On-Line Testing And Robust System Design (IOLTS, pp. 119-122), 2018.

[28] F. M. Goncalves, M. B. Santos, I. C. Teixeira, and J. P. Teixeira, "Self-checking and fault tolerance quality assessment using fault sampling," in 17th IEEE International Symposium on Defect and Fault Tolerance in VLSI Systems, 2002. DFT 2002. Proceedings., 2002, pp. 216-224.

[29] S. Mirkhani, J. A. Abraham, T. Vo, H. Jun, and B. Eklow, "FALCON: Rapid statistical fault coverage estimation for complex designs," in 2012 IEEE International Test Conference, 2012, pp. 1-10.

[30] 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, 2020/04/01 2020.

[31] S. A. Al-Arian and M. A. Al-Kharji, "Fault simulation and test generation by fault sampling techniques," in Proceedings 1992 IEEE International Conference on Computer Design: VLSI in Computers & Processors, 1992, pp. 365-368.

[32] G. Asadi and M. B. Tahoori, "An analytical approach for soft error rate estimation in digital circuits," in 2005 IEEE International Symposium on Circuits and Systems, 2005, pp. 2991-2994 Vol. 3.

[33] M. M. Mukaka, "Statistics corner: A guide to appropriate use of correlation coefficient in medical research," Malawi medical journal : the journal of Medical Association of Malawi, vol. 24, no. 3, pp. 69-71, 2012.