شناسایی خطاهای غیر قابل آزمون در مدارهای ترتیبی با استفاده از محدودیت های مسیر آزمون

مقدمه:

تولید آزمون برای مدارهای سنکرون ترتیبی یک کار زمان بر است. ابزار تولید الگوی آزمون خودکار(2) (ATPG) تلاش زیادی را برای هم برای استخراج بردارهای آزمون برای خطاهای قابل تست و هم اثبات اینکه برای خطاهای غیر قابل تست آزمونی وجود ندارد، صرف می‌کند. به همین دلیل شناسایی خطاهای غیر قابل تست یک ویژگی مهم جهت بالا بردن سرعت در ATPG ترتیبی است. درصد خطاهای غیر قابل تست در مدارهای ترتیبی به طور قابل ملاحظه ای بیشتر از مدارهای ترکیبی است. برای مدارهای ترکیبی، خطاهای غیر قابل تست به دلیل منطق اضافی رخ می‌دهد در حالی که در مدارهای ترتیبی به دلیل حالت‌های غیر قابل دسترس یا انتقال های حالت غیر ممکن اتفاق می افتد.
کارهایی جهت شناسای خطاهای غیر قابل تست پیشنهاد شده است. اولین روش خطا گرا(3) و بر اساس به کار بردن ATPG ترکیبی جهت گسترش مدل مدارهای ترتیبی با فریم زمانی بود. با این حال این روش به دلیل سایز انفجاری مدل های ترتیبی Unrolled قابل گسترش نبود .به همین دلیل روش استقلال خطا مطرح شد. الگوریتم جدید FIRES نامیده می‌شد و آن اطلاعات حالت غیر مجاز را برای کامل کردن تحلیل افزونگی پیاده سازی کرده است. در ادامه روش های دیگری از جمله MUST، FUNI، FILL و ... آمد. مشکل رایج در روش‌های بالا این بود که در سطح منطقی طراحی عمل می‌کردند و بنابر این تعداد زیادی از آن ها خارج از سطح netlist های منطقی بودند.
در این مقاله یک روش شناسایی خطاهای غیرقابل آزمون سلسله مراتبی(4) ارائه داده می‌شود. این روش امکان تشخیص غیر قابل تست بودن های ترتیبی در ماژول‌های ترکیبی(5) (واحدهای عملیاتی، مالتی پلکسر ها) جاسازی شده در یک مدار سلسله مراتبی و براساس محدودیت‌های فعال سازی مسیر استخراج شده توسط یک RTL ATPG را می‌دهد. در این مقاله ما یک روش شناسایی غیر قابل تست بودن سلسله مراتبی برای نمونه کلی خطاهای مدل چسپان(6) غیرقابل آزمون ترتیبی ارائه می‌دهیم.
ابتدا یک تولیدکننده الگوی آزمون RTL جهت استخراج مجموعه‌ایی از تمام محدودیت‌های ممکن فعال‌سازی مسیر آزمون برای ماژول تحت آزمون(7) (MUT) در یک تعداد چرخه خاص به کار برده می‌شود. سپس، محدودیت‌ها کمینه شده‌اند و یک تولید کننده الگوی آزمون قطعی(8) حاصل از محدودیت‌ها جهت ایجاد تست سلسله مراتبی با زمان محدود اجرا می‌شود و غیر قابل آزمون بودن برای مدارهای ترتیبی اثبات می‌شود. آزمایشات نشان می‌دهد که این روش قادر است تعداد زیادی از خطاهای غیر قابل آزمون را اثبات کند وبازدهی آن در پوشش خطا خیلی بیشتر از روش ATPG تجاری است.
روشی که در این مقاله به کار برده شده است یک جریان آزمون بالا به پایین(9) است، زیرا روش سنتی پایین به بالا(10) به دلیل نادیده گرفتن محدودیت‌های انتشار بسیار خوش بینانه است. شکل 1 یک جریان آزمون بالا به پایین را برای MUT در یک طراحی RTL بر سلسله مراتبی ارائه می‌دهد.
جریان شامل سه فاز است. در فاز اول، مجموعه کاملی از محدودیت‌ها جهت راه اندازی یک مسیر آزمون برای یک ماژول RTL راه اندازی شده است. در فاز دوم، این مجموعه از محدودیت ها همانطور که در ادامه بیان می‌شود به حداقل رسیده اند سپس محیط آزمون به زبان VHDL ترجمه شده است و با استفاده از کامپایلر SDC(11) سنتز شده است. در فاز سوم، تست‌های قطعی برای ماژول سطح منطقی با توجه به محدودیت‌های مسیر کمینه شده تولید می‌شود.
در نهایت به عنوان نتیجه ما لیستی از خطاهای غیرقابل تست در MUT و همچنین الگوهای آزمون برای کل طراحی را به دست می‌اوریم.

