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

ДЕРЖАВНИЙ ВИЩИЙ НАВЧАЛЬНИЙ ЗАКЛАД

“ДОНЕЦЬКИЙ НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ”

УДК 681.518:681.326.7

Автореферат

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

Побудова енергоефективних тестів та ідентифікуючих послідовностей цифрових схем на основі методу симуляції відпалювання

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

Зуауі Рамзі

Донецьк - 2011

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

Робота виконана в Державному вищому навчальному закладі «Донецький національний технічний університет» Міністерства освіти і науки, молоді та спорту України.

Науковий керівник: кандидат технічних наук, доцент Іванов Дмитро Євгенійович, доцент кафедри «Автоматизовані системи управління», ДВНЗ «Донецький національний технічний університет», Міністерство освіти і науки, молоді та спорту України.

Офіційні опоненти:

доктор технічних наук, професор Каргін Анатолій Олексійович, завідувач кафедри «Комп'ютерні технології», Донецький національний університет, Міністерство освіти і науки, молоді та спорту України;

доктор технічних наук, професор Кривуля Геннадій Федорович, завідувач кафедри «Автоматизація проектування обчислювальної техніки», Харківський національний університет радіоелектроніки, Міністерство освіти і науки, молоді та спорту України.

Захист відбудеться “16” червня 2011р. о 14:00 на засіданні спеціалізованої вченої ради Д11.052.03 Державного вищого навчального закладу «Донецький національний технічний університет» Міністерства освіти і науки, молоді та спорту України за адресою: 83001, м. Донецьк, вул. Артема, 58. ауд. 8.704.

З дисертацією можна ознайомитися в бібліотеці Донецького національного технічного університету за адресою: 83001, м. Донецьк, вул. Артема, 58, II навч. корп.

Автореферат розісланий “12” травня 2011р.

Вчений секретар спеціалізованої вченої ради Д11.052.03 кандидат технічних, доцент Г.В. Мокрий.

Загальна характеристика роботи

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

В даний час розроблено цілий ряд ефективних алгоритмів ідентифікації цифрових схем: генерації перевіряючих і діагностичних тестів, побудови ініціюючих послідовностей, тощо. Серед зарубіжних авторів найбільший внесок у розвиток проектування цифрових схем внесли I. Pomeranz, V.D. Agraval, Y. Zorian, P. Prinetto, M. Abramovici, серед вітчизняних вчених: Д.В. Сперанський, П.П. Пархоменко, Л.В. Дербунович, Р. Убар, Г.Ф. Кривуля, Ю.О. Скобцов. Однак триваюче зростання складності проектів змушує розробників шукати нові шляхи вирішення класичних завдань технічної діагностики. Це пов'язано з тим, що стосовно до сучасних проектів розроблені методи часто не дають практично прийнятного результату. Обмеження виражається в тому, що вони або не можуть закінчити обробку великого проекту (внаслідок переповнення стеків повернень процедур), або така обробка триватиме неприйнятно довго.

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

Зв'язок роботи з науковими програмами, планами, темами. Тема даної дисертаційної роботи, а також її результати пов'язані з виконанням НДР № 0110U000111 «Розробка наукових основ системного аналізу об'єктів комп'ютеризації та проектування інформаційних, управляючих систем» (Н-33-05) у рамках наукового напрямку кафедри автоматизованих систем управління Донецького національного технічного університету.

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

Для досягнення зазначеної мети роботи вирішуються такі задачі:

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

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

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

4. Розробка тришагового методу побудови енергоефективних вхідних тестів з мінімізованим розсіюванням тепла.

5. Програмна реалізація запропонованих алгоритмів побудови вхідних послідовностей та їх оптимізації.

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

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

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

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

Наукова новизна отриманих результатів полягає в наступному.

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

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

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

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

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

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

2. Для всіх запропонованих еволюційних алгоритмів на основі проведених машинних експериментів визначено раціональні значення евристичних констант.

