Міністерство освіти і науки України

Національний аерокосмічний університет ім. М.Є. Жуковського
“Харківський авіаційний інститут”

ЯКИМЕЦЬ Наталія Володимирівна

УДК 681.5.09

МЕТОДИ ТА ПРОГРАМНО-ТЕХНІЧНІ ЗАСОБИ СТВОРЕННЯ ВІДМОВОСТІЙКИХ ЦИФРОВИХ СИСТЕМ УПРАВЛІННЯ З ПРОГРАМОВАНОЮ ЛОГІКОЮ З ВИКОРИСТАННЯМ ГЕНЕТИЧНИХ АЛГОРИТМІВ

05.13.03 – системи і процеси керування

АВТОРЕФЕРАТ
дисертації на здобуття наукового ступеня
кандидата технічних наук

Харків – 2008

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

Роботу виконано у Національному аерокосмічному університеті ім. М.Є. Жуковського "Харківський авіаційний інститут" Міністерства освіти і науки України.

Науковий керівник: | доктор технічних наук, професор
Харченко Вячеслав Сергійович,

Національний аерокосмічний університет

ім. М.Є. Жуковського "Харківський авіаційний інститут",
завідуючий кафедрою комп’ютерних систем і мереж,
заслужений винахідник України.

Офіційні опоненти: – | доктор технічних наук, професор

Краснобаєв Віктор Анатолійович,

Харківський національний технічний університет сільського господарства ім. Петра Василенка, професор кафедри автоматизації та комп’ютерних технологій, заслужений винахідник України;

– | кандидат технічних наук

Лук’янович Олександр Євгенович,

Науково-виробниче підприємство “Хартрон-Аркос”,
провідний науковий співробітник.

Захист відбудеться “_11_” _квітня_ 2008 р. о _12_ годині на засіданні спеціалізованої вченої ради Д64.062.01 у Національному аерокосмічному університеті ім. М.Є. Жуковського "Харківський авіаційний інститут" за адресою: 61070, м. Харків, вул. Чкалова, 17, радіотехнічний корпус, ауд. 232.

З дисертацією можна ознайомитись у науково-технічній бібліотеці Національного аерокосмічного університету ім. М.Є. Жуковського "Харківський авіаційний інститут".

Автореферат розісланий “_7_” _березня_ 2008 р.

Вчений секретар

спеціалізованої вченої ради М.О. Латкін

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

Актуальність теми дослідження. Сучасний досвід проектування й експлуатації систем керування аерокосмічного застосування обумовлює жорсткі вимоги до адаптивності, масштабованості й відкритості архітектури наступного покоління таких систем. Технологічним підходом до побудови систем керування з архітектурою, що задовольняє цим вимогам, є концепція “система на кристалі” (System On a Chip, SoС), яка передбачає інтеграцію в одному кристалі якомога більшої кількості елементів. Використання технології SoС дозволяє збільшити швидкодію системи керування, забезпечити її гнучкість (можливість “гарячого” переконфігурування), скоротити час розробки й модернізації. Елементною базою для створення “систем на кристалі” являються мікросхеми програмованої логіки, оскільки вони досить ресурсоємні, мають велику обчислювальну потужність і здатну до реконфігурації архітектуру.

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

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

Значний внесок у розвиток теорії й практики створення відмовостійких автоматів і систем керування внесли багато вчених: A. Авіженіс, Т. Андерсон, Ж.К. Лапрі, А.І. Кривоносов, А.С. Кулік, О.М. Романкевич, В.В. Сапожников, Е.С. Согомонян, М.С. Щербаков, Б.М. Наумов та ін. Розробку теорії багатоверсійних систем і технологій для створення гарантоздатних (надійних і безпечних) рішень для критичних застосувань здійснено Харченком В.С. та його учнями. Проблеми розробки цифрових систем у рамках некласичного підходу до їхнього створення досліджені в працях таких учених, як А. Томпсон, Дж. Коза, Г.К. Вороновський, та ін. Аналіз робіт в галузі створення відмовостійких багатоверсійних цифрових систем керування показує, що:

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

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

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

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