2. استخراج محدودیت‌های مسیر آزمون در RTL

در این قسمت نمایش RTL(12) (سطح انتقال ثبات ) از یک سیستم دیجیتال تعریف می‌شود. مفهوم محدودیت‌های مسیر آزمون را برای تست کردن یک ماژول در طراحی RTL معرفی می‌شود و روند استخراج آن‌ها توسط الگوریتم پیاده‌سازی شده در تولید کننده الگوی آزمون سلسله مراتبی DECIDER [22] توصیف می‌شود.

2.1 نمایش RTL

شکل 2 یک دید ساختاری RTL از یک سیستم دیجیتال را نشان می‌دهد. در طراحی RTL فرض بر این است که طراحی به دو قسمت تقسیم شده است : قسمت کنترل و قسمت مسیر داده (13). یک سیستم دیجیتال RTL دارای F و X است که در آن F مجموعه‌ایی از ماژول‌ها در شبکه و X مجموعه‌ای از متغیرهای اتصال ماژول است.
قسمت کنترل توسط یک (14)FSM شامل سه ماژول ارائه شده است : یک ثبات حالت با یک متغیر خروجی ، ماژول منطقی حالت بعدی با یک متغیر خروجی و یک ماژول منطقی خروجی FSM، با خروجی‌های اولیه و متغیرهای کنترل . متغیرهای ورودی قسمت کنترل از ورودی‌های اولیه طراحی (متغیرهای )، متغیرهای بیت وضعیت گرفته شده از مسیر داده و مقدار فعلی متغیرهای وضعیت تشکیل شده است. خروجی قسمت کنترل شامل خروجی‌های اولیه طراحی، متغیرهای سیگنال کنترل و مقدار بعدی متغیر رجیستر حالت است.
به همین ترتیب، مسیر داده به عنوان شبکه‌ای از ماژول‌های به هم پیوسته در نظر گرفته شده است. ماژول‌ها شامل رجیسترهای با متغیرهای خروجی ، مولتی پلکسرهای با خروجی‌های ، واحدهای عملیاتی برای پیاده‌سازی عملیات ریاضی با خروجی‌های و ماژول‌های مقایسه گر F با خروجی‌های هستند. ورودی‌ها برای مسیر داده ورودی‌های اصلی XI و متغیرهای سیگنال کنترل هستند که مورد آخر به دو قیمت تقسیم شده است : آدرس مولتی پلکسرها و متغیر فعال سازی رجیستر . خروجی‌های مسیر داده شامل خروجی اصلی و هم چنین متغیرهای بیت وضعیت از ماژول عملگر مقایسه‌گر است که منتج به قسمت کنترل است.

2.2 – استخراج محدودیت های آزمون

