Experimenting with evolutionary meta-heuristics for state justification in sequential ATPG

Abstract

إن انتاج أنماط الاختبار (Test Pattern Generation) للدارة المتسلسلة باستخدام الطرق الموجة (Deterministic Methods) أو الخوارزميات التي تعتمد على تعيين الأخطاء مسبقاً (Algorithms Fault-oriented) ؛ يعتبر غاية في التعقيد ، ويستغرق الكثير من الوقت . لذلك تحتاج إلى نهج جديد للارتقاء بالتقنيات المتوفرة لتقليص وقت التنفيذ ، وزيادة نسبة اكتشاف الأخطاء . تعتبر الخوارزميات الارتقائية (Evolutionary Algorithms) فعالة في مجال البحث عن حلول مثلى لمشكلة معينة كإنتاج أنماط الاختبار ، التي تعتبر عملية بحث ضمن مجال واسع من الأنماط . كما تعتبر عملية تعيين حالة الدارة (State Justification) في عناصر التسلسل من ضمن العمليات المشتركة بين طرق الإنتاج التلقائي لأنماط الاختبار (ATPG) في الدوائر المتسلسلة . إن تعيين حالة الدارة باستخدام الخوارزميات الموجهة مشكلة معقدة تتضمن العديد من القرارات التراجعية التي تزيد وقت التنفيذ ، حيث يمكن تقليص هذا الوقت باستخدام طرق مبنية على المحاكاة ، لكن هذه الطرق تعجز عن اكتشاف الأخطاء غير المستقرة التي يمكن اكتشافها باستخدام الخوارزميات الموجهة . أم في هذه الرسالة فإننا نعرض نهجا مركبا يستخدم مزيجا من الخوارزميات الارتقائية والخوارزميات الموجهة لتعيين حالة الدارة . هذا النهج يعتمد على تطبيق الخوارزميات الجينية (Genetic Algorithms) على سلاسل الحالات المراد تعيينها النمط تلو الآخر على خلاف الخوارزميات الجينية السابقة التي تعمل على سلسلة كاملة . إن مشاكل الطرق السابقة تكمن في عدم قدرتها على تعيين الحالات التي يصعب الوصول إليها بسبب استخدام سلسلة محدودة الطول ، بالإضافة إلى أن هذه الطرق لا تأخذ في حسبانها جودة الحالات الوسيطة التي تصل إليها الدارة أثناء عملية التعيين ، حيث تقوم بتقييم الكروموزوم بناء على آخر حالة وصلتها الدارة . إن النهج الجديد يتغلب على هذه المشاكل في أثناء إنتاج أنماط الاختبار واحدا تلو الآخر ، وهذا النهج تمت مقارنته مع الخوارزميات السابقة ، حيث دلت نتائج الدراسة التي أجريت على مجموعة من الدوائر من علامة المقايسة ISCAS 89 على تحسن كبيرة في نسبة الحالات التي تم تعيينها بإضافة تقليص وقت التنفيذ .