Зв’язок роботи з науковими програмами, планами, темами. Дослідження, результати яких наведено в дисертації, проводились у відповідності з державними планами НДР, програмами і договорами, що були виконані на кафедрі комп’ютерних систем і мереж Національного аерокосмічного університету ім. М.Є. Жуковського та інших організаціях:

- “Теоретичні основи, методи та інструментальні засоби аналізу, розробки та верифікації гарантоздатних інформаційно-управляючих систем для аерокосмічних об’єктів і комплексів критичного застосування” (Національний аерокосмічний університет ім. М.Є. Жуковського “ХАІ”, ДР № 0106U001071, 2006);

- “Розробка науково-теоретичних основ та інформаційних технологій оцінки та забезпечення відмовостійкості та безпеки комп’ютеризованих систем аерокосмічних комплексів, а також інших комплексів критичного застосування” (Національний аерокосмічний університет ім. М.Є. Жуковського “ХАІ”, ДР № 104U003502, 2003-2005);

- “Розробка методів та інформаційних технологій оцінки, підтримки верифікації та проектування ІУС, важливих для безпеки АЕС” (Національний аерокосмічний університет ім. М.Є. Жуковського “ХАІ”, ДР № 0103U004093, 2005-2006).

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

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

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

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

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

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

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

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

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

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

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

Наукова новизна одержаних результатів.

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

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

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

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

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

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

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

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

Результати досліджень впроваджені в:

- НТ СКБ “Полісвіт” при проектуванні бортових обчислювальних систем управління літака АН-140, зокрема, регулятора температури системи протиобмерзання (акт впровадження від 04.10.2007);

- ЗАТ “Радій” при виконанні НДР “Розробка методів та інформаційних технологій оцінки, підтримки верифікації й проектування ІУС, важливих для безпеки АЕС”, та розробці варіантів цифрових систем керування для АЕС (акт впровадження від 02.09.2007);

- навчальному процесі Національного аерокосмічного університету ім. М.Є. Жуковського “ХАІ” (акт впровадження від 21.02.2007).

Обґрунтованість і достовірність наукових положень, висновків і рекомендацій дисертаційної роботи підтверджується:

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

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

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

Апробація результатів дисертації. Основні наукові положення, ідеї та висновки дисертаційної роботи доповідались й обговорювались на науково-технічному семінарі “Критичні комп’ютерні технології та системи” кафедри комп’ютерних систем та мереж Національного аерокосмічного університету ім. М.Є. Жуковського “ХАІ”. Наукові результати роботи доповідались також на міжнародній науково-практичній ювілейній конференції “Проблеми енергозабезпечення та енергозбереження в АПК України” (м. Харків, 2003 р.); IEEE East-West Design and Test Workshop (EWDTW’05) (м. Одеса, 2005 р.); науково-технічній конференції “Проблемы информатики и моделирования” (м. Харків, 2005 р.); міжнародних науково-технічних конференціях “Dependable Systems, Services and Technologies” (м. Полтава, 2006 р.; м. Кіровоград 2007 р.); IEEE East-West Design and Test Workshop (EWDTW’06) (м. Сочі, Росія, 2006 р.); International Research Training Groups Workshop in Computer Science (Dagstuhl, Germany, 2006); міжнародній науково-практичній конференції “Комп’ютерні системи в автоматизації робочих процесів” (м. Хмельницький, 2007 р.); The Second International Workshop on Engineering Fault Tolerant Systems (Дубровнік, Хорватія, 2007); IEEE East-West Design and Test International Symposium (Єреван, Арменія, 2007).

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

Структура та обсяг дисертації. Дисертація має вступ, чотири розділи, висновки й додатки. Повний обсяг дисертації складає 189 сторінку, у тому числі: 81 рисунок, з яких 2 на окремій сторінці, 26 таблиць, з яких 1 на окремій сторінці, список з 134 використаних літературних джерел на 14 сторінках, 4 додатки на 26 сторінках.

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

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

