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

“КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ”

Романкевич Віталій Олексійович

УДК 621.325.5

Методи та засоби ефективного визначення параметрів відмовостійких багатопроцесорних систем

Спеціальність - 05.13.13 – Обчислювальні машини, системи

та мережі

АВТОРЕФЕРАТ

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

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

Київ 2001

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

Робота виконана в Національному технічному університеті України “Київський політехнічний інститут” на кафедрі спеціалізованих комп’ютерних систем

Науковий керивник: доктор технічних наук, професор

Тарасенко Володимир Петрович,

НТУУ “КПІ”, завідувач кафедрою СКС

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

Тоценко Віталій Георгійович,

Інститут проблем реєстрації інформації НАНУ,

завідувач відділом 106

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

Селігей Олександр Минович,

Український інститут промислової власності,

завідувач відділом електроніки, обчислювальної техніки та зв’язку

Провідна установа: Інститут проблем математичних машин і систем НАНУ, відділ 115

Захист відбудется “ 18 ” 06 2001 р. о 14:30 на засіданні спеціалізова-ної ради Д 26.002.02 у НТУУ “КПІ” (м. Київ, просп. Перемоги, 37, корп. 18, ауд. 306)

Відзиви на автореферат у двох екземплярах, завірені печаткою установи, просимо надсилати на адресу: 03056, м. Київ, просп. Перемоги, 37, вченому секретарю НТУУ “КПІ”.

З дисертацією можна ознайомитись в бібліотеці Національного технічного університету України “Київський політехнічний інститут”

Автореферат розісланий “ 17 ” 05 2001 р.

Вчений секретар Орлова М.М.

спеціалізованої вченої ради

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

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

Розв’язанню головних задач організації відмовостійких багатопроцесорних систем (ВБС) – їх проектуванню та тестуванню – присвячено багато наукових робіт, щороку проводяться десятки конференцій. Враховуючи те, що при проектуванні ВБС використовуються різноманітні види надлишковості, можна зазначити, що iдентифікация стану модулів системи – складна і важлива задача. Найбільш загальний випадок – система без діагностичного ядра, тобто в системі відсутня завідомо дієздатна частина, та без суцільного дублювання модулів. Задача організації процесу діагностування частково розв’язана для різних моделей несправності і різних обмежень на діагностичний граф. Проте задачі оптимiзацiї цього процесу і визначення граничних можливостей становлять науковий інтерес.

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

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

Зв'язок роботи з науковими програмами, планами, темами.

Результати дисертаційної роботи були використані в НТУУ “Київський політехнічний iнстiтут” при виконанні держбюджетних тем: “Методи і засоби побудови відмовостійких багатопроцесорних систем обробки інформації (1994-1995 р.р.), “Методи і математичні моделі оцінки надійності і засоби її підвищення для відмовостійких реконфiгурованих обчислювальних систем”, № держреєстрацiї 0196U009315 (1996-1997 р.р), “Комп’ютерні моделі відмовостійких багатопроцесорних систем керування складними об’єктами” № держреєстрацiї 0198U000738 (1998-2000 р.р.).

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

Об’єктом дослідження є процеси самотестування в сучасних ВБС та їх поведінка в потоці відмов процесорів.

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

Основні задачі дослідження у відповідності до поставленої мети полягають у наступному.

1. Аналіз і систематизація методів і засобів дiагностування ВБС та поведінки ВБС у потоці відмов.

2. Розробка методів виконання діагностичного експерименту в комутованих ВБС, спрямованих на його оптимiзацію, а також одержання оцінок кількості елементарних перевірок і кількості тактів.

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

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

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

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

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

1. Вперше запропоновано метод оптимiзацiї процесу дiагностування в самотестованих багатопроцесорних системах, що дозволяє мiнiмiзувати кількість елементарних тестових перевірок. Доведено, що в рамках широко розповсюдженої діагностичної моделі для визначення стану всіх компонент системи достатньо не більш ніж n+2t перевірок (n – кількість компонент системи, t – кількість реальних відмов).

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

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

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

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

Практичне значення одержаних результатів визначається тим, що вони дозволяють оптимiзувати процес самодiагностування в ВБС, проводити аналіз їх поведінки в потоці відмов і більш точно визначати і розраховувати їх параметри. Результати роботи можуть бути використані в організаціях, що займаються проектуванням і експлуатацією відмовостійких багатопроцесорних обчислювальних систем і систем керування складними об’єктами. Результати, що стосуються побудови і використання графо-логічних моделей, а також генерації булевих функцій для них, використовуються в Національному технічному університеті України “Київський політехнічний iнстiтут” кафедрою “Спеціалiзовані комп’ютерні системи” при викладі курсів “Прикладна теорія цифрових автоматів ч.2”, а також “Надійність, контроль, діагностика і експлуатація комп’ютерних систем”. Результати, що стосуються оптимізації діагностичного експерименту та побудови графо-логічної моделі циклічного типу прийняті до використання у ВАТ “РИТМ” м. Київ.

