Методи синтезу структурних тестів для цифрових синхронних схем на основі апаратних засобів, що реконфігуруються

Размещено на http://www.allbest.ru/

Одеський національний політехнічний університет

УДК 681.518.54

Автореферат

дисертації на здобуття наукового ступеня кандидата технічних наук

Методи синтезу структурних тестів для цифрових синхронних схем на основі апаратних засобів, що реконфігуруються

Спеціальність 05.13.05 - Комп'ютерні системи та компоненти

Борисевич Олексій Валерійович

Одеса - 2008

Дисертацією є рукопис.

Роботу виконано в Севастопольському національному технічному університеті Міністерства освіти і науки України на кафедрі кібернетики та обчислювальної техніки.

Науковий керівник доктор технічних наук, професор Скатков Олександр Володимирович, Севастопольський національний технічний університет, завідувач кафедри кібернетики та обчислювальної техніки

Офіційні опоненти:доктор технічних наук, професор, Дрозд Олександр Валентинович, Одеський національний політехнічний університет, професор кафедри комп'ютерних інтелектуальних систем та мереж

доктор технічних наук, професор, Мусієнко Максим Павлович, Черкаський державний технологічний університет, професор кафедри комп'ютеризованих i інформаційних технологій у приладобудуванні

Захист відбудеться «22» ____01_____ 2009 р. о 13³⁰ на засіданні спеціалізованої вченої ради Д 41.052.01 при Одеському національному політехнічному університеті за адресою: 65044, м. Одеса, пр. Шевченка 1, ауд. 400-А.

З дисертацією можна ознайомитися в бібліотеці Одеського національного політехнічного університету за адресою: 65044, м. Одеса, пр. Шевченка 1.

Автореферат розісланий «19» ____12_____ 2008 р.

Вчений секретар спеціалізованої

вченої ради Ю.С. Ямпольський

схема пам'ять автомат обчислення

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

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

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

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

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

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

Дисертаційна робота виконана відповідно до плану науково-дослідної роботи Севастопольського національного технічного університету № Е503-42/2003 «Моделювання і діагностика цифрових, аналого-цифрових і мікропроцесорних РЭА» (№ ДР 0104U003502). Крім того, окремі результати дисертаційних досліджень були отримані згідно планів НДР № 286-Н «Розробка систем автоматизованого проектування пристроїв на СВІС» (№ ДР 0108U003512).

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

Для досягнення зазначеної мети в роботі розв'язані наступні задачі:

- виконано аналіз існуючих методів побудови тестових послідовностей для схем з пам'яттю та вибрані перспективні напрямки їхнього вдосконалювання;

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

- розроблено еволюційний метод синтезу тестів з використанням апаратного прискорення;

- розроблено алгоритм оцінки довжини тестових послідовностей автомата та запропоновані співвідношення для вибору між програмною і апаратною системами синтезу тестів;

- розроблено апаратні засоби прискорення обчислень при синтезі тестів еволюційними методами, що оптимально використовують ресурси програмувальних логічних інтегральних схем (ПЛІС);

- здійснено апробацію результатів дослідження на міжнародній бібліотеці послідовних схем ІSCAS-89.

Об'єктом дослідження є процес контролю і структурної діагностики цифрових синхронних схем з пам'яттю.

Предметом дослідження є методи та засоби синтезу структурних тестів для діагностики несправностей у цифрових синхронних схемах з пам'яттю.

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

1. Вперше розроблений апаратно-орієнтовний метод розв'язання задачі синтезу тестів, який поєднує застосування апаратних засобів для прискорення комбінаторного перебору, декомпозицію схеми та використання еволюційних алгоритмів.

2. Вперше доведено збіжність компактного генетичного алгоритму з моделюванням элітизма до глобального оптимуму ін'єктивної цільової функції.

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

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

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

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

Запропоновані в роботі методи та апаратні структури є основою експериментальних програмних і програмно-апаратних засобів для синтезу тестів, що перевіряють, цифрових синхронних схем з пам'яттю.

Результати дослідження впроваджені в ЗАТ «НТП ЮБК-Спектр» у програмно-апаратному комплексі АСК для ремонту і діагностики спеціалізованої електронної техніки, вінницькому заводі «Термінал» у діагностичній програмно-апаратній системі ПАРМ.