У першому розділі проведено аналіз предметної області дослідження, а саме: розглянуто вимоги до аерокосмічних бортових систем керування і технології реалізації таких систем; розглянуто математичний апарат, що використовується в рамках класичного й некласичного підходів до створення цифрових систем керування з програмованою логікою (ЦСКПЛ), а також обґрунтовано вибір показників для оцінки їх надійності. За результатами проведеного аналізу зроблено такі висновки: 1) сучасні ЦСКПЛ доцільно будувати як “системи-на-кристалі” (SoС), оскільки такий підхід найбільш розвинутий і підтриманий як архітектурою SoС, яка для систем керування може об’єднувати всі цифрові та цифроаналогові засоби датчиків і виконуючих пристроїв, так і засобами проектування; 2) основні причини втрати працездатності ЦСКПЛ аерокосмічного застосування пов’язані з відмовами елементної бази внаслідок фізичних дефектів, наявністю та проявом дефектів проектування, неповною відповідністю умов експлуатації вимогам технічного завдання, впливом навколишнього середовища; 3) можливим методом для зменшення кількості та забезпечення стійкості до проектних дефектів є багатоверсійне проектування, при цьому диверсифікація проектів ЦСКПЛ може здійснюватися як у рамках класичного проектування за допомогою стандартного інструментарію САПР, так і некласичного, коли для створення ЦСКПЛ використовуються еволюційні методи моделювання, зокрема, генетичні алгоритми (ГА); 4) для вирішення задач багатоверсійного проектування ЦСКПЛ необхідно забезпечити методичну та інструментальну підтримку процесу розробки диверсних рішень. В кінці розділу формується загальна наукова задача досліджень, яка розбивається на ряд часткових взаємопов'язаних задач, а також обґрунтовується методика їх проведення.

Основні результати розділу опубліковані в роботах [2, 3].

У другому розділі розглядається концепція ресурсно-орієнтованої диверсифікації проектів ЦСКПЛ і описується методика розробки відмовостійких ЦСКПЛ на основі частково працездатних (частково визначених і частково коректних) автоматів (ЧПА) засобами ГА (рис. 1). Для формування множини ресурсів проектування пропонується використовувати різні концептуальні підходи до створення ЦСКПЛ, оскільки отримані в такий спосіб версії будуть в незначній мірі корелювати між собою. У рамках дисертаційного дослідження було обрано математичний апарат ГА як альтернативу класичному САПР-орієнтованому підходу.

Аналіз особливостей синтезу ЦСКПЛ за допомогою класичного (САПР) і некласичного (ГА) підходу показує, що проекти таких систем можуть порівнюватися на логічному і на фізичному рівнях. На логічному рівні ЦСКПЛ може бути представлена у вигляді орієнтованого графа , який утворюють N зайнятих у проекті логічних комірок ПЛІС і множина зв'язків L, які утворює множина логічних комірок. В якості метрики диверсності на логічному рівні пропонується ступінь різниці в розміщенні вершин графів з множинами вершин двох версій N1 і N2: , де /N1/, /N2/, /N1 N2/ - потужності відповідних множин. На фізичному рівні

Рис. 1. Створення ЦСКПЛ на основі ЧПА | проект ЦСКПЛ може бути представлений у вигляді просторової конфігурації, яку утворює /N/ зайнятих логічних комірок ПЛІС. Множині логічних комірок відповідає множина , де si – координати і–ї комірки. В якості метрики диверсності на фізичному рівні пропонується ступінь різниці в топології логічних комірок проектів ЦСКПЛ на ПЛІС: , де /S1/, /S2/, /S1 S2/ - потужності відповідних множин.

На сьогоднішній день сучасний інструментарій дозволяє перетворити розробку ЦСКПЛ у цілком автоматизований процес. У рамках некласичного проектування ЦСКПЛ можна виділити два аспекти.

По-перше, досить часто апарат ГА нездатний реалізувати синтез

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

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