3. Запропоновані методи та розроблене програмне забезпечення використовуються в Інституті прикладної математики і механіки НАН України у вигляді нового модуля «SA-Analyze» автоматизованої системи моделювання і діагностики АСМІД.

Особистий внесок здобувача. Всі основні наукові положення, що виносяться на захист, отримані автором самостійно. У роботах, які виконані в співавторстві, внесок здобувача полягає в наступному: [1-2, 6] - розроблено алгоритм симуляції відпалювання побудови ініціюючих послідовностей; [3, 8-9] - алгоритм симуляції відпалювання верифікації еквівалентності синхронних послідовністних схем; [5, 10-11] - розроблено дворівневий алгоритм побудови тестів з використанням стратегії симуляції відпалювання на нижньому рівні; [4, 12] - розроблені алгоритм надлишкової генерації тестів та алгоритм симуляції відпалювання вибору субоптимальної підмножини послідовностей.

Апробація роботи. Основні наукові результати роботи доповідалися і обговорювалися на:

- III і IV Всеукраїнській науково-практичній конференції «Сучасні тенденції розвитку інформаційних технологій в науці, освіті та економіці», Луганськ, 2009, 2010;

- III Міжнародній науково-практичній конференції молодих вчених, аспірантів, студентів «Сучасна інформаційна Україна: інформатика, економіка, філософія», Донецьк, 2009;

- X Міжнародній науково-технічній конференції «Штучний інтелект. Інтелектуальні системи», Дивноморське, Росія, 2009;

- Третій міжнародній науково-технічній конференції «Моделювання та комп'ютерна графіка», Донецьк, 2009;

- Другій міжнародній науково-практичній конференції «Інтелектуальні системи в промисловості та освіті (ІСПО)», Суми, 2009;

- Науково-практичній молодіжній школі-семінарі «Інформаційні інтелектуальні системи 2009», Харків, 2009;

- П'ятій міжнародній науково-технічній конференції «Гарантоздатні (надійні та безпечні) системи, сервіси та технології, DESSERT», Кіровоград, 2010;

- XII Науково-практичній міжнародній конференції «Інформаційні технології в освіті і управлінні », Нова Каховка, 2010.

Публікації. За темою дисертаційної роботи опубліковано 12 друкованих робіт, з яких 5 статей у наукових виданнях відповідно до вимог ВАК України, 9 у працях конференцій, у тому числі 1 - в електронному вигляді.

Структура та обсяг роботи. Дисертаційна робота має 169 сторінок основного тексту і складається з вступу, 4 розділів, висновків, в неї включено 12 малюнків, 12 таблиць, список використаних джерел з 139 найменувань, 2 додатки.

Основний зміст

У першому розділі «Аналіз методів моделювання та побудови вхідних ідентифікуючих послідовностей цифрових схем» вводяться поняття об'єкту дослідження: математичні моделі цифрової схеми (ЦС), алфавіти представлення сигналів, моделі несправностей. Розглянуто питання моделювання непошкоджених цифрових схем, алгоритми моделювання цифрових схем з пошкодженнями: конкурентний, дедуктивний, паралельний за розрядами машинного слова.

Розглянуто поняття різних типів ідентифікуючих послідовностей (ІП) ЦС: тестових, ініціюючих та верифікуючих еквівалентність. Виконано аналіз методів побудови IП: псевдовипадкові, структурні (D-алгоритм, PODEM), а також тих, що застосовують техніку символьних перетворень. Детально розглянуто генетичний алгоритм побудови тестів.

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

У кінці розділу виконано постановку завдань дослідження.

У другому розділі «Однорівневі алгоритми симуляції відпалювання побудови ідентифікуючих послідовностей» описано алгоритм симуляції відпалювання (СВ), досліджено можливість його застосування до задач побудови вхідних ІП шляхом порівняння з генетичним алгоритмом, а також розроблено однорівневі алгоритми СВ побудови таких послідовностей.

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

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