برای هر ماژول تحت آزمایش (MUT) مسیر داده، توالی حالت قسمت کنترل FSM به منظور انتشاز اثر خطا، از خروجی MUT به خروجی اصلی، و انتشار مقادیر از ورودی اصلی به ورودی‌های MUT استخراج می‌شود. توسط مجموعه‌ایی از محدودیت‌ها یک مسیر آزمون ارائه داده می‌شود. همه مسیرهای تست در یک تعداد چرخه خاص فعال شده است و محدودیت‌های مربوط توسط الگوریتم پیشنهادی استخراج شده است. این چرخه ابتدا به یک تنظیم شده و سپس به تدریج افزایش یافته است تا زمانی که محدودیت‌های به دست آمده بعد از کمینه سازی خالی نباشد. به منظور استخراج محدودیت‌های مسیر آزمون RTL در این مقاله یک ابزار فعال سازی مسیر آزمون (DECIDER) به کار گرفته شده است. مفهوم محدودیت برای یک مسیر آزمون واحد برای MUT مسیز داده در شکل 3 نشان داده شده است.
محدودیت‌های مسیر آزمون به سه دسته تقسیم شده اند : 1- محدودیت‌های فعال‌سازی مسیر 2- محدودیت‌های تبدیل 3- محدودیت‌های انتشار .
محدودیت‌های فعال‌سازی مسیر به شرایط گذر حالت FSM بستگی دارند. محدودیت‌های تبدیل، منعکس کننده تغییرات در طول مسیر از ورودی MUT سطح بالا تا ورودی‌های اصلی کل مدار است. محدودیت‌های انتشار نشان می‌دهد که چگونه مقادیر از خروجی MUT به خروجی اصلی بسته به مقدار ورودی اصلی انتشار می‌یابد. ایده اصلی در اینجا این چک کردن این موضوع است که آیا اثر خطا وقتی که به یک خروجی اصلی انتشار یافته است ماسک خواهد شد؟
یک نمونه کلی از محدودیت را برای MUT پیشنهاد شده در شکل 3 در نظر بگیرید، این چنین محدودیت‌هایی به صورت زیر استخراج شده اند. ابتدا مقادیر از متغیر خروجی به خروجی اصلی توسط فعالیت یک توالی حالت در قسمت کنترل انتشار داده می‌شود. در اینجا x(t) به مقدار متغیر x در زمان t دلالت دارد. بنابر این انتشار توالی حالت در زمان t شروع می‌شود که آن را قدم آشکارسازی(15) می‌گویند و در زمان t+n به پایان می‌رسد. در طول انتشار محدودیتهای فعال‌سازی مسیر در گام‌های زمانی به وجود آمده‌اند که مقادیر حالت بعدی xs به بیت‌های وضعیت xN وابسته است. وقتی که تاثیر مقدار خطا از در زمان t+n انتشار می‌یابد پس از آن محدودیت انتشار Cp به وجود آمده است. با شروع از گام t+n حرکت به عقب تا رسیدن به زمان آشکارسازی t انجام می‌شود و در هر گام محدودیت‌های انتشار و محدودیت‌های فعال‌سازی به‌روز می‌شوند. در مرحله آشکارسازی t، محدودیت تبدیل برای هر ورودی MUT ایجاد می‌شود. بدون از دست دادن کلیت شکل 3، یک MUT با ورودی و نشان داده شده است که برای این نمونه محدودیت تبدیل به ترتیب ایجاد شده‌اند. حرکت به عقب تا گام t-m انجام می‌شود که در آن همه متغیرها در محدودیت دارای مقدار اصلی شده باشند.
همان‌طور که مشاهده می‌شود در طول این فرآیند، همه محدودیت‌ها ایجاد شده‌اند.

3. کمینه کردن محدودیت‌های مسیر آزمون

در این قسمت کمینه کردن محدودیت‌های مسیر آزمون برای MUT شرح داده می‌شود. این مرحله به این دلیل نیاز است‌که همه محدودیت‌های مسیر آزمون ممکن است به طور قابل ملاحظه در VHDL و همچنین سنتز منطقی آن‌ها بزرگ شوند. هر مسیر آزمون ، که درآن P مجموعه‌ایی از همه مسیرهای آزمون برای یک MUT در یک فریم زمانی است، ممکن است به یک صورت سه‌گانه نمایش داده شود که محدودیت‌های انتشار، تبدیل و فعال‌سازی مسیر را برای مسیر آزمون Pi نشان می‌دهند. می‌توان مجموعه کامل از مسیرهای آزمون P توسط فرم نرمال گسسته(16) (DNF) بیان کرد و سپس به روشی که بیان می‌شود آن را کمینه کرد. روش کمینه کردن DNF به صورت زیر است:
در فرم DNF یک درخت وجود دارد که در آن نودهای میانی عملگرهای Λ و V هستند و برگ‌ها QFBV(17) (عبارات )هستند. بعضی از محدودیت‌ها در مسیر آزمون می‌تواند زائد باشد که جهت حذف آن‌ها از روشی که در ادامه آمده است استفاده می‌شود. یک فرمول منطقی φ حاصل از فرم نرمال منفی(18) را در نظر بگیرید. ابتدا از آن یک درخت ساخته می‌شود. ایده این است که برگ هر آزمون L در مقابل یک فرمول ویژه αL قرار دارد که محدودیت بحرانی نامیده می‌شود. اگر αL= L باشد آنگاه L می‌تواند مقدار TRUE بگیرد، مثلا فرض کنید φ به صورت زیر باشد :