Повністю коректним автоматом (ПКА) називається автомат, у якого кожному вхідному вектору хi з множини всіх вхідних векторів Х для довільного моменту часу tiT відповідає коректний (згідно специфікації) вихідний стан yi з множини коректних вихідних станів Yc, тобто tiT, xi X: xi yi, yi Yc, Yc = Y, де хi – поточний вхідний вектор автомата; X – множина всіх вхідних векторів автомата; yi – вихідний стан автомата, що відповідає хi; Yc – множина коректних вихідних станів автомата; Y – загальна множина вихідних станів автомата.

Автомат називається частково коректним (ЧКА), якщо існує хоча б один момент часу tiT, впродовж якого існує хоча б один вхідний вектор хi з множини всіх вхідних векторів Х, якому не відповідає коректний вихідний стан yi з множини коректних вихідних станів Yc, тобто tiT, xi X: xi yi, yi Yс, Yc Y (рис. 2).

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

Рис. 2. ПКА, побудований на основі ЧКА при фіксованому часі

Рис. 3. ПВА, побудований на основі ЧВА при фіксованому часі

Повністю визначеним автоматом (ПВА) є автомат, у якого кожному вхідному вектору хi із множини всіх вхідних векторів Х для довільного моменту часу tiT відповідає вихідний стан yi такий, що інформація щодо його коректності (належить або не належить множині Yc) відома заздалегідь, тобто tiT, xi X: xi yi, yi Yd, Yd = Y, де Yd – множина визначених (специфікованих) вихідних станів автомата.

Автомат називається частково визначеним (ЧВА), якщо існує хоча б один момент часу tiT, впродовж якого існує хоча б один вхідний вектор хi з множини всіх вхідних векторів Х, якому відповідає вихідний стан yi такий, що інформація щодо його коректності (належить або не належить множині Yc) не відома заздалегідь, тобто tiT, xi X: xi yi, yi Yd, Yd Y (рис. 3).

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

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

Основним фактором при оцінці надійності таких систем є вибір елементарного об'єкта для подальшої побудови структурної схеми надійності ЦСКПЛ.

1. Якщо елементарними об'єктами ЦСКПЛ являються автомати (рис. 4), то розрахунок надійності такої системи виконується, виходячи із припущення, що відмова кожного ЧПА абсолютна (не залежно від того, на якій частині вихідних сигналів він формує неправильний результат) і призводить до повної втрати його працездатності. Тому залежно від сформованої множини ЧПА, які реалізують повну функціональність системи, формується структурна схема її надійності, згідно з якою обчислюється з використанням формул для постійного резервування.

2. Якщо елементарними об'єктами ЦСКПЛ являються групи визначених і коректних вихідних даних автоматів (рис. 5), то розрахунок надійності такої системи виконується, виходячи із припущення, що відмова ЧПА не призводить до повної втрати працездатності автомата, і ЧРА може мати вірні вихідні дані на деяких наборах вхідних даних. Тому ЦСКПЛ обчислюється таким чином:

, де pij(t) – імовірність безвідмовної роботи j-го

автомату на i-й групі визначених і коректних вихідних даних; рк(t) – імовірність безвідмовної роботи засобів контролю ЦСКПЛ; n – кількість груп визначених і коректних вихідних даних ЦСКПЛ; m - кількість автоматів, що мають визначені й коректні вихідні дані на i-й групі.

Рис. 4. Структурна схема надійності ЦСКПЛ на ЧПА, де елементарні об'єкти – автомати

Рис.5. Розбивка множини вихідних даних ЧПА

Рис. 6. Структурно-логічна схема надійності ЦСКПЛ на ЧПА, якщо елементарні об'єкти - автомати й групи визначених і коректних вихідних даних

3. Якщо елементарними об'єктами ЦСКПЛ є автомати й групи визначених і коректних вихідних даних (рис. 6), то розрахунок надійності такої системи виконується, виходячи із припущення, що відмова ЧПА з певною ймовірністю може спричинити повну або часткову втрату працездатності автомата. Тому

ЦСКПЛ обчислюється як =, де