Мета алгоритму - пошук конфігурації з максимальною оцінкою:

(1)

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

Формально алгоритм СВ задається наступним чином:

(2)

де: - початкове рішення; зазвичай будується випадковим чином;

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

- довжина двійкового кодування рішень;

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

- , функція вартості потенційного рішення ;

- початкова температура;

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

Побудова алгоритму СВ для вирішення конкретної задачі означає завдання зазначених вище компонент.

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

(3)

Швидкість зменшення температури задається розподілом і вплива

є як на швидкість збіжності всього алгоритму, так і на його здатність долати локальні оптимуми.

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

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

- кодування особин в ГА відповідає кодуванню конфігурацій в алгоритмі СВ;

- операціям мутації в ГА відповідають операції збурення в алгоритмі СВ.

У задачах побудови вхідних ІП в залежності від складності алгоритму розв'язання виділяються дві різні моделі застосування алгоритмів СВ: одно- та дворівневі (рис.2).

Далі в розділі розробляються два алгоритми побудови вхідних ІП, які засновані на однорівневій моделі.

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

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

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

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

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

Друге визначення обране в якості основного, оскільки має дві переваги:

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

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

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

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

- додавання (видалення) рядка: у випадковому місці в конфігурації додається (видаляється) рядок.

Функція вартості для конфігурації-послідовності має наступний вигляд:

(4)

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

Алгоритм побудови ініціюючих послідовностей використовує однорівневі модель (рис.2.а). У вигляді псевдокоду його наведено нижче.

Алгоритм А1

Логічне Ініціювання(опис схеми, параметри)

{

K₀=ПобудоваНачальноїКонфігурації();

C_i=C(K_i); T_i=T_нач; // начальна температура

доки( T_i>T_кон )// цикл за температурою

{

для( int j=0 ; j<РозмірОточення ; j++ )

{

K_пром=ОбратиКонфігураціюЗОточення(K_i);

C_пром=C(K_пром);

якщо( ЦільДосягнуто(C_пром) )

{

рішення=K_пром; повернення;

}

C_i=C_пром-C_i;

якщо( C_i>0 ) K_i+1=K_пром;

інакше K_i+1=K_пром з ймовір. P(C_i)=exp(-C_i/kT_i);

}

T_i+1=ОбновитиТемпературу(T_i);

}

Рішення=K_i+1;

}

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

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

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

Визначення 4. Пара станів і автоматів і є такою, що вирівнює, якщо існує вхідна послідовність, яка переводить задані автомати в пару еквівалентних станів, тобто:

~(5)

де и функції переходів автоматів.

Визначення 5. Автомати і називаються послідовністно апаратно еквівалентними (ПАЕ) тоді і тільки тоді, коли існує вхідна послідовність , яка вирівнює довільну пару станів і . Послідовність у цьому випадку називається універсальною послідовністю, що вирівнює.

Визначення 6. Значення сигналу є таким, що покриває значення сигналу , якщо пара приймає наступні значення: , , , та .

Тобто пара не може приймати значення , , та .

Визначення 7. Автомат (схема) є тризначною незмінюючою заміною (ТНЗ) для автомата (схеми) тоді і тільки тоді, коли для довільної послідовності вихідні реакції покривають реакції .

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

Визначення 8. Схема є 3-значним еквівалентом (ТЕ) схеми тоді і тільки тоді, коли для будь-якої вхідної послідовності вихідні пари значень належать множині .

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

Властивості ТНЗ і ТЕ мають наступні переваги:

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

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

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

Тому для побудови алгоритму верифікації еквівалентності обрано властивості ТНЗ і ТЕ. Повна формальна перевірка властивості еквівалентності в сенсі визначення 7 (або 8) є дуже важким завданням. Тому воно переформулюється на протилежне: ми не будемо доводити еквівалентність заданих схем, а будемо будувати послідовність, яка буде намагатися розрізнити їх поведінку в сенсі визначення 7 (або 8). Більше того, таке переформулювання задачі дозволяє перейти від автоматного завдання об'єктів верифікації до структурного.

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