Особистий внесок здобувача полягає в удосконаленні і розробці нових методів і засобів, які дозволили вирішити сформульовані задачі дослідження. В роботах, опублікованих у співавторстві, здобувачеві належить: узагальнення методу PODEM для функціональних елементів схем довільного базису та удосконалення генетичного алгоритму для побудови настановних послідовностей [1]; генетичний алгоритму для побудови тестів синхронних схем з множиною тактових входів [2]; функціональна модель та експериментальна реалізація системи [3]; умови транспортування і генерації несправностей, виражені через тестові ситуації [8]; оцінка ефективності засобу в порівнянні із програмною реалізацією [9]; узагальнення методу, заснованого на моделі скорочення-зникнення термів булевої функції для багаторівневих вентильних схем [11]; цільова функція і алгоритм оптимізації для пошуку установної послідовності автомата [13]; декомпозиціний алгоритм синтезу тесту [14]; архітектура апаратного засобу рішення задачі здійсненності булевої формули [15]; цільові функцій з властивостями унімодальності та ін'єктивності [16].

Апробація результатів дисертації. Основні наукові положення і результати, отримані автором при виконанні дисертаційної роботи, розглядалися на III міжнародній науковій конференції «Інтелектуальні системи прийняття рішень і прикладні аспекти інформаційних технологій ISDMIT'2007» (Євпаторія, 2007); IX міжнародній науково-технічній конференції «Системний аналіз і інформаційні технології» (Київ, 2007); «Сучасні проблеми радіотехніки і телекомунікацій», (Севастополь, 2007 - 2008); міжнародній науково-практичній конференції «Інформаційні технології і інформаційна безпека в науці, техніку і утворенні ИНФОТЕХ» (Севастополь, 2007 - 2008); Всеукраїнській науково-технічній конференції «Системи автоматики і автоматичне керування» (Севастополь, 2006); а також на розширеному засіданні наукового семінару кафедри «Комп'ютерні інтелектуальні системи та мережі» Одеського національного політехнічного університету (Одеса, 2008).

Публікації. Основні результати дисертації опубліковані в 16 друкованих працях, серед яких 5 статей у збірниках наукових праць, що включені до списку спеціальних видань ВАК, а також 11 тез доповідей у збірниках матеріалів наукових конференцій.

Структура і обсяг дисертації. Дисертація складається із вступу, п'яти розділів, висновків і додатків. Повний обсяг дисертації становить 189 сторінок. Робота містить 56 рисунків, 21 таблицю, 4 додатки на 40 сторінках, та посилення на 129 джерел.

ОСНОВНИЙ ЗМІСТ РОБОТИ

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

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

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

Об'єктом тестування є комбінаційна частина цифрової синхронної схеми з пам'яттю (з єдиним тактовим входом). Схема , що представляється мультиграфом , де - множина логічних елементів схеми, - множина з'єднань, декомпозується на множину фрагментів (підсхем) , . У роботі застосований алгоритм декомпозиції схеми на підсхеми без розгалужень, що дозволило використовувати теорему про домінування і еквівалентність несправностей. Розбивка схеми може бути заданим, якщо цифровий пристрій синтезований на функціональних елементах відомого базису (мультіплексоры, суматори і т.д.), у такому випадку досягається скорочення часу синтезу тесту за рахунок повторного використання тестової інформації, отриманої для кожного типу функціональних елементів схеми.

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

- системи булевих функцій вичерпних тестових перевірок ,

- системи булевих функцій прозорості входів ,

- булевої функцій для опису стану виходу,

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

Запропонованому алгоритму властиві основні достоїнства програмних реалізацій методу PODEM.

1. Перебір тільки по вхідних наборах (не по елементах схеми, як у класичному D-Алгоритмі).

2. Максимальне використання засобів моделювання схем.

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

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

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

- відсутність поділу на окремі етапи побудови тесту для комбінаційної частини і обчислення настановної послідовності;

- детерміноване обчислення тестів для підсхем, що скорочує час побудови тестів і поліпшує їх якість;

