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

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

نویسندگان

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

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

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

4 عضو هیئت علمی، گروه مهندسی کامپیوتر، دانشگاه کاشان

10.22052/scj.2021.111571

چکیده

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

کلیدواژه‌ها


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

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

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

  • Ahmad Ehteram 1
  • Hossein Ghasvari 2
  • Majid Delshad 1
  • Shaahin Hessabi 3
  • Hossein Sabaghian-Bidgoli 4
چکیده [English]

Path delay simulation is a method of assessing the quality of a test in which the number of paths identified by the experimenter 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 todaychr('39')s circuits has made path delay fault simulation a time-consuming operation. Hence the need for higher speed algorithms is strongly felt. Existing methods of path delay fault simulation suffer from long execution time, inaccuracy or the need for special hardware. In the present work, a very fast algorithm has been proposed to simulate path delay faults, which while increasing the speed, also maintains its accuracy and on the other hand does not require special hardware to run. This method simultaneously uses several different techniques to increase speed. Some of these techniques include innovations such as critical path tracing (to reduce search space), simplify path delay propagation conditions (to reduce computational volume), and creating the array checklist (to eliminate comparison and search operations when merging detected path lists). Using these techniques alongside well-known techniques such as path indexing (to prevent complete path extraction) and 32-bit parallelism (using 32 simultaneous test vectors) has significantly increased speed. The proposed method has been tested on a number of ISCAS85 and ITC99 criteria and the results of combining different techniques have been compared with a number of previous works. The results show that the techniques used are about 186 times more effective than others.

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

  • Test
  • Path delay fault
  • Fault simulation
  • Critical path tracing
  • Robust path
  • Non-robust path