(6)

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

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

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

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

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

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

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

Пропонований підхід побудови енергоефективних тестів засновано на понятті надлишкового тестування. Структурна схема підходу наведена на рис.4 і складається з трьох етапів:

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

- оцінка параметра розсіювання тепла для кожної підпослідовності в тесті;

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

Етап 1 рішення завдання полягає в побудові вхідної послідовності (набору підпослідовностей) , яка володіє необхідною надлишковою повнотою при фіксованій надлишковості . Генерація надлишкових тестів на першому етапі заснована на понятті надлишковості.

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

Визначення 10. Надлишкова повнота послідовності при заданій надлишковості дорівнює:

(7)

де - число несправностей з множини , які перевіряються не менше разів заданою вхідною послідовністю.

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

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

=СВ_ПобудоваТеста(схема,,).

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

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

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

Етап 2 полягає в обчисленні оцінки розсіювання тепла для кожної підпослідовності . Для КМОП технології розсіювання тепла для заданої вхідної послідовності визначається виразом:

(8)

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

Етап 3 також базується на алгоритмі СВ і полягає у виборі підмножини послідовностей такій, що виконуються дві наступні умови:

- повнота тесту для вибраної підмножини послідовностей дорівнює повноті вихідної послідовності:

(9)

- параметр розсіювання тепла для вибраної підмножини мінімальний:

(10)

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

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

Побудова узагальненого критерію на основі (10) і (11) утруднено. Тому в алгоритмі виділяються дві фази роботи, в яких використовуються різні функції оцінки. У першій фазі з множини обираються такі підмножини, для кожної з яких виконана умова (10). Функція оцінки при цьому має вигляд:

(11)

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

(12)

де: ; - сума параметра розсіювання тепла для всіх підпослідовностей, які входять до .

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

Алгоритм А2

СО Вибір Підмножини(,,,параметри)

{

=ПобудуватиВипадковуПідмножину();

Фаза=1; ; ;

=ОцінитиКонфігурацію(,,,Фаза);

// цикл за температурою

while( !( ДосягнутоКритерійЗупинки() ) )

{

for( int i=0 ; i<КількістьІтерацій ; i++ )

{

=Збурення(,);

= ОцінитиКонфігурацію (,,,Фаза);

;

if( || )

=; // позитивна зміна вартості

}

// реалізуємо розклад температур

Обновити_T();

if( )

{

Фаза=2; ;

}

} // кінець while - цикл за температурою

return ;

} //кінець побудови підмножини

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

У розділі 4 «Програмна реалізація і апробація алгоритмів» представлені результати проведених машинних експериментів з програмною реалізацією запропонованих у дослідженні алгоритмів. Програмні модулі утворюють підсистему «SA-Analyze», яка входить до нової версії системи АСМІД. Дана система призначена для контролю та діагностики цифрових схем на всіх етапах «життєвого циклу»: проектуванні, виготовленні та експлуатації. Слід зазначити, що вперше в даній системі застосовані алгоритми, спрямовані на проектування енергоефективних пристроїв.

З програмною реалізацією кожного із запропонованих алгоритмів проводилися машинні експерименти на схемах з міжнародного каталогу ISCAS-89. Програмна реалізація складає орієнтовно від 1,5 тисяч строк коду (однорівневі алгоритми СВ побудови ІП та вибору субоптимальної множини) до 4 тисяч строк коду (дворівневий алгоритм СВ побудови надлишкових тестів).

