یک الگوریتم بسیار سریع برای شبیهسازی اِشکال تأخیر مسیر مدارهای دیجیتال بر اساس پیمایش موازی مسیر بحرانی
نویسندگان
1 دانشکده مهندسی برق و کامپیوتر، گروه مهندسی برق، واحد کاشان، دانشگاه آزاد اسلامی، کاشان، ایران
2 دانشکده فنی و مهندسی، گروه مهندسی برق، واحد اصفهان (خوراسگان)، دانشگاه آزاد اسلامی، اصفهان، ایران
3 دانشکده مهندسی کامپیوتر، گروه مهندسی برق، دانشگاه صنعتی شریف، تهران، ایران
4 دانشکده فنی و مهندسی، گروه مهندسی برق، واحد اصفهان (خوراسگان)، دانشگاه آزاد اسلامی، اصفهان، ایران
5 دانشکده مهندسی برق و کامپیوتر، گروه مهندسی کامپیوتر، دانشگاه کاشان، کاشان، ایران
doi
10.22052/scj.2021.111571چکیده
شبیهسازی اِشکال تأخیر مسیر روشی برای ارزیابی کیفیت آزمون است که در آن تعداد مسیرهای شناسایی شده توسط یک مجموعه آزمون مشخص میشود. زمان اجرای شبیهسازی اشکال تاخیر مسیر به تعداد کل مسیرهای یک مدار وابسته است. افزایش روزافزون بزرگی و پیچیدگی مدارات دیجیتال و رابطه نمایی تعداد مسیرها بر حسب تعداد دروازههای یک مدار، شبیهسازی اِشکال تأخیر مسیر را برای مدارات امروزی به عملیاتی زمانبر تبدیل کرده است. از این رو نیاز به وجود الگوریتمهای سرعت بالاتر به شدت احساس میشود. روشهای موجود شبیهسازی اِشکال تأخیر مسیر بخاطر زمان اجرای طولانی، عدم دقت و یا نیاز به سختافزار خاص دچار مشکل هستند. در کار حاضر یک الگوریتم بسیار سریع برای شبیهسازی اِشکال تأخیر مسیر ارائه میشود که ضمن افزایش سرعت، دقت خود را نیز حفظ میکند و از طرفی برای اجرا به سختافزار خاصی نیاز ندارد. این روش بطور همزمان از چند تکنیک مختلف برای افزایش سرعت استفاده میکند. برخی از این تکنیکها مانند رهگیری مسیر بحرانی (جهت کوچک کردن فضای جستجو)، سادهسازی شروط انتشار تاخیر مسیر (برای کاهش حجم محاسبات) و ایجاد چک لیست آرایهای (به منظور حذف عملیات مقایسه و جستجو هنگام ادغام لیست مسیرهای شناسایی شده) نوآوری محسوب میشوند و بکارگیری آنها در کنار تکنیکهای شناخته شده مانند اندیسگذاری مسیرها (برای جلوگیری از استخراج کامل مسیرها) و موازات 32 بیتی (جهت اعمال 32 بردار آزمون همزمان) باعث افزایش قابل توجه سرعت شده است. روش پیشنهادی بر روی تعدادی از مدارهای محک ISCAS85 و ITC99 آزمایش شده و نتایج ترکیب تکنیکهای مختلف با یکدیگر و با تعدادی از کارهای گذشته مقایسه شده است. نتایج بدست آمده، تأثیر تکنیکهای بکار رفته و بهبود حدود 186 برابری نسبت به کارهای دیگران را نشان میدهد.