- моделювання схеми на рівні підсхем, а не на рівні логічних елементів, що зменшує загальний час обчислень;

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

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

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

, (1)

, ,

,

де:

- множина булевих функцій, виконання яких необхідно для активізації несправності,

- кількість змінних, від яких залежить булева функція ,

- множина підсхем, виходи яких є виходами схеми,

- точка простору двійкових наборів така, що , де - відстань між векторами по Хемингу.

Коефіцієнти в (1) обчислюються таким чином:

1. , для підсхеми , яка містить несправність, що тестується, де - логічна умова генерації несправності.

2. , якщо крізь не транспортується сигнал несправності.

2. , де - множина вхідних сигналів підсхеми , - умова транспортування сигналу із входу на вихід , - значення коефіцієнта для підсхеми, підключеної до входу .

Для цільової функції (1) показано, що приймає максимальне значення тоді і тільки тоді, коли послідовність є тестовою для заданої несправності.

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

У третьому розділі сформульований і досліджений новий еволюційний метод синтезу тестів з використанням засобів апаратного прискорення.

Представлено аналіз ефективності апаратного прискорення еволюційного пошуку тестових послідовностей. Запропоновано співвідношення для вибору між програмною і апаратною системами синтезу тестів з метою одержання найменшого часу рішення:

,

,

де: - оцінка відносини середнього часу рішення задачі синтезу тесту із застосуванням програмної реалізації еволюційного пошуку до часу рішення із застосуванням апаратно-оріентовного методу, - мінімальний час підготовки апаратних засобів до роботи; - кількість входів у схемі, що тестується; - середня довжина тестової послідовності; - кількість логічних елементів у схемі, - кількість константних несправностей, що тестуються; - питома продуктивність системи моделювання несправностей (середній час моделювання одного логічного елемента); - час такту роботи синхронної схеми, що тестується; - питома продуктивність системи логічного синтезу (середній час синтезу в ПЛІС одного логічного елемента); - коефіцієнти, що характеризують розмір простору пошуку від бітової довжини тестової послідовності.

Для оцінки середньої довжини тестових послідовностей запропоноване інтервальне подання сигналів у цифровій схемі. Сигналу в синхронної схемі зіставляється матриця виду:

,

,

де компоненти описують потенційну можливість установки відповідних логічних значень: сигнал може прийняти значення логічної 1 на тактах з по , і логічного 0 у часовому інтервалі з по .

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

На основі інтервального подання сигналів запропонований новий метод оцінки довжини тестових послідовностей, що полягає в наступному:

- справна схема моделюється з використанням інтервального подання сигналів, у результаті чого для кожного первинного виходу обчислюється інтервальна матриця сигналу ;

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

- оцінка довжини тестової послідовності для несправності заснована на обчисленні інтервальних матриць вихідних сигналів логічних елементів XOR, входи яких підключені до виходів справної та несправної схем.

Сформульовано метод синтезу тестів з використанням спільно реалізованої в ПЛІС системи моделювання несправностей і оптимізаційного алгоритму.

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

В якості оптимізаційного алгоритму за критерієм мінімуму необхідної пам'яті обраний компактний генетичний алгоритм Compact GA, запропонований Р. Хариком.

Траєкторія компактного генетичного алгоритму апроксимована векторним диференціальним рівнянням:

, (2)

де: - вектор ймовірності одиничного значення в хромосомах; - вектори хромосом; - вектор значень математичних очікувань, обчислених для кожного компонента ; - розмірність вектора рішення задачі оптимізації; . В (2) завжди виконується , де -скалярна цільова функція, що оптимізується;

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

Теорема 1. Точка фазової траєкторії є стаціонарною, якщо і тільки якщо цільова функція ін'єктивна, та у точці досягає максимуму: для всіх .

Теорема 1 установлює умову асимптотичної збіжності алгоритму і формулює вимогу ін'єктивності для цільової функції, що оптимізується.

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

,

де - підсхема без розгалужень у схемі ; - схема, в яку введено несправність; функції визначені для кожної пари елементів (, ) так, що якщо сигнали на виходах елементів і різні, - рівні; - вагові коефіцієнти, пропорційні мінімальній відстані від виходу підсхеми до виходів схеми ; - ознака активності в підсхемі : якщо існує хоча б один елемент , для якого , у протилежному випадку ; - вагові коефіцієнти:

,

де - мінімальна відстань від елемента до , - множина вихідних елементів схеми.

Показано, що дана цільова функція ін'єктивна та має максимум , якщо і тільки якщо є тестовою послідовністю, що перевіряє, для заданої несправності.

Четвертий розділ присвячений розробці апаратних засобів для розв'язання задачі синтезу тестів цифрових схем з пам'яттю, які оптимально використовують ресурси програмувальних логічних інтегральних схем.

На підставі з доведеної результативності алгоритму Compact GA поставлена задача збільшення його продуктивності за рахунок апаратної реалізації в ПЛІС. Представлена последовно-паралельна реалізація алгоритму Compact GA.

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

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

На основі розглянутого підходу розроблений апаратний засіб із застосуванням ПЛІС Altera Cyclone III EP3C25Q240. Здійснено експериментальне дослідження різних варіантів апаратної реалізації алгоритму Compact GA, результати якого підтверджують значну перевагу (в 2,5 - 6 разів при повністю комбінаційному обчисленні цільової функції) запропонованих апаратних засобів над програмною реалізацією алгоритму за часом рішення задач оптимізації. Алгоритм Compact GA і його апаратна реалізація є основою спеціалізованого програмно-апаратного засобу синтезу тесту схем з пам'яттю.

Зроблено порівняння наступних варіантів апаратної реалізації модуля обчислення цільової функції з урахуванням декомпозиції схеми на підсхеми без розгалужень:

- послідовна організація обчислення цільової функції, у якому кожний додаток обчислюється за один такт;

- повністю паралельне обчислення , у якому для підсумовування компонентів використовується дерево суматорів;

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

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

біт.

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

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

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

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

Основа пропонованої системи - контролер K, який є програмувальним автоматом, що здійснює керування всім процесом побудови тесту. Модуль S' - це схема, що тестується, у яку по шині E з контролера K уводяться несправності. Схема S - дублікат S', у якій по вихідних сигналах елементів S і S' формуються вектори активності . Блок GA - модуль, що апаратно реалізує алгоритм Compact-GA. У процесі роботи сформовані модулем GA вектора рішень X(t) і Y(t) послідовно подаються на входи схем S' і S. Блок обчислення цільової функції F(X) на основі результатів моделювання схем S і S' обчислює оцінки і , а також ознаку для послідовностей і , , і формує результат порівняння , на основі якого здійснюється генерація нового покоління рішень X і Y і триває ітеративний процес оптимізації.

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

1. Декомпозиція схеми на одновихідні підсхеми .

2. Розрахунок вагових коефіцієнтів цільової функції і .

3. Генерація мовного опису схем S і S'.

4. Логічний синтез всієї системи з модулів S, S', F(X), GA, K.

5. Для всіх несправностей схеми: введення несправності в схему S', запуск алгоритму оптимізації, збереження тестової послідовності.

У п'ятому розділі представлені основні результати тестування експериментальних реалізацій запропонованих програмно-апаратних методів і засобів на бібліотеках схем ISCAS-89. Наведено результати порівняння методів разом з програмною реалізацією алгоритму GATTO - широко відомого методу синтезу тестів, заснованого на генетичних алгоритмах.

Для розв'язання задачі побудови тестів за допомогою еволюційного пошуку і моделювання несправностей розроблений апаратний засіб на основі програмувальної логічної схеми Cyclone III EP3C25Q240.