Для перевірки ефективності алгоритму верифікації еквівалентності експерименти полягали в наступному: для заданої схеми будувалася схема з мінімальною зміною в комбінаційній частини (змінювався тип одного випадково обраного логічного вентиля), після чого алгоритм будував послідовність, що повинна розрізнити їх поведінку. За результатами серії експериментів (25 експериментів для кожної зі схем каталогу) алгоритм розрізнив поведінку в 96,71% випадків. Для порівняння наводяться дані по іншим відомим алгоритмам верифікації еквівалентності: генетичний алгоритм верифікації еквівалентності - 94,7%, алгоритм VEGA - 88,35%, алгоритм AQUILA - 65,00%. Результати для двох останніх згаданих алгоритмів наводяться тільки для схем невеликий розмірності через обмеження самих алгоритмів. Виграш становить від 2-6% у порівнянні з ГА до 30% у порівнянні зі структурними методами.

Алгоритм СВ побудови ІнП за параметром «число ініціалізованих тригерів» показує результати, які можна порівняти з генетичним алгоритмом. Це пояснюється тим, що знайдені в результаті пошуку рішення є найкращими відомими. За рахунок оптимізації алгоритму СВ шляхом введення адаптації ймовірностей збурюючих операцій за фазами роботи у восьми з 15 додаткових експериментів вдалося істотно зменшити довжину ініціюючих послідовностей: у середньому в 3.19 рази.

Для стратегії побудови енергоефективних тестів для кожної зі схем послідовно виконувалися алгоритми етапів 1-3 (розділ 4). Результати експериментів наведені в табл.1. Стовпець «повнота теста» показує надлишкову повноту тесту для . Стовпець «зменшення розсіювання тепла» показує зменшення параметра у фазі 2 алгоритму щодо першої знайденої підмножини , для якої виконано умову (13). У середньому досягнуто зменшення розсіювання тепла на 86,34%. Стовпець «довжина послідовності» показує початкову та кінцеву довжину тестової послідовності, а також фактор її зменшення. У середньому довжину послідовності вдалося зменшити в 12,89 разів. Такі чисельні значення показують дуже високу ефективність запропонованого підходу.

Таблиця 1 Чисельні результати експериментів побудови енергоефективних тестів.

схема	повнота тесту, %	зменшення розсіювання тепла, %	довжина послідовності	час роботи, час:мін:сек.
			початкова	досягнута	зменшення, раз	загальне (фази 1-3)	фаза 3 СВ, сек.
s298	85.71	92.02	1467	149	9.85	0:21	1
s344	96.19	92.97	3621	288	12.57	1:01	1
s349	95.42	91.73	1960	162	12.10	0:27	1
s382	89.47	91.02	8661	855	10.13	3:36	1
s386	73.95	90.77	17826	1699	10.49	5:34	1
s400	88.21	93.08	16617	1448	11.48	10:43	<1
s444	79.32	88.72	3676	434	8.47	3:00	1
s641	44.75	88.91	57372	7134	8.04	1:28:28	3
s713	81.93	91.56	11841	1219	9.71	3:35	1
s832	48.05	89.74	3135	338	9.28	2:01	4
s1196	91.22	84.19	16117	2725	5.91	1:15	23
s1238	77.86	76.33	7025	1798	3.91	0:55	6
s1269	17.87	87.77	647	78	8.29	2:55	1
s1423	73.47	81.89	76075	14557	5.23	2:01:21	5
s1488	92.19	83.25	16968	3128	5.42	6:28	20
s1494	95.22	89.55	10966	1274	8.61	3:40	9
s1512	4.86	84.75	130	20	6.50	3:13	1
s2081	8.29	93.28	480	32	15	12:03	<1
s3271	96.57	89.60	11422	1541	7.41	2:25	64
s3330	66.45	88.29	5345	1357	3.94	16:09	5
в середньому:	86.34			12.89

Додатково досліджувалися властивості алгоритму СВ побудови тестів без надлишковості. Для всіх контрольних схем алгоритм СВ побудував тести з повнотою на 3-4% вище, ніж генетичний алгоритм, однак довжина тестів була вищою.

Висновки

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