Р'(t) - імовірність безвідмовної роботи тих частин автоматів ЦСКПЛ, відмова яких приводить до відмови відповідного автомата вцілому; Р'(t) обчислюється за принципом, коли елементарними об'єктами ЦСКПЛ є автомати, однак, у розрахункових формулах використовується - імовірність безвідмовної роботи частини j-го автомата ЦСКПЛ, відмова якої призводить до повної відмови автомата; Р''(t) - імовірність безвідмовної роботи тих частин автоматів ЦСКПЛ, відмова яких призводить до відмови відповідного автомата на відповідних групах визначених і коректних даних; – імовірність безвідмовної роботи j-го автомата на i-й групі визначених і коректних вихідних даних за умови безвідмовної роботи частини j-го автомата, відмова якої призводить до повної відмови j-го автомата.

Для підвищення відмовостійкості ЦСКПЛ, розроблених за допомогою ГА, запропоновано два методи.

1. Метод константи. Сутність методу: виходячи з необхідного (заданого) рівня відмовостійкості системи, вибирається мінімальна кількість елементарних об'єктів n для всіх груп вихідних даних; для формування однієї версії автомати підбираються таким чином, щоб у кожній групі кількість надлишкових елементів mi задовольняла умові n ? mi.

2. Удосконалений метод оптимального резервування ЦСКПЛ, створених на ЧПА. Даний метод базується на алгоритмі найскорішого спуску. Він враховує особливості логіки роботи ЧПА, синтезованих засобами ГА, і дозволяє оптимізувати структуру таких систем за критеріями надійності та компактності. Цей метод доцільно використовувати у випадку, якщо потрібно отримати ЦСКПЛ, що займає мінімально можливу кількість логічних комірок ПЛІС при заданому рівні надійності або має максимально можливий рівень надійності при заданій кількості логічних комірок.

Основні результати розділу опубліковані в роботах [2, 3, 7 - 10].

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

, де i – номер версії в популяції; Xr – кількість вхідних

векторів, яким відповідають вірні вихідні вектори; n – розрядність вхідних даних.

Проведено порівняльний аналіз версій ЦСКПЛ, отриманих засобами САПР і ГА, а також версій ЦСКПЛ, створених на основі ЧПА різного типу, з огляду на вимоги до складності та часові обмеження на розробку системи (табл. 1). В якості прототипу було обрано блок порівняння терморегулятора для регулювання температури в салоні літака АН-70. Версії порівнювалися на логічному рівні. Оцінка стійкості до відмов ЦСКПЛ на ЧПА наддала можливість максимальний (без урахування додаткових засобів реконфігування) відносний виграш у зменшенні ймовірності відмови в 6 – 21 раз у порівнянні з прототипом залежно від обраної моделі оцінки відмовостійкості системи (табл. 2).

Таблиця 1

Імовірність безвідмовної роботи терморегулятора АН-70 і прототипу при 1/год, , NПЛІС=256 логічних комірок

- | Елементарний об’єкт | Час, години

- | - | 10 | 102 | 103 | 104 | 105

Модель на ЧВА і ЧКА | Автомати | 0,999999953 | 0,999999531 | 0,999995313 | 0,999953126 | 0,99953136

Групи вихідних даних | 0,999999977 | 0,999999766 | 0,999997656 | 0,999976563 | 0,999765652

Модель на ПВА і ЧКА | Автомати | 0,999999965 | 0,999999648 | 0,999996484 | 0,999964844 | 0,999648499

Групи вихідних даних | 0,999999987 | 0,999999868 | 0,999998682 | 0,999986817 | 0,999868171

Прототип | - | 0,999999711 | 0,999997109 | 0,999971094 | 0,999710979 | 0,997113549

Таблиця 2

Відносний виграш у зменшенні ймовірності відмови моделей терморегулятора АН-70 і прототипу при 1/год, , NПЛІС=256 логічних комірок

- | Елементарний об’єкт | Час, години

- | - | 10 | 102 | 103 | 104 | 105

Порівняння моделі на ПВА і ЧКА та моделі на ЧВА і ЧКА | Автомати | 1,339285682 | 1,331675824 | 1,333188002 | 1,333311565 | 1,333254113

Групи вихідних даних | 1,777722976 | 1,777776727 | 1,7777762 | 1,777765541 | 1,777660699

