1. 16.1 Системи генерації тестів

Анотація: В лекції розглядається проблема побудови перевіряючих тестів для цифрових схем. Описана загальна архітектура системи побудови перевіряючих тестів. Викладено методи генерації тестів для комбінаційних схем, які використовуються на початковому етапі, і не орієнтовані на конкретну несправність. До них відносяться псевдовипадкове побудова і метод критичних шляхів.

Генерація перевіряючих тестів навіть для комбінаційних схем цифрових систем є складною як у математичному, так і в технічному плані проблемою. Її найважливішими аспектами є:

1. вартість генерації тестів;
2. якість генеруються тестів;
3. вартість тестування схеми з допомогою побудованих вхід-вихідних послідовностей.

Перш за все, слід розрізняти функціональні і структурні тести. Алгоритми побудови функціональних тестів генерують повне безліч різноманітних тестових наборів, які дозволяють повністю перевірити функцію, реалізовану даною схемою. Наприклад, для комбінаційної схеми з входами і одним виходом функціональним тестом є безліч всіляких тестових довічних наборів, що дозволяє відновити булеву функцію, яка реалізується тестируемой схемою. Очевидно, що для схем великої розмірності такий підхід не завжди прийнятний.

З іншого боку, структурні тести перевіряють тільки мінімально необхідне безліч несправностей (як правило, одиночних константних несправностей після процедури скорочення списку, викладеної в "Моделі логічних елементів" ). Далі ми, в основному, будемо розглядати структурні тести.

У теоретичному аспекті показано [ 16.1 ], Що генерація тестів відноситься до класу NP-повних проблем (тобто переборного типу), для яких не існує алгоритмів рішення полиномиальной складності. У практичному аспекті складність її вирішення залежить від застосовуваного алгоритму генерації тесту. Ефективність розроблюваних алгоритмів прийнято перевіряти на схемах з різних міжнародних каталогів (benchmarks): ISCAS85 [ 16.2 ], ISCAS89 [ 16.3 ], ITC99 [ 16.4 ] І ін. Псевдовипадкові методи генерації тестів мають низьку складність алгоритму, але дають довгі тестові послідовності і невисоку повноту. Детерміновані методи генерації дають тести кращої якості, але мають велику складність. Якість побудованих тестів визначається, як правило, за допомогою програм моделювання несправних схем, в яких реалізуються методи, розглянуті в попередньому розділі. Безпосередньо процес тестування проводиться на спеціальному обладнанні - тестерах, які забезпечують подачу вхідних тестових впливів на схеми, з'їм вихідних сигналів і їх порівняння з еталонними значеннями. Найважливішими характеристиками тестерів є тактова частота і обсяг пам'яті для зберігання тестових впливів.

Структурні методи генерації тестів поділяються на два класи:

1. побудова тесту для схеми в цілому безвідносно конкретної несправності;
2. побудова тесту для конкретної заданої несправності.

У першому розділі розглядається структура системи генерації тестів, в наступних двох "Синтез тестів для комбінаційних схем" -16.3 описані методи побудови тестів, які використовуються на початковому етапі генерації перевіряючих тестів для всієї схеми. У наступних розділах будуть викладені методи побудови тестів для конкретної несправності, які, як правило, використовуються на заключному етапі генерації тестів. З нашої точки зору, їх доцільно застосовувати на останньому етапі, коли залишилося відносно невелике число неперевірених несправностей. На початковому етапі краще застосовувати іншу стратегію. Потрібні швидкодіючі і прості в реалізації методи побудови тестів, які дозволяють з малими витратами часу отримати тест для більшої частини несправностей. Одним з таких методів є псевдовипадковий метод генерації тестів, досить докладно описаний в літературі [ 16.5 , 16.6 ].

16.1 Системи генерації тестів

Метою автоматизованої системи генерації тестів є побудова перевіряючого тесту для даної схеми. При цьому бажано, щоб:

1. повнота побудованого тесту була максимальна;
2. вартість генерації тестів (процесорний час) була мінімальна;
3. отриманий тест мав мінімальну довжину.