Основними результати, які отримані у дослідженні, є:

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

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

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

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

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

6. На основі проведених експериментів для всіх запропонованих еволюційних алгоритмів визначено раціональні значення евристичних параметрів: розклад температури, константа Больцмана, тощо.

7. Проведено апробацію реалізованих алгоритмів на схемах з міжнародного каталогу ISCAS-89, яка свідчить про поліпшення якісних характеристик ідентифікуючих послідовностей від 3 до 30% залежно від типу розв'язуваної задачі, при цьому розсіювання тепла при їх застосуванні зменшується в середньому на 86%.

8. Програмні модулі, що розроблені, впроваджено у якості підсистеми «SA-Analyze» в нову версію автоматизованої системи моделювання і діагностики АСМІД, яка призначена для використання на всіх етапах життєвого циклу цифрових схем: проектуванні, оптимізації, виробництві та обслуговуванні.

Список опублікованих праць за темою дисертації

1. Иванов Д.Е. Применение стратегии симуляции отжига для задачи построения инициализирующих последовательностей цифровых схем / Д.Е. Иванов, Р. Зуауи // «Вісник східноукраїнського національного університету ім.В.Даля».- 2009.- №1(131), частина 2.- С.161-168.

2. Иванов Д.Е. Алгоритм построения инициализирующих последовательностей цифровых схем, основанный на стратегии симуляции отжига / Д.Е. Иванов, Р. Зуауи // Искусственный интеллект.- 2009.- №4.- С.415-424.

3. Иванов Д.Е. Верификация эквивалентности цифровых схем с использованием стратегии симуляции отжига / Д.Е. Иванов, Р. Зуауи // «Науковий вісник Чернівецького університету. Випуск №479. Комп'ютерні системи та компоненті».- 2009.- С.33-41.

4. Иванов Д.Е. Алгоритм симуляции отжига оптимизации рассеивания тепла диагностических тестов / Д.Е. Иванов, Р. Зуауи // «Радіоелектронні і комп'ютерні системи».- 2010.- №7(48).- С.170-175.

5. Иванов Д.Е. Алгоритм симуляции отжига построения тестов цифровых устройств / Д.Е. Иванов, Р. Зуауи // Вестник Херсонского национального технического университета.- 2010.- №2(38).- С.416-422.

6. Иванов Д.Е. Стратегия симуляции отжига построения инициализирующих последовательностей цифровых схем / Д.Е. Иванов, Р. Зуауи // Матеріали III Всеукраїнської науково-практичної конференції “Сучасні тенденції розвитку інформаційних технологій в науці, освіті та економіці”, 9-11 квітня 2009.- Луганськ:ЛНУ ім. Т.Г. Шевченка, 2009.- С.272-274.

7. Зуауи Р. Сравнение эволюционных поисковых стратегий: генетические алгоритмы и симуляция отжига / Рамзи Зуауи // Праці ІІІ-ї Міжнародної науково-практичної конференції молодих учених, аспірантів, студентів “Сучасна інформаційна Україна: інформатика, економіка, філософія”.- Донецьк, 2009.- Т.1.- С.242-246.

8. Иванов Д.Е. Применение стратегии симуляции отжига для верификации эквивалентности последовательностных схем / Д.Е. Иванов, Р. Зуауи // Х Международная научно-техническая конференция «Искусственный интеллект. Интеллектуальные системы» (ИИ-2009), 28 сентября-3октября 2009, Дивноморское, Россия.- Таганрог: Изд-во ТТИ ЮФУ, 2009.- С.30-32.

9. Иванов Д.Е. Построение идентифицирующих последовательностей цифровых схем с использованием стратегии симуляции отжига / Д.Е. Иванов, Р. Зуауи // Труды Третьей международной научно-технической конференции "Моделирование и компьютерная графика".- Донецк, 7-9 октября 2009г. (в электронном виде).