Порівняння моделі на ЧВА і ЧКА з прототипом | Автомати | 6,166665922 | 6,166659199 | 6,166591993 | 6,165919988 | 6,159205826

Групи вихідних даних | 12,3333317 | 12,33331695 | 12,33316953 | 12,33169546 | 12,31696826

Порівняння моделі на ПВА і ЧКА з прототипом | Автомати | 8,258927375 | 8,211990971 | 8,221226456 | 8,22109243 | 8,211786499

Групи вихідних даних | 21,92524713 | 21,92588384 | 21,92561527 | 21,92286326 | 21,89539041

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

У результаті аналізу основних методів відбору версій ЦСКПЛ, що застосовуються в ГА, було запропоновано схему, яка передбачає використання методу рангового відбору на початкових етапах життєвого циклу популяції, оскільки саме тоді ймовірність формування версій з однаковим рівнем пристосованості є найбільш високою, у той час як у більш пізніх популяціях рекомендується використовувати метод “рулетки”.

Для того, щоб уникнути некоректного ранжування версій з однаковим рівнем пристосованості в разі використання методу рангового відбору, запропоновано нормувати ймовірності відбору версій з однаковою пристосованістю. Суть удосконалення методу: 1) версії поточної популяції з однаковою пристосованістю поєднуються в групи; 2) рулетка розбивається на умовні сектори, кількість яких Mу дорівнює сумі чисел від 1 до g, де g – кількість сформованих груп; 3) група з мінімальним рівнем пристосованості одержує один сектор рулетки, наступна - два сектори і т.д., група з максимальною пристосованістю дістає g секторів; 4) кожний умовний сектор ділиться на h рівних частин, де h - кількість версій у групі.

В результаті рулетка буде розділена на сектори таким чином: , де

M – загальна кількість секторів рулетки; g – кількість груп; hj – кількість версій в j-й групі. Використання методу нормованого рангового відбору дозволяє одержувати необхідні версії у більш ранніх популяціях (табл. 3).

Таблиця 3

Результати експериментів по дослідженню диверсифікації проекту терморегулятора для АН-70 за допомогою ГА на етапі відбору

Експеримент | 1 | 2 | 3 | 4 | 5

Схема відбору | рулетка, елітний | ранговий, елітний | рулетка, ранговий, елітний | нормований ранговий,

елітний | нормований ранговий,

рулетка, елітний

Кількість автоматів | 2 | 2 | 2 | 2 | 2

Автомати одержані на ітераціях | 651-704 | 638-812 | 316-711 | 586-764 | 194-458

Приріст виграшу (число ітерацій ГА) відносно експерименту 5 | 351,5 | 399 | 187,5 | 349 | 0

Основні результати розділу опубліковані в роботах [1, 3, 4, 6].

У четвертому розділі розглядається метод і програмно-технічний комплекс (ПТК) засобів створення й оцінки відмовостійких ЦСКПЛ, отриманих за допомогою ГА. Метод включає два етапи:

- на підставі результатів аналізу вимог до ЦСКПЛ формуються таблиці вихідних даних і вибирається тип автоматів, на яких доцільно будувати систему, після чого за допомогою ГА, розробляється модель ЦСКПЛ;

- на підставі інформації щодо кількості та логіки функціонування автоматів, що входять до складу ЦСКПЛ, розробляється підсистема контролю ЧПА, які утворюють систему. Для цього відповідно до логіки роботи кожного автомата будується еталонна модель поведінки системи, де кожному вхідному сигналу xi ставиться у відповідність множина еталонних (заздалегідь відомих) вихідних сигналів автоматів ; реальні вихідні сигнали автоматів, що відповідають xi, порівнюються між собою, й формується множина реальних вихідних сигналів ;

- множина реальних вихідних сигналів порівнюється з еталонною , і вибирається така пара (,), щоб = , де j – номер автомата, на який можна переключитися.

Для апаратної реалізації відмовостійких ЦСКПЛ на частково працездатних автоматах, що синтезуються за допомогою ГА, на підставі запропонованого методу був розроблений програмно-технічний комплекс (рис. 7).