پس مقدار x+y=3 برابر false می‌شود و اتصال دوم حذف می‌شود، باقیمانده فرمول نیز چون x=1 => x>0 پس مقدار x>0 می‌تواند با TRUE جایگزین شود و در نهایت عبارت به x=1 کمینه می‌شود (شکل 5).

4- ATPG حاصل از محدودیت برای اثبات غیر قابل آزمون بودن:

4-1 ) تخصیص نمودارهای تصمیم گیری:

مجموعه کمینه شده از مسیرهای آزمون P به دست آمده توسط استخراج محدودیت‌ها که در قسمت 2 تعریف شد و هم چنین کمینه‌سازی ارائه شده در قسمت 3، محیط آزمون را برای ATPG حاصل از محدودیت شکل می‌دهند. در این قسمت یک مثال ارائه می‌شود که در آن برای نشان دادن محدودیت مسیر آزمون از نمودار تخصیص تصمیم(19) (ADD) استفاده می‌شود. ADD یک گراف مارپیچی است که شامل مجموعه‌ایی از نودها است که در چهار دسته می‌تواند طبقه‌بندی شود(شکل 6):
گره خواندن 2-گره نوشتن 3- عملگرها 4- گره تخصیص تصمیم(20) (ADN)
یک گره خواندن یک پورت ورودی اصلی، یک واحد ذخیره سازی و یا یک ثابت را ارائه می‌دهد در حالی که گره نوشتن یک پورت خروجی اصلی یا یک واحد ذخیره سازی را ارائه می‌دهد. یک گره عملگر یک واحد عملیاتی ریاضی یا منطقی را ارائه می‌دهد در حالی ADN یک مقداری از مجموعه مقادیری را انتخاب می‌کند که بر اساس شرایط محاسبه شده توسط واحدهای عملیاتی منطقی منطقس فرآهم شده است. اگر یکی از ورودی‌های شرط TRUE باشد مقدار داده ورودی مربوطه انتخاب شده خواهد بود.

4-2) مثال ATPG محصول محدودیت

شکل 7 یک کد VHDL را برای محاسبه بزرگترین مقسوم علیه مشترک(21) (GCD) از دو تا ورودی IN1 و IN2 نشان می‌دهد. شکل 8 بدون وارد شدن به جزئیات بیشتر ADD را برای مجموعه کامل محدودیت‌های استخراج شده برای GCD را نشان می‌دهد. به عبارت دیگر MUT می‌تواند با استفاده از یکی از دو مسیر آزمون ارائه شده در شکل 7.a و 7.b تست شود. دو مسیر آزمون شامل یک محدودیت فعال مسیر و یک مسیر است که جز جابجا شدن ورودی‌ها کاملا یکسانند. توجه شود که از نقطه نظر دسترسی به MUT این دو محیط هم ارزند. فرم DNF برای این محیط آزمون به این صورت می‌شود:
( x1 ≠ x2 ) Λ (x1 > x2) V ( x1 ≠ x2 ) Λ (x1 < x2)
که کمینه کردن آن مانند شکل 9 می باشد.
( x1 ≠ x2 ) Λ (x1 > x2) V ( x1 ≠ x2 ) Λ (x1 < x2) = (x1 > x2)
شکل 10 ، ADD را برای محیط کمینه شده نشان می‌دهد، محدودیت نشان می‌دهد که MUT تنها وقتی قابل دسترس است که ورودی اول آن از ورودی دوم بزرگتر باشد ، مثلا : (X1 > X2)

5. معایب روش پیشنهادی