10. Иванов Д.Е. Возможность применения стратегии симуляции отжига в диагностике цифровых схем / Д.Е. Иванов, Р. Зуауи // Тези доповідей Другої міжнародної науково-практичної конференції «Інтелектуальні системи в промисловості і освіті (ІСПО) - 2009».- Суми:Видавництво Сумського державного університету, 2009.- С.72-74.

11. Зуауи Р. Двухуровневый алгоритм генерации тестов, основанный на стратегии симуляции отжига / Р. Зуауи // Друга науково-практична молодіжна школа-семінар «Інформаційні інтелектуальні системи 2009», ХНУРЕ, 2-4 грудня 2009.- Харків:ХНУРЕ, 2009.- С.175-176.

12. Иванов Д.Е. Оптимизация входных диагностических последовательностей с помощью алгоритма симуляции отжига / Д.Е. Иванов, Р. Зуауи // Матеріали IV Всеукраїнської науково-практичної конференції “Сучасні тенденції розвитку інформаційних технологій в науці, освіті та економіці”, 15-17 квітня 2010.- Луганськ:ЛНУ ім. Т.Г. Шевченка, 2010.- С.44-46.

Анотація

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

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

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

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

Розроблено алгоритмічне та програмне забезпечення для вирішення вказаних задач. Проведено його апробацію на схемах з міжнародного каталогу ISCAS-89, яка свідчить про поліпшення якісних характеристик побудованих послідовностей від 3 до 30% в залежності від типу розв'язуваної задачі, розсіювання тепла при їх прикладанні зменшується в середньому на 86%.

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

Аннотация

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

Диссертация на соискание учёной степени кандидата технических наук по специальности - 05.13.05 - Компьютерные системы и компоненты,- Государственное высшее учебное заведение «Донецкий национальный технический университет», Донецк, 2011.

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

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

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

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

Разработана трёхшаговая стратегия построения энергоэффективных тестов, которая основана на избыточном тестировании.

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

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

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

Разработано алгоритмическое и программное обеспечение для решения указанных выше задач, которое позволяет строить последовательности заданных классов с высокими качественными характеристиками. Проведена апробация реализованных алгоритмов на схемах из международного каталога ISCAS-89, которая показывает увеличение качественных характеристик построенных последовательностей от 3 до 30% в зависимости от типа решаемой задачи, при этом рассеивание тепла при их приложении уменьшается в среднем на 86%.

Разработанное программное обеспечение применяется в качестве подсистемы «SA-Analyze» в новой версии автоматизированной системы АСМИД, которая разрабатывается в Институте прикладной математики и механики НАН Украины.

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

Annotation

Zouaoui Ramzi. Construction of the energy-efficient tests and identifying sequences of digital circuits based on the simulated annealing method. - Manuscript.

Thesis on competition of a scientific degree of candidate of technical science on speciality 05.13.05 - Computer Systems and Components.- Donetsk National Technical University, Donetsk, 2011.

Dissertation is devoted to solution of the actual scientific and technical problems - to improve the quailty of the automated diagnosis of digital circuits by developing new evolutionary algorithms for constructing of the identifying sequences that are based on the simulated annealing strategy.

Basing on the comparative analysis with genetic algorithms it is proposed to use the simulated annealing strategy for solving the tasks of the dissertation. On its basis the one-level algorithms for constructing of initializing and equivalence verification sequences are proposed. A three steps strategy of building of the energy efficiency tests basing on redundant testing are proposed. Phases of redundant test generation and selection of the suboptymal set of sequences are implemented on the simulating annealing algorithm.

The algorithms and software are developed to solve the mentioned above problems. Approbation on the circuits from international catalog ISCAS-89 shows the increase of quality of constructed sequences from 3 to 30% depending on the type of problem, and the heat dissipation during their application is reduced on average by 86%.

Keywords: digital device, identifying sequence, evolution methods, simulated annealing algorithm, redundant testing, energy efficiency tests.

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

...