Особистий внесок здобувача полягає в розробці нових методів, алгоритмів і програм, що забезпечують розв’язання поставлених задач. Всі основні результати роботи одержані автором особисто. В публікаціях, написаних в співавторстві, здобувачеві належить: в роботі [1] – ідея і алгоритм генерації функцій для циклічної базової моделі; в роботі [2] – метод проведення діагностичного експерименту в ВБС, що оптимiзує час, і алгоритм оперування з множиною потенційно несправних модулів; в роботі [4] – ідея методу і алгоритм формування функцій з допомогою таблиць; в роботі [5] – методика проведення статистичного експерименту з моделлю ВБС для розрахунку надійності; в роботі [6] – ідея декомпозицiї системи; в роботі [7] – метод побудови нециклічних GL-моделей базових підсистем ВБС; в роботі [8] – нециклічні моделі для довільних ВБС; в роботі [9] – iєрархічна модель ВБС.

Апробація результатів дисертації. Основні результати роботи доповідалися і обговорювалися на науково-технічних семінарах кафедри спеціалізованих комп’ютерних систем НТУУ “КПІ” (жовтень 1997, жовтень 1998, листопад 1999), на 9-й, вересень 1996, 10-й, вересень 1997, 11-й, вересень 1998, 12-й, вересень 1999 міжнародних школах-семінарах “Перспективні системи управління на залізничному, промисловому і міському транспорті” (ХарГАЖТ – УЗ – НАНУ), а також на 2-й Всеукраїнській молодіжній науково-практичній конференції “Людина і космос”, Дніпропетровськ НЦАОМУ 2000.

Публікацiї. По темі дисертації опубліковано 9 наукових робіт, в тому числі 4 статті в наукових журналах, 5 тез доповідей.

Структура і об’єм дисертації. Дисертаційна робота складається з вступу, чотирьох розділів, висновків і 2 додатків. Робота містить 137 сторінок друкованого тексту, 28 рисунків, 10 таблиць і список використаної літератури на 87 найменувань.

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

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

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

вона не накладає практично ніяких обмежень на результат перевірки rij процесора vj процесором vi;–

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

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

Вводяться визначення.

Визначення 1. Множиною потенційно несправних модулів самотестованих багатопроцесорних систем назвемо будь-яку множину IV, в якій кількість працездатних модулів не перебільшує кількості несправних. Приклад множини потенційно несправних модулів I={vi,vj} для випадка rij=1.

Визначення 2. Вагою модуля viV\I назвемо число mi=|Q(vi)|, де Q – обернено транзитивне замикання за нульовими тестовими перевірками. Фактично mi – кількість модулів, що беруть участь у шляхах, які закінчуються в vi та містять нульові перевірки.

Нагадаємо, що для ПМЧ-моделі характерно: rnn=0, rnf=1, rff=x, rfn=x; тут n – працездатний модуль; f – несправний модуль; х – невідомий результат (х може бути 0 або 1).

Доводиться теорема.

В паралельно t-діагностованій (0tT=(N-1)/2) ВБС, що складається з N модулів, для виконання діагностичного експерименту в рамках ПМЧ-моделі достатньо N+2t елементарних перевірок.

Пропонується алгоритм проведення діагностичного експерименту, що складається з двох етапів: пошуку працездатного процесора і після цього - визначення стану усіх процесорів системи. Для розв’язання задачі першого етапу пропонується алгоритм.

Алгоритм.

1. i=1, I=. Перейти до 2.

2. Якщо ri,i+1=1, то перейти до 3, інакше до 6.

3. I=I{vi,vi+1}. Перейти до 4.

4. i=i+2. Перейти до 5.

5. Якщо i<N, то перейти до 2, інакше до 10.

6. Якщо vi – початок шляху, то перейти до 7, інакше до 8.

7. mi=1. Перейти до 8.

8. mi+1=mi+1. Перейти до 9.

9. i=i+1. Перейти до 5.

10. Кінець.

На базі визначень 1 і 2 записуються ознаки, що дозволяють ідентифікувати працездатний процесор:

vkV\I (I=2T) vkF

vklj (mk>T-I/2) vk F ,

де F – множина несправних процесорів у ВБС.