یکی از اصلی‌ترین محدودیت‌های پیاده‌سازی روش تست غیرقابل تشخیص بودن سلسله مراتبی این است در آن مدارهای RTL در نظر گرفته شده بر این موضوع که به دو قسمت کنترل و مسیر داده تقسیم شود تاکید می‌کند در حالی که در اکثریت RTL های دنیای واقعی مفهوم قسمت کنترل تنها وجود ندارد. محدودیت دیگرش این است که در این روش ماژول انتخاب شده برای تحلیل غیر قابل تست بودن از طراحی RTL باید ترکیبی باشد و برای ماژول دلخواه ترتیبی کار نمی‌کند. پیچیدگی DNF محدودیت‌ها در مرحله کمینه کردن با افزایش K رشد نمایی دارد، که درآن K محدودیت چرخه فعال‌سازی مسیر است.

6- نتایج تجربی

برای بررسی روش به صورت عملی آزمایشاتی انجام شده است که نتایج آن در جدول‌هایی به صورتی که در ادامه آمده است مشاهده می‌شود، برای این آزمایشات از Benchmarkهای زیر استفاده شده است، یک GCD، یک مولتی پلکسر(22) و یک معادله دیفرانسیل(23).
در جدول 1 زیر زمان سپری شده برای هر کدام از مراحلی که در روش پیشنهادی ذکر شد برای هر کدام از بنچ مارکها آمده است. همان طوری که در جدول 1 ملاحظه می‌شود مرحله استخراج محدودیت‌ها بیشتراز دو دقیقه زمان اجرا نیاز دارد. برای مرحله کمینه کردن، همانطور که در قسمت 5 بحث شد به محدوده زمانی بستگی دارد مثلا برای ADD2 محدوده K ، 7 است و زمان کمینه سازی بیشتر از 4000 s است. سنتز محیط آزمایش از VHDL به سطخ منطقی تقریبا مقدار ثابتی دارد و برای هر ماژول بین 5 تا 10 ثانیه است، در حالی که ATPG برای هر MUT کمتر از 0.02 ثانیه را می‌گیرد. جدول 2 شامل آمار دقیق از مدار تجزیه و تحلیل است. جدول 2 لیستی از تعداد کل خطاهای چسپان در کل مدار را نشان می‌دهد، و سپس تعداد خطاهای تست شده، خطاهای غیر قابل مشاهده و غیر قابل کنترل، خطاهای رجیستری غیر قابل آزمایش، خطاهایی مکه طبق روش پیشنهادی اثبات شد که غیرقابل آزمونند و در نهایت خطاهای باقیمانده را نشان می‌دهد. جدول 3 به مقایسه این روش و روش ATPG تجاری می‌پردازد. در جدول 3 میزان پوشش خطا میزان کارایی روش را نشان می‌دهد که به طور میانگین در روش پیشنهادی بین 8 الی 14 درصد بیشتر است.

نتیجه گیری :

در اینجا روشی برای تحلیل خطای مدل چسپان غیر قابل آزمون سلسله مراتبی در مدارهای ترتیبی ارائه شد. روش بر اساس استخراج کردن و کمینه کردن محدودیت‌های مسیر آزمون RTL بود که این مراحل محصولی را برای ATPG به دست می‌دادند. در انجا یک روش مرسو ن برای کمینه کردن محدودیت‌های مسیر آزمون ارائه شد. برای ارزیابی روش مورد نظر از آزمایش آن روی بنچ مارکهای ترکیبی استفاده شد و مشاهده شد که قادر به تولید آزمون با حداکثر بازدهی برای ماژول های جاسازی شده در RTL است.

پي‌نوشت‌ها:

1-کارشناسی ارشد معماری کامپیوتر
2- Automated Test Pattern Generation
3 - Fault Oriented
4 - Hierarchical untestability
5 - Combitional
6 - stack- at
7 - Module Under Test
8 - deterministic
9 - top- down
10 - Bottom- up
11 - Synopsys Design Compiler
12 - Register Transfer Level
13 - datapath
14 - Finite State Machine
15 - Manifestation
16 - Disjunctive Normal Form
17 - quantifier-free bitvector
18 - negation normal form
19 - Assignment decision diagram
20 - assignment decision node
21 - Greatest Common Divisor
22 - Mux 8x8
23 - differential equation