Програмна частина системи синтезу тестів складається з наступних підсистем: модуля аналізу текстового опису схеми (підтримуються описи списків зв'язку елементів на мовах Verilog і у форматі Bench), модуля кластеризації (розбивки схеми на підсхеми), модуля обчислення коефіцієнтів для елементів і під схем та модуля формування текстового опису апаратної системи.

Результати застосування методу, заснованого на апаратній реалізації генетичного алгоритму, до найскладніших схем бібліотеки ISCAS-89, а також порівняння швидкодії з методом GATTO наведені в табл. 1. В таблиці , , відповідно, - сумарний час побудови тесту, що перевіряє, за допомогою програмно-апаратного засобу (разом з часом компіляції апаратних структур ПЛИС) і частка несправностей, що тестуються; , , відповідно, - час побудови тесту і частка несправностей, що тестуються методом GATTO. Реалізація методу GATTO і програмна частина запропонованої системи запускалися на одній комп'ютерній платформі: AMD Sempron 3600+ 2GHz, DDRII 1024 Mb. Представлені в таблиці 1 числові значення є математичними очікуваннями відповідних характеристик. Для обробки експериментальних даних використані стандартні процедури математичної статистики та теорії ймовірності.

Таблиця 1. Системні характеристики апаратного засобу синтезу тестів, отримані для складних схем бібліотеки ISCAS-89.

Схема	FCGATTO,%	TGATTO,з	LGATTO	FCHard,%	THard,з	LHard
S13207	27,32	1889,04	544	28,3	698,126	572
S15850	8,37	2828,31	153	9,02	901,542	161
S35932	89,85	3995,25	903	92,02	1105,65	949
S38417	20,59	39204,09	1565	20,59	10310,98	1644
S38584	49,9	39528,03	5500	50,35	9705,57	5775

Проведене спільне порівняння запропонованих методів на схемах бібліотеки ISCAS-89. За результатами експериментів дані рекомендації з використання методів, залежно від критеріїв оптимальності (кількість несправностей, що покриваються, час побудови тесту) і розмірності схем.

Встановлено, що додаткові апаратні витрати, пов'язані з організацією обчислювального процесу синтезу тестів, знижуються із зростанням складності схеми, що тестується, а прискорення, що досягається, монотонно зростає (табл. 2).

Експериментальні результати застосування різних програмних реалізацій алгоритмів до схем бібліотеки ISCAS-89 зведені до діаграми на рис. 3. Використано наступні позначення методів: GATTO - метод побудови тесту GATTO; MixedGA - змішаний генетико-символьний метод; HardGA - метод спільної апаратної реалізації генетичного алгоритму і системи моделювання несправностей.

Таблиця 2. Порівняння складності апаратної реалізації системи синтезу тестів схеми для ряду схем бібліотеки ISCAS-89 різної розмірності.

Схема	Кількість тригерів	Кількість вентилів	Логічна складність системи S	Відношення h=S/(NGates+NDFF)	Часовий виграш, %
s420.1	16	254	860	3.671	12.55
s444	21	212	727	3.596	0.34
s35932	1728	18149	63460	3.51	72.47
s38417	1636	23950	85443	3.555	73.71
s38584	1452	20996	74114	3.553	75.45

Як випливає з отриманих експериментальних результатів, всі запропоновані методи на більшості схем бібліотеки ISCAS-89 виявляються більш ефективними в порівнянні з методом GATTO. Завдяки застосуванню розробленого апаратного засобу, отримане значне скорочення часу синтезу тесту (на більш, ніж 70 % для окремих схем бібліотеки), практично, без погіршення діагностичних властивостей тесту.

ВИСНОВКИ

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

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

2. Узагальнено метод топологічно-орієнтованого прийняття рішень (Path Oriented DEcision Making - PODEM) для побудови тестів комбінаційних схем, що складаються з функціональних елементів довільної структури. Розроблено генетичний алгоритм для побудови тестів, що перевіряють, і діагностичних тестів, заснований на декомпозиції схеми на підсхеми, які описані в символьному виді системою булевих функцій.

3. Доведено доказ збіжність генетичного алгоритму Compact-GA до глобального оптимуму цільової функції. Отримано послідовно-паралельну апаратну реалізацію алгоритму Compact-GA, що оптимально використовує ресурси ПЛІС. Експериментальні результати показують, що апаратна реалізація алгоритму в ПЛІС перевершує за швидкістю у 2,5 - 6 разів програмну реалізацію Compact-GA на різних функціях, що оптимізуються.

4. Запропоновано цільову функцію, яка враховує декомпозицію схеми на підсхеми без розгалужень, глобальний оптимум якої в просторі вхідних послідовностей відповідає тестовій послідовності для заданої несправності в цифровій схемі з пам'яттю. Розроблено апаратний засіб для обчислення значення цільової функції на основі різниці стану справної і несправної схем з пам'яттю.

5. Запропоновано комплексний метод рішення задачі синтезу тестів, який поєднує застосування апаратних засобів для прискорення комбінаторного перебору, декомпозицію схеми і використання еволюційних алгоритмів, що дозволяє скоротити час синтезу тестових послідовностей в 1,5 - 4 рази в порівнянні із традиційними методами, заснованими на генетичних алгоритмах.

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

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

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

9. Результати дослідження рекомендуються до використання в області виробничого контролю якості виробів мікроелектроніки (цифрових інтегральних мікросхем) при створенні програмних і програмно-апаратних засобів для синтезу тестів, що перевіряють, цифрових схем, а також у діагностичних комплексах при експлуатаційному обслуговуванні електронної техніки.

СПИСОК ОПУБЛІКОВАНИХ ПРАЦЬ ЗА ТЕМОЮ ДИСЕРТАЦІЇ

1. Новоселов В.Г. Декомпозиционный метод построения проверяющего теста для цифровых схем, реализованных на ПЛИС типа CPLD и FPGA / В.Г. Новоселов, А.В. Борисевич // Вестник СевГТУ. Сер. Информатика, электроника, связь: Сб. научн. трудов. - Севастополь: изд-во СевНТУ, 2007. - Вып. 82. - С. 56-63.

2. Борисевич А.В. Генетический алгоритм для построения диагностического теста сложных цифровых схем / А.В. Борисевич, Р.О. Берзин // Вестник СевГТУ: "Информатика, электроника, связь", вып. 74. - Севастополь: изд-во СевНТУ, 2006. -- С. 91-96.

3. Скатков А.В. Система аппаратного моделирования цифровых схем для построения проверяющих тестов эволюционными методами. / А.В. Скатков, А.В. Борисевич // Восточно-Европейский журнал передовых технологий. - 2/6 (26) 2007. - Харьков, 2007. - С. 9-20.

4. Борисевич А.В. Эффективная аппаратная реализация генетического алгоритма COMPACT-GA для поиска экстремума функций / А.В. Борисевич // Оптимизация производственных процессов : сб. науч. тр. Севастоп. нац. техн. ун-т. - Севастополь: изд-во СевНТУ, 2007. - С. 189-195.

5. Борисевич А.В. Система построения тестов цифровых схем на основе аппаратной реализации генетического алгоритма и моделирования неисправностей / А.В. Борисевич // Восточно-Европейский журнал передовых технологий. - 5/2 (29) 2007. - Харьков, 2007. - С. 36-42.

6. Борисевич А.В. Генетический алгоритм для построения проверяющих тестов цифровых схем с памятью на основе символьного представления функциональных элементов // Материалы международной научной конференции «Интеллектуальные системы принятия решений и прикладные аспекты информационных технологий ISDMIT'2007», г. Евпатория, 15-18 мая 2007 г. - Херсон: Изд-во ХМИ, 2007. - Т. 3. - С. 30-33.

7. Борисевич А.В. Об алгебраической структуре NP-трудных задач / А.В. Борисевич // «Автоматизация: идеи, проблемы, решения» : материалы международной научно-технической конференции, г. Севастополь, 8-12 сентября 2008 г. - Севастополь, 2008. - С. 199-201.

8. Новоселов В.Г. Об одном декомпозиционном методе построения проверяющего теста для цифровых схем / В.Г. Новоселов, А.В. Борисевич // Материалы IX международной научно-технической конференции «Системный анализ и информационные технологии» (15 - 19 мая 2007 г., г. Киев). - К.: НТУУ "КПИ", 2007. - С. 158

9. Скатков А.В. Аппаратный подход к ускорению моделирования цифровых схем для построения диагностических тестов / А.В. Скатков, А.В. Борисевич // «Современные проблемы радиотехники и телекоммуникаций РТ-2007», г. Севастополь, 16-21 апреля 2007 г. - Севастополь: Изд-во СевНТУ, 2007. - С. 186.

10. Борисевич А.В. Об оптимальной аппаратной реализации генетического алгоритма поиска экстремума функций / А.В. Борисевич // Материалы международной научно-практической конференции «Проблемы математического моделирования», г. Днепродзержинск, 23-25 мая 2007 г. - Днепродзержинск: изд. ДГТУ, 2007. - С. 21-23.

11. Скатков А.В. Аппаратное ускорение решения задач выполнимости для построения тестов цифровых схем / А.В. Скатков, А.В. Борисевич // Вестник СевГТУ. Сер. Информатика, электроника, связь: Сб. научн. трудов. - Вып. 91. - Севастополь: изд-во СевНТУ, 2008. - С. 47-57.

12. Борисевич А.В. Аппаратный подход к синтезу диагностических тестов цифровых схем с памятью / А.В. Борисевич // Информационные технологии и информационная безопасность в науке, технике и образовании “ИНФОТЕХ-2007”. Материалы международной научно-практической конференции, 10-16 сентября 2007 г. - Севастополь: Изд-во СевНТУ, 2007. - С. 44-48.

13. Новоселов В.Г. Некоторые вопросы эффективного построения проверяющего теста для ПЛИС / В.Г. Новоселов, А.В. Борисевич // Системы автоматики и автоматическое управление : материалы Всеукраинской научно-технической конференции, г. Севастополь, 16-18 мая 2006 г. - Севастополь, 2006. - С. 14-17.

14. Новоселов В.Г. Cмешанный аналитико-генетический подход к построению тестов для цифровых схем / В.Г. Новоселов, А.В. Борисевич // Computer-aided design of discrete devices CAD DD'2007. Материалы VI международной конференции 14 - 15 ноября 2007 г., г. Минск. НАН Беларуси, Институт технической кибернетики. - Минск, 2007. - Т.2. - С. 221-228.

15. Борисевич А.В. Аппаратное ускорение вычисления дизъюнкций в методе решения задач выполнимости WalkSAT / А.В. Борисевич, А.В. Скатков // Материалы XII Международного молодежного форума «Радиоэлектроника и молодежь в XXI веке», г. Харьков, 1-3 апреля 2008 г. - Харьков: изд-во ХНУРЭ, 2008. - С. 85.

16. Скатков А.В. Выбор целевых функций для решения задач синтеза тестов цифровых схем эволюционными методами / А.В. Скатков, А.В. Борисевич // «Современные проблемы радиотехники и телекоммуникаций РТ-2008», г. Севастополь, 15-19 апреля 2008 г. - Севастополь: Изд-во СевНТУ, 2008. - С. 201.

АНОТАЦІЯ

Борисевич А.В. Методи синтезу тестів для цифрових синхронних схем на основі апаратних засобів, що реконфігуруються. - Рукопис.

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 05.13.05 - Комп'ютерні системи та компоненти. - Севастопольський національний технічний університет, Севастополь, 2008.

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

Ключові слова: моделювання несправностей, апаратне прискорення алгоритмів, синтез тестів, еволюційні алгоритми, змішані пошукові стратегії.

ANNOTATION

Borisevich A.V. Methods for synthesis of tests for synchronous digital circuits based on reconfigurable hardware. - The manuscript.

The thesis grace candidate of technical sciences, specialty 05.13.05 - Computer systems and components. - Sevastopol National Technical University, Sevastopol, 2008.

In the thesis discusses the methods of synthesis of tests for synchronous digital circuits with memory. We propose methods that use structural decomposition testing, symbolic analysis of fragments of the circuit, as well as hardware support for the process of synthesis and simulation test failures. The problem of effective use of hardware acceleration of evolutionary search test sequences is solved. Algebra, that describe the controllability of signals in digital synchronous circuits and an algorithm for evaluating the length of test sequences proposed. Developed new fitness functions for the solution of the evolutionary synthesis test methods that have injectivity and unimodal properties, and economically implemented in hardware. A hardware architecture for the synthesis of tests, based on shared hardware implementation of the search algorithm and fault simulation subsystem. Using the proposed methods and algorithms can substantially increase the speed of synthesis of checking tests for synchronous digital circuits, and effectively solve the problem of external diagnosis experienced in the production of digital circuits and its maintenance.

Key words: fault simulation, hardware acceleration of algorithms, test synthesis, evolutionary algorithms, mixed search strategy.

АННОТАЦИЯ

Борисевич А.В. Методы синтеза тестов для цифровых синхронных схем на основе реконфигурируемых аппаратных средств. - Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.05 - Компьютерные системы и компоненты. - Севастопольский национальный технический университет, Севастополь, 2008.

Современные системы автоматизированного управления, связи, обработки сигналов, представляют собой электронные схемы сверхбольшой сложности, тестирование и верификация которых является важнейшей задачей, решаемой на этапе выпуска готовой продукции и при ее эксплуатации, неотъемлемой частью которой является синтез проверяющих и диагностических тестов.

Поскольку размер пространства, внутри которого производится поиск тестовых последовательностей, растет экспоненциально от числа первичных входов и собственных состояний схемы, то проблема генерации тестов отнесена к классу NP-полных.

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

Решена задача эффективного использования аппаратного ускорения эволюционного поиска тестовых последовательностей. Получено соотношение для выбора между программной и аппаратной системами синтеза тестов с целью получения наименьшего времени решения.

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

На основе интервального представления сигналов предложен новый метод оценки длины тестовых последовательностей, который использует моделирование неисправной цифровой схемы средствами предложенной алгебры.

Рассмотрено решение задачи синтеза теста с помощью гибридного эволюционного алгоритма, использующего декомпозицию и символьный анализ схем, что позволяет сочетать преимущества детерминированных и генетических алгоритмов синтеза тестов.

Для решения задачи синтеза теста на основе декомпозиционного представления схемы разработано обобщение метода топологически-ориентированного принятия решений для функциональных элементов произвольной структуры, описанных системой булевых функций.

Для синтеза проверяющего теста схемы с памятью разработан смешанный иерархический генетико-символьный метод, который также использует декомпозицию схемы на подсхемы и предвычисление тестов для них. В методе задача построения теста всей схемы для заданной неисправности формулирована как задача максимизации скалярной функции в пространстве последовательностей входных наборов схемы, которая решается эволюционным алгоритмом. Предложена унимодальная целевая функция, которая определяется с помощью числовых оценок, вычисляемых от всех булевых функций, задающих условия генерации и транспортировки неисправности, конъюнкция которых является необходимым и достаточным условием построения теста.

Сформулирован и исследован новый эволюционный метод синтеза тестов с использованием средств аппаратного ускорения, в котором сочетаются программные алгоритмы анализа тестируемой схемы, генерации текстового описания аппаратных структур на языке описания аппаратуры, логический синтез и конфигурирование аппаратных средств. В результате осуещствлеятся автономное от ПЭВМ решение задачи синтеза теста для заданной неисправности на основе структурной декомпозиции схемы, эволюционного поиска тестовых последовательностей и аппаратного моделирования неисправностей.

На основе декомпозиционного подхода разработаны экономично реализуемые аппаратно целевые функции, для которых доказаны свойства инъективности и унимодальности.

Предложена математическая модель прмененного в методе эволюционного алгоритма как динамической системы. В результате анализа устойчивости дифференциального уравнения модели установлено, что алгоритм асимптотически сходится к оптимуму инъективной функции.

Разработаны асинхронный (комбинационный) и синхронный вычислитель целевой функции по разности состояния исправной и неисправной схем.

Рассмотрены оценки логической сложности для синхронной и асинхронной реализации вычислителя целевой функции. Показано, что с ростом размера подсхем, число логических элементов в асинхронной реализации растет как величина порядка логарифма от размера подсхем. Синхронный метод позволяет вычислять значение целевой функции за число тактов, равное числу подсхем, на которые декомпозирована схема и требует значительно меньших аппаратных ресурсов по сравнению с асинхронным комбинационным вычислением.

Разработана общая архитектура аппаратного средства решения задачи синтеза теста.

Проведена серия экспериментов по апробации предложенных методов на схемах библиотеки ISCAS-89. В результате чего доказана эффективность предложенных в работе методов по критериям времени построения теста и процента обнаруживаемых неисправностей по сравнению с чисто эволюционным методом.

Ключевые слова: моделирование неисправностей, аппаратное ускорение алгоритмов, синтез тестов, эволюционные алгоритмы, смешанные поисковые стратегии.

Размещено на Allbest.ru

...