Дійсно, згідно першої умови довільний процесор vi , що не входить в певну множину I, де вже ідентифіковано Т несправних процесорів, є працездатний.

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

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

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

Доводиться наступна теорема.

Для ідентифікації працездатного модуля достатньо не більше [Log N] тактів.

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

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

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

Принцип побудови GL-моделей полягає в наступному. Нехай маємо деякий зв’язний неорієнтований граф G, ребра якого позначаються певним чином вибраними булевими функціями , де кожна змінна xi () є індикаторною функцією, що позначає стан і-го елементу системи, тобто xi=1, якщо і-й елемент системи працездатний, і xi=0 у протилежному випадку. Ребро, позначене функцією , залишається в графі G, якщо і видаляється з нього, якщо .

Якщо обрати функції таким чином, щоб граф G згубив зв’язність тільки на тих векторах стану ВБС, де має місце її відмова, то буде одержана потрібна GL-модель. Очевидно, що дуже важливими етапами при побудові графо-логічної моделі є вибір графа G і функцій .

В подальшому систему, що містить n модулів і стає непрацездатною лише тоді, коли відмовляють не менш ніж m її модулів, будемо називати базовою ВБС и позначати m-ВБС, а її модель – K(m,n).

Зупинимось далі на випадку 2-ВБС. В якості графа G оберемо неорієнтований циклічний n-ребровий граф, i-му ребру якого відповідає булева функція

для .

Доводиться наступна теорема.

Граф G губить зв’язність, якщо і тільки якщо не менш ніж три змінні з множини {x1,...,x n} приймають нульові значення.

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

Рис. 1

Недолік: теорема справедлива лише для випадку 2-ОМС. На рис. 1 приведена модель K(2,6).

Для розв’язання задачі побудови базової GL-моделі в загальному випадку (довільні значення m і n) пропонується інший підхід. Нехай m-ВБС має n елементів, і множина, що складена з цих елементів, розбита на q підмножин з кількістю елементів n1, n2, … ,nq відповідно. Нехай також існують , L>1 - такі булеві функції, що кожна з них приймає нульове значення, якщо дорівнюють нулю, принаймні, m змінних, що визначають стани mi елементів для кожного з ni – підмножин (i) у відповідності з усіма можливими комбінаціями чисел m1, m2, …, mq з i-го набору.

Тоді справедлива наступна теорема.

Не менш ніж дві функції з множини приймуть нульові значення, якщо, принаймні, m+1 з n змінних дорівнюють нулю.

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

де має місце

Реброві функції формуються кожна по-своєму. Їх кількість і складність залежать від m і n, а також від розбиття вихідної множини процесорів ВБС на підмножини з наступним розподілом відмов між підмножинами. Достатньо велика кількість експериментів, проведених для різноманітних значень m і n, показала, що оптимальним є розбиття вихідної множини змінних (процесорів) і наступних підмножин кожен раз на дві рівні підмножини. Відзначаються властивості, які полегшують формування ребрових функцій: для випадку однієї відмови, тобто для K(1,i), функція, що моделює поведінку відповідної підмножини процесорів, зводиться до кон’юнкції змінних, а для випадку i відмов, тобто K(i,i) – до диз’юнкції змінних.

Формування функцій для випадку K(4,8) ілюстровано прикладом, що демонструє можливість формування булевих функцій безпосередньо з таблиць.

{ x 1, x 2, x 3, x 4} | { x 5, x 6, x 7, x 8 }

К ( 4, 4 )

К ( 3, 4 ) | К ( 1, 4 )

К ( 2, 4 ) | К ( 2, 4 )

К ( 1, 4 ) | К ( 3, 4 )

К ( 4, 4 )

{ x 1, x 2} | { x 3, x 4}

К( 2, 2) | К( 1, 2)

К( 1, 2) | К( 2, 2)

{ x 1, x 2} | { x 3, x 4}

К( 2, 2)

К( 1, 2) | К( 1, 2)

К( 2, 2)

{ x 5, x 6} | { x 7, x 8}

К( 2, 2) | К( 1, 2)

К( 1, 2) | К( 2, 2)

{ x 5, x 6} | { x 7, x 8}

К( 2, 2)

К( 1, 2) | К( 1, 2)

К( 2, 2)