مراجع :
1. Agrawal VD, Chakradhar ST (1995) Combinational ATPG theorems for identifying untestable faults in sequential circuits. IEEE Trans Comput Aided Des 14(9):1155–1160.
2. Brayton RK, Hachtel GD, McMullen CT, Sangiovanni-Vincentelli AL (1984) Logic Minimization Algorithms for VLSI Synthesis. Kluwer Academic Publishers, Boston
3. Chayakul V, Gajski DD, Ramachandran L (1993) High-Level Transformations for Minimizing Syntactic Variances, DAC (Proceedings of the Design Automation Conference), Dallas, Texas, USA, p 413– 418.
4. De Moura L, Bjørner N (2008) Z3: An Efficient SMT Solver. TACAS (International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS)), Budapest, Hungary, p 337–340.
5. Dillig I, Dillig T, Aiken A (2010) Small Formulas for Large Programs, Proc. of the 17th intl. conf. on Static Analysis, SpringerVerlag, Berlin, Heidelberg, p 236–252 .
6. Fujiwara H, Ooi CY, Shimizu Y (2008) Enhancement of Test Environment Generation for Assignment Decision Diagrams, 9th IEEE Workshop on RTL and High Level Testing, Nov. IEEE, Sapporo, Japan, 45–50
7. Ghosh I, Fujita M (2000) Automatic test pattern generation for functional RTL circuits using assignment decision diagrams, Proc. DAC 520 J Electron Test (2012) 28:511–521. (Proceedings of the Design Automation Conference), Los Angeles, California, USA, p 43–48
8. HLSynth92 benchmarks.http://ftp.ics.uci.edu/pub/hlsynth/HLSynth92.
9. ITC benchmarks.http://www.cerc.utexas.edu/itc99-benchmarksbench.html
10. Iyer MA, Long DE, Abramovici M (1996) Identifying sequential redundancies without search. In: Proc. 33rd Annu. Conf. DAC, LasVegas, pp 457–462.
11. Jervan G et al (2002) High-Level and Hierarchical Test Sequence Generation. IEEE HLDVT, Cannes, 169–174
12. Lee J, Patel JH (1994 Oct) Architectural level test generation for microprocessors, IEEE Trans. CAD (IEEE Transactions on CAD of Integrated Circuits and Systems), Piscataway, New Jersey, USA, p 1288–1300.
13. Liang H-C, Lee CL, Chen EJ (1995) Identifying untestable faults in sequential circuits. IEEE Des Test Comput 12(3):14–23.
14. Long DE, Iyer MA, Abramovici M (2000) FILL and FUNI: Algorithms to identify illegal states and sequentially untestable faults. ACM Trans Des Autom Electron Syst 5(3):631–657
15. Murray BT, Hayes JP (1988) Hierarchical test generation using precomputed tests for modules, Proc. ITC (Proceedings of the International Test Conference), Washington, D.C., USA, p 221–
229.
16. Peng Q, Abramovici M, Savir J (2000) MUST: multiple stem analysis for identifying sequential untestable faults. In: Proc. Int. Test Conf. IEEE, Atlantic City, NJ, USA, p 839–846
17. Raik J, Fujiwara H, Ubar R, Krivenko A (2008) Untestable fault identification in sequential circuits using model-checking. ATS (Proceedings of the Asian Test Symposium), Sapporo, Japan, p 667–672
18. Raik J, Rannaste A, Jenihhin M, Viilukas T, Ubar R, Fujiwara H (2011) Constraint-Based Hierarchical Untestability Identification for Synchronous Sequential Circuits, Proc. of the European Test Symposium, IEEE Computer Society, Trondheim, Norway, p 147– 152
19. Raik J, Ubar R (1999) Sequential Circuit Test Generation Using Decision Diagram Models, Proceedings of the DATE Conference, IEEE Computer Society, Munich, Germany, p 736–740
20. The ECLiPSe Constraint Programming Systemhttp://eclipseclp.org/
21. Vedula V, Abraham J (2002) FACTOR: A Hierarchical Methodology for Functional Test Generation and Testability Analysis, DATE Conf., IEEE Computer Society, Paris, France, p 730–734
22. Viilukas T, Raik J, Jenihhin M, Ubar R, Krivenko A (2010). Constraint-based test pattern generation at the register-transfer level, 13th IEEE DDECS Symposium, IEEE Computer Society, Vienna, Austria, p 352–357
23. Zhang L, Ghosh I, Hsiao M (2003) Efficient Sequential ATPG for Functional RTL Circuits, Int. Test Conf., IEEE, Charlotte, NC, USA, p 290–298