Рис. 7. Архітектура ПТК засобів розробки ЦСКПЛ за допомогою ГА

Дослідження диверсифікації варіантів ЦСКПЛ у рамках різних підходів до проектування проводилося на прикладі протикригової системи літака АН-70. Для цього на основі існуючого прототипу блоку порівняння регулятора температури в салонілітака АН-70 за допомогою ГА було синтезовано систему, яка реалізує ту ж функціональність, і проведено порівняльний аналіз обох проектів. Версії порівнювалися на фізичному рівні. Відповідно до таблиці істинності було отримано модель, що являє собою два ЧПА (рис. 8). Перенесення моделі в ПЛІС здійснювалось за допомогою пакету Quartus IІ v6.0. Після компіляції загальна кількість логічних комірок проекту склала 27, тоді як у другому проекті їх 74. Для порівняльного аналізу відмовостійкості обох проектів, отриманих за допомогою засобів САПР і ГА, було проведено моделювання відмов в середовищі розробленого емулятора відмов цифрових систем на ПЛІС (рис.9, табл.4). Результати моделювання у випадку ГА-проекту показали виграш в 1,1–13,29 рази по ймовірності |

збереження працездатного стану системи для відмов різної кратності (рис. 10).

Рис. 8. Модель регулятора температури АН-70

Рис. 9. Фізичне розміщення на ПЛІС зайнятих логічних комірок проектів регулятора температури і їх вид в середовищі емулятора відмов ПЛІС

Таблиця 4

Імовірність збереження працездатного стану терморегулятора АН-70 у разі відмов різної кратності |

1-крат. відмова | 2- крат. відмова | 3-крат. відмова | Відмова 5% ПЛІС | Відмова 10% ПЛІС | Відмова 25% ПЛІС | Відмова 50% ПЛІС | Відмова 75% ПЛІС

ГА-проект | 0.9579 | 0.9506 | 0.9428 | 0.8654 | 0.8104 | 0.6632 | 0.3979 | 0.0803

Прототип | 0.8704 | 0.7973 | 0.7445 | 0.4796 | 0.3431 | 0.0499 | 0 | 0

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

Основні результати розділу опубліковані в роботах [4, 5, 10 - 12].

Рис. 10. Виграш за ймовірністю збереження працездатного стану проектів терморегулятора,

ВИСНОВКИ

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

Отримано нові наукові результати, які розвивають методи синтезу багатоверсійних систем в області розробки технологій створення й оцінки надійності відмовостійких ЦСКПЛ.

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

Удосконалено метод розробки багатоверсійних відмовостійких ЦСКПЛ у частині процедури одержання версій за допомогою генетичних алгоритмів. Метод дозволяє автоматизувати процеси синтезу різних версій системи з необхідними характеристиками.

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

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

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

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

1. Yakymets N. Normalized Rank Selection Method and its Application in Design of Fault Tolerant PLD-based Systems Using Genetic Algorithms// Радіоелектронні компютерні системи. – 2007. – № 7 (26). - C.57 - 61.

2. N. Yakymets, V. Kharchenko, N. Sidorenko. Resource-Oriented Diversification of Fault-Tolerant PLD-Systems // Радіоелектронні компютерні системи. – 2006. - № 7. – С. 60-63.

3. Yakymets N., Kharchenko V. Diversification Techniques of Fault-Tolerant Systems on FPGAs Using CAD-Based and Genetic Algorithms-Based Designs // Системи озброєння і військова техніка. – 2006. – № 4 (8). – C. 114-117.

4. Н. В. Якимец, В. С. Харченко. Метод и средства синтеза отказоустойчивых цифровых систем управления с программируемой логикой на основе частично работоспособных автоматов // Вісник Хмельницького національного університету. – 2007. – Т. 1, №3. – C. 209 – 211.

5. Yakimets N.V., Ushakov A.A. Analysis of failure types and development of an adjustable generator of failures for PLDs // Вісник Нац. техн. ун-ту “ХПІ”. – 2003.