Як вже відзначалось, область використання ВБС – це, передусім обчислювальні системи і системи керування складними об’єктами. При цьому для обчислювальних систем характерні регулярність структури та однотиповість процесорів, що в деякій мірі полегшує їх проектування і розрахунок параметрів. Для систем керування навпаки – порівняно менша кількість процесорів (десятки, сотні, інколи тисячі) і відносна нерегулярність структури. Останнє пов’язано, як правило, з великою кількістю джерел інформації різноманітного типу (датчиків) і різнотиповістю процесорів. Для нас інтерес становить також той факт, що різні частини системи, що керують різними ділянками об’єкту (простіше кажучи, підсистеми), повинні бути захищені від відмов по різному. До цього потрібно добавити, що реальні ВБС керування складними об’єктами не відповідають визначенню базових: система (або підсистема) може вийти з ладу при виникненні k певних відмов і, в той же час, бути стійкою до s інших відмов при s>k. Сказане призводить до задачі трансформації базових моделей K(m,n) таким чином, щоб вони могли відображати реакцію ВБС на заданих векторах станів, де кратність відмов не дорівнює m. В дисертації розглянуто в рамках GL-моделей дві можливості: більш складні функції, що приписуються ребрам циклічного графа, і більш складні графи.

Нехай на деякому векторі стану

x1 x2 x3 … xm xm+1 xm+2 … xn

0 0 0 … 0 0 1 … 1

ВБС залишається працездатною (тут 0 означає відмову компоненти). Нехай базова модель K(m,n) губить на цьому наборі ребра a1 і a2, тобто граф G губить зв’язність. Стверджується, що для збереження адекватності моделі достатньо ребру a1 з функцією f1()=0 приписати функцію f1*=f1Q (Q – конституєнта 1 для набору ), або провести додаткове ребро і приписати йому функцію =Q. Додаткове ребро повинне проходити між ребрами a1 и a2 базової моделі.

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

В третьому розділі розглядаються також базові моделі нециклічного типу. Пропонується декілька видів таких моделей (один з них приведений на рис. 2 для випадку K(3,8)). Аналізуються їх можливості, виконується порівняння з циклічними моделями, для чого запропоновано критерій

S = R + УRi=1 Si,

де R – загальна кількість ребер графа GL–модели; Si – складність подання булевої функції, що приписується i-ому ребру, відображена в кількості двомістних операцій. Виявляється, що розглянуті моделі нециклічного типу займають проміжне положення між моделями, запропонованими в розділі 2. Розв’язується задача трансформації цих моделей для відбивання більш низького або високого ступеню відмовостійкості заданої ВБС по відношенню до базової подібно тому, як це робиться для циклічних моделей.

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

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

Далі пропонується ієрархія GL–моделей підсистем. Основна ідея створення ієрархічної моделі полягає в тому, що моделі більш низького рівня слугують змінними для ребрових функцій моделей більш високого рівня. Це дозволяє звести задачу відображення на моделі здатності вихідної ВБС бути нечутливою до відмов деяких сукупностей своїх підсистем на певних векторах станів до задачі синтезу GL–моделей, розглянутих раніше, в розділах 2 і 3.

Далі в розділі розглядається організація проведення експерименту з побудованою моделлю деякої ВБС для розв’язання двох задач: визначення “вузьких місць” і розрахунку надійності. Обидві задачі виникають на етапі проектування. Перша пов’язана з пошуком векторів стану ВБС, що мають максимальну ймовірність появи і призводять до відмови системи. Зрозуміло, що ймовірність появи 1 (відмова процесора) в якомусь розряді вектору визначається інтенсивністю відмов відповідного процесора. Друга задача також потребує генерації векторів станів, причому в ще більшій кількості. Тому в дисертації приділяється достатньо багато уваги генерації векторів станів ВБС, з одного боку, і порядку їх подачі на модель, з іншого. Останнє впливає на складність і швидкодію самого генератора і на ефективність організації експерименту в цілому шляхом, наприклад, зменшення кількості “порожніх” експериментів, які не впливають або майже не впливають на кінцевий результат визначення параметрів ВБС. Пропонується наступна організація формування векторів станів системи для виконання експерименту з GL–моделлю заданої ВБС. З початку генеруються усі можливі вектори з вагою 1, потім – з вагою 2 і т.д. до деякого значення k1. Підраховується ймовірність появи відмови в цій частині експерименту

Qc=?(i)·p(i),

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

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

Необхідно відзначити, що значну роль на цьому етапі грає джерело векторів станів ВБС, що імітує потік відмов. Ефективність виконання моделювання і розрахунку значною мірою залежить від якісних характеристик генерованих псевдовипадкових послідовностей багаторозрядних наборів із заданою вагою ((,)-наборів), які відображають відмовні ситуації в досліджуваній системі для різних значень кратностей відмов її елементів. В роботі запропоновано принцип побудови (,)-генератора, оснований на моделюванні марковського процесу, станами якого є випадкові перестановки n элементів. Якщо – перестановка, що відображає стан процесу в момент часу , а – випадковий вектор, що переводить процес у стан , то здійснюється підстановка

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

