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

Автореферат дисертації на здобуття наукового ступеня кандидата технічних наук Побудова енергоефективних тестів та ідентифікуючих послідовностей цифрових схем на основі методу симуляції відпалюванняРобота виконана в Державному вищому навчальному закладі «Донецький національний технічний університет» Міністерства освіти і науки, молоді та спорту України. Науковий керівник: кандидат технічних наук, доцент Іванов Дмитро Євгенійович, доцент кафедри «Автоматизовані системи управління», ДВНЗ «Донецький національний технічний університет», Міністерство освіти і науки, молоді та спорту України. Захист відбудеться “16” червня 2011р. о 14:00 на засіданні спеціалізованої вченої ради Д11.052.03 Державного вищого навчального закладу «Донецький національний технічний університет» Міністерства освіти і науки, молоді та спорту України за адресою: 83001, м.В даний час розроблено цілий ряд ефективних алгоритмів ідентифікації цифрових схем: генерації перевіряючих і діагностичних тестів, побудови ініціюючих послідовностей, тощо. Однак триваюче зростання складності проектів змушує розробників шукати нові шляхи вирішення класичних завдань технічної діагностики. У даній роботі розглядаються алгоритми побудови ідентифікуючих послідовностей, які засновані на стратегії симуляції відпалювання. Модифіковано тришагову стратегію побудови енергоефективних тестів, в якій етапи генерації надлишкових тестів і вибору субоптимальної підмножини послідовностей реалізовано на алгоритмі симуляції відпалювання, що дозволило істотно зменшити параметр розсіювання тепла побудованого тесту. У роботах, які виконані в співавторстві, внесок здобувача полягає в наступному: [1-2, 6] - розроблено алгоритм симуляції відпалювання побудови ініціюючих послідовностей; [3, 8-9] - алгоритм симуляції відпалювання верифікації еквівалентності синхронних послідовністних схем; [5, 10-11] - розроблено дворівневий алгоритм побудови тестів з використанням стратегії симуляції відпалювання на нижньому рівні; [4, 12] - розроблені алгоритм надлишкової генерації тестів та алгоритм симуляції відпалювання вибору субоптимальної підмножини послідовностей.У першому розділі «Аналіз методів моделювання та побудови вхідних ідентифікуючих послідовностей цифрових схем» вводяться поняття обєкту дослідження: математичні моделі цифрової схеми (ЦС), алфавіти представлення сигналів, моделі несправностей. Виконано аналіз методів побудови ІП: псевдовипадкові, структурні (D-алгоритм, PODEM), а також тих, що застосовують техніку символьних перетворень. У другому розділі «Однорівневі алгоритми симуляції відпалювання побудови ідентифікуючих послідовностей» описано алгоритм симуляції відпалювання (СВ), досліджено можливість його застосування до задач побудови вхідних ІП шляхом порівняння з генетичним алгоритмом, а також розроблено однорівневі алгоритми СВ побудови таких послідовностей. Видно, що в структурі алгоритму СВ присутня велика кількість евристик, від значень яких істотно залежить ефективність адаптації алгоритму до конкретного завдання: початкова і кінцева температури, швидкість зміни температур, розподіл ймовірностей прийняття негативних змін, спосіб побудови кодування конфігурацій і обчислення їх оцінок. Може бути показано що, якщо схема є тризначною незмінюючою заміною для , тоді що послідовність, що є ініціюючою для схеми , також є ініціюючою для схеми .У дисертаційній роботі запропоновано нове рішення актуальної наукової задачі, що має важливе значення в життєвому циклі проектування цифрових схем. Розроблено нові еволюційні алгоритми побудови ідентифікуючих послідовностей та їх оптимізації, які засновані на новій стратегії симуляції відпалювання і дозволяють підвищити якісні характеристики послідовностей, що будуються. Отримав подальший розвиток еволюційний підхід ідентифікації цифрових схем за рахунок застосування нової оптимізаційної стратегії симуляції відпалювання, що дозволило підвищити ефективність автоматизованого діагностування великих послідовністних схем. Розроблено дворівневий алгоритм побудови вхідних тестів для синхронних послідовністних схем, в якому на нижньому рівні пошуку тесту для однієї несправності запропоновано використовувати алгоритм симуляції відпалювання, що дозволило підвищити повноту побудованих тестів.

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

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

Основними результати, які отримані у дослідженні, є: 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.