Це випливає з економічних вимог. Повнота тесту безпосередньо впливає на якість виробленої продукції. Довжина тесту впливає на вартість тестування ЦУ і визначає характеристики необхідних тестерів і час тестування.

Слід зазначити, що повнота тесту повинна визначатися щодо перевіряються (ненадлишкових) несправностей. Так, наприклад, для схеми, що має 5% надлишкових несправностей, повнота тесту 96% є явно недосяжною. Тому іноді розрізняють повноту і ефективність тесту, які визначаються наступним чином. повнота - , де - загальне число несправностей і - число перевіряються на даному тесті несправностей. ефективність - , де - число надлишкових несправностей.

Кількісні значення повноти (і ефективності) тесту, очевидно, також істотно залежить від того, як формувалося безліч несправностей. Сучасні системи, як правило, використовують методи скорочення списків несправностей, засновані на відносинах еквівалентності і домінування, які були розглянуті в "Моделі логічних елементів" .

Сучасна система генерації тестів включає в себе наступні основні компоненти:

1. Програми генерації тестів, які дозволяють швидко отримати на першому етапі початкову тестову послідовність і працюють зі схемою в цілому, а не орієнтовані на конкретну несправність;
2. Програми моделювання несправних схем, що дозволяють на поточний момент оцінити досягнуту повноту тесту і визначити безліч неперевірених несправностей, для яких необхідно добудувати тест;
3. Програми побудови тесту для конкретної заданої несправності, які використовуються на другому етапі генерації тесту при його "доведенні" до необхідної повноти;
4. Програми стиснення тестів, які дозволяють компактно об'єднати фрагменти тестів, отриманих на різних етапах.

Структура системи генерації тестів представлена ​​на Мал. 16.1 . Тут в першій фазі зазвичай використовуються псевдовипадкові алгоритми (або методи критичних шляхів і т.п.), які досить швидко дозволяють досягти прийнятної повноти початкового тесту 50-80%. Після цього виконується моделювання несправностей і визначається безліч неперевірених несправностей, яке обробляється на другому етапі.

Мал.16.1.

Структура системи генерації тестів

Псевдокод укрупненого алгоритму генерації тестів першого етапу представлений нижче.

Перша фаза закінчується при досягненні необхідної для першої фази повноти тесту, яка визначається користувачем, або внаслідок ліміту часу. При цьому число несправностей, що перевіряються одним тестовим набором, спочатку досить велике, а потім швидко зменшується. Відповідно число не включені в тест вхідних наборів швидко зростає. В кінці першої фази формується безліч неперевірених несправностей, тести для яких далі генеруються в другій фазі.

Перша фаза (схема) {While (повнота або час не досягнуто) {Генерація тесту (t); Моделювання несправностей (t); p = число знову перевіряються несправностей (t); if (p прийнятно) then включення t в тест; }} Друга фаза (схема, безліч несправностей) {while (є необроблені несправності) {вибір нової несправності f; генерація тесту t для f; if (тест для f побудований) then {включення t в тест; моделювання несправностей на наборі t; виключення несправностей, що перевіряються t; }}}

Вище представлений псевдокод другої фази генерації тесту. При побудові тесту для даної несправності можна використовувати один з розглянутих вище методів. Слід зазначити, що час генерації тесту для поточної несправності необхідно контролювати.

Якщо воно перевищує певний задається користувачем поріг, то несправність виключається з подальшої обробки і оголошується не перевіряється. Найбільші витрати часу мають місце для надлишкових несправностей, для яких в гіршому випадку може знадобитися повний перебір всіляких вхідних значень.

Тому має сенс на етапі препроцесорної обробки схеми, по-можливості, знайти і виключити з подальшої обробки надлишкові несправності. Істотний вплив на ефективність генерації тесту надає також метод вибору нової несправності. Зазвичай вибираються несправності, розташовані якомога ближче до зовнішніх входів схеми. Це обумовлено тим, що побудований для такої несправності тест активізує в схемі довгий шлях і тому перевіряє більше несправностей.

Це веде до болем коротким тестовим послідовностям. Друга фаза закінчується, коли оброблені всі несправності з певного в першій фазі безлічі. Але можливий і достроковий останов через перевищення лімітів процесорного часу або довжини тесту.