یک الگوریتم بسیار سریع برای شبیه‌سازی اِشکال تأخیر مسیر مدارهای دیجیتال بر اساس پیمایش موازی مسیر بحرانی

احترام, احمد; صباغیان بیدگلی, حسین; قسوری, حسین; دلشاد, مجید; حسابی, شاهین

doi:10.22052/scj.2021.111571

یک الگوریتم بسیار سریع برای شبیه‌سازی اِشکال تأخیر مسیر مدارهای دیجیتال بر اساس پیمایش موازی مسیر بحرانی

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

نویسندگان

¹ دانشکده فنی و مهندسی، گروه مهندسی برق، واحد اصفهان (خوراسگان)، دانشگاه آزاد اسلامی، اصفهان، ایران

² دانشکده مهندسی برق و کامپیوتر، گروه مهندسی کامپیوتر، دانشگاه کاشان، کاشان، ایران

³ دانشکده مهندسی برق و کامپیوتر، گروه مهندسی برق، واحد کاشان، دانشگاه آزاد اسلامی، کاشان، ایران

⁴ دانشکده مهندسی کامپیوتر، گروه مهندسی برق، دانشگاه صنعتی شریف، تهران، ایران

10.22052/scj.2021.111571

چکیده

شبیه‌سازی اِشکال تأخیر مسیر روشی برای ارزیابی کیفیت آزمون است که در آن تعداد مسیرهای شناسایی شده توسط یک مجموعه آزمون مشخص می‌شود. زمان اجرای شبیه‌سازی اشکال تاخیر مسیر به تعداد کل مسیرهای یک مدار وابسته است. افزایش روز‌افزون بزرگی و پیچیدگی مدارات دیجیتال و رابطه نمایی تعداد مسیرها بر حسب تعداد دروازه‌های یک مدار، شبیه‌سازی اِشکال تأخیر مسیر را برای مدارات امروزی به عملیاتی زمان‌بر تبدیل کرده است. از این رو نیاز به وجود الگوریتم‌های سرعت بالاتر به شدت احساس می‌شود. روش‌های موجود شبیه‌سازی اِشکال تأخیر مسیر بخاطر زمان اجرای طولانی، عدم دقت و یا نیاز به سخت‌افزار خاص دچار مشکل هستند. در کار حاضر یک الگوریتم بسیار سریع برای شبیه‌سازی اِشکال تأخیر مسیر ارائه می‌شود که ضمن افزایش سرعت، دقت خود را نیز حفظ می‌کند و از طرفی برای اجرا به سخت‌افزار خاصی نیاز ندارد. این روش بطور همزمان از چند تکنیک مختلف برای افزایش سرعت استفاده می‌کند. برخی از این تکنیک‌ها مانند رهگیری مسیر بحرانی (جهت کوچک کردن فضای جستجو)، ساده‌سازی شروط انتشار تاخیر مسیر (برای کاهش حجم محاسبات) و ایجاد چک لیست آرایه‌ای (به منظور حذف عملیات مقایسه و جستجو هنگام ادغام لیست مسیرهای شناسایی شده) نوآوری محسوب می‌شوند و بکارگیری آنها در کنار تکنیک‌های شناخته شده مانند اندیس‌گذاری مسیرها (برای‌ جلوگیری از استخراج کامل مسیرها) و موازات 32 بیتی (جهت اعمال 32 بردار آزمون همزمان) باعث افزایش قابل توجه سرعت شده است. روش پیشنهادی بر روی تعدادی از مدارهای محک ISCAS85 و ITC99 آزمایش شده و نتایج ترکیب تکنیک‌های مختلف با یکدیگر و با تعدادی از کارهای گذشته مقایسه شده است. نتایج بدست آمده، تأثیر تکنیک‌های بکار رفته و بهبود حدود 186 برابری نسبت به کارهای دیگران را نشان می‌دهد.

کلیدواژه‌ها

20.1001.1.23223707.1399.9.1.48.1

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

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

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

Ahmad Ehteram ¹
Hossein Sabaghian-Bidgoli ²
Hossein Ghasvari ³
Majid Delshad ¹
Shaahin Hessabi ⁴

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

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

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

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

چکیده [English]

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.

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

Test
Path Delay Fault
Fault Simulation
Critical Path Tracking
Robust Path
Non-robust Path

مراجع

[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.