, якщо = 1; , якщо ,

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

,

де , функція визначається з виразу:

.

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

Останній підрозділ (4.3) присвячений структурній організаціі спеціалізованої комп’ютерної системи, що націлена на виконання експерименту з GL-моделями ВБС, запропонованими в розділах 2 та 3. Структура такої спеціалізованої комп’ютерної системи має вигляд, наведений на рисунку 3.

Система є централізованою: комплекс засобів, що представлен у верхній частині рисунку 3 знаходиться у хост-комп’ютері, модулі. що представлені знизу, розташовані у кожному з комп’ютерів тієї локальної мережі, яку має у своему розпорядженні користувач. Функції, що виконуются кожним з модулів є зрозумілими з того , що сказано вище. Сюди треба додати кілька слів про модуль оптимізації, що входить до блоку “компілятор GL-моделі”. Він вирішує дві різні задачи. Перша задача – це виконання оптимізації GL-моделі на рівні її структури (ребра та реброві функції). Це дозволяє, в де-яких випадках, значно спростити модель і таким чином зменшити обсяг обчислень. Друга задача оптимізації пов’язана безпосередньо із процесом обчислень: GL-модель транслюєтся у спеціальні структури даних, які є найбільш ефективними для виконання комп’ютерного обчислення булевих функцій та зв’язності графу. Основна ідея оптимізації полягає в побудові дерева рішень як для обчислення булевих функцій, так і для зв’язності графу. Після цього дерево рішень транслюєтся в асемблерно-подібний псевдокод, що може виконуватися за допомогою блоку “розрахункове ядро”. Для підвищення продуктивності обчислень псевдокод може бути перетворений безпосередньо в комп’ютерний код.

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

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

Рис. 3

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

ОCНОВНІ ВИСНОВКИ І РЕЗУЛЬТАТИ РОБОТИ

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

Головні наукові і практичні результати роботи полягають у наступному.

1.

2.

3.

4.

5.

6.

7.

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

1.

2.

3.

4.

5.

6.

7.

8.

9.

АНОТАЦІЇ

Романкевич Віталій Олексійович. Методи та засоби ефективного визначення параметрів відмовостійких багатопроцесорних систем. – рукопис.

Дисертація на здобуття вченого ступеня кандидата технічних наук за спеціальністю 05.13.13 – обчислювальні машини, системи та мережі. Національний технічний університет України “Київський політехнічний інститут”, Київ, 2001.

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

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

Romankevitch V.A. Methods and Means for Effective Determination of Fault-Tolerant Multiprocessor Systems’ Parameters. – Manuscript.

Thesis for the candidate’s degree by the specialty 05.13.13 – computing machines, systems and nets. – National Technique University of Ukraine “Kiev Polytechnic Institute”, Kiev, 2001.

Thesis deals with development of methods and means providing more effective determination of fault-tolerant multiprocessor systems’ parameters. New methods for organizing of diagnostic experiment into self-diagnosable multiprocessor systems have been proposed. The methods allow to determine and minimize an important parameters of such systems, namely the number of elementary test operations and the number of the experiment steps directed to determination of states for all processors of the system.

New model of fault-tolerant multiprocessor systems’ behavior in failure flow had been proposed, the methods of its transformation in dependence of changes in the system fault-tolerance’ degree had been designed. Basis of the model is a graph which arcs are marked by some Boolean functions and the arguments of these functions are system processors states. Existence of these arcs is determined by values of above mentioned Boolean functions.

Structure of specialized computer system, controlled generator of pseudorandom patterns which imitates failure flow and organization of experiments with designed graph-logic models had been proposed. All it together allows to determine different parameters of fault-tolerant multiprocessor systems’ parameters by using of available computing means.

Key words: fault-tolerant multiprocessor systems, testing, graphs, Boolean functions, controlled pseudorandom number generators.

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

Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.13 – вычислительные машины, системы и сети. Национальный технический университет Украины “Киевский политехнический институт”, Киев, 2001.

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

На основе анализа работ, посвященных исследованию самотестируемых многопроцессорных систем, выбрана модель Препарата-Метца-Чена, и в рамках этой модели предлагаются методы организации диагностического эксперимента, позволяющие минимизировать два важных параметра систем: количество элементарных тестовых проверок до N+2t (N- число процессоров системы, t-число реальных отказов) и количество тактов до величины [Log N]+1. Доказываются необходимые теоремы и предлагаются алгоритмы проведения эксперимента, обеспечивающие решение поставленной задачи.

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

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