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

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

Автореферат

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

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

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

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

статистичний експеримент графологічний обчислювальний

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

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

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

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

Зв'язок роботи з науковими програмами, планами, темами. Дисертаційні дослідження виконувалися на кафедрі спеціалізованих комп'ютерних систем Національного технічного університету України «Київський політехнічний інститут» в рамках науково_дослідних робіт:

- «Методи та засоби оцінки надійності реконфігуровних відмовостійких багатопроцесорних систем», № держреєстрації 0107U002168 (2007-2009 рр.);

- «Спеціалізована комп'ютерна система діагностування та розрахунку надійності реконфігуровних відмовостійких багатопроцесорних систем», № держреєстрації 0110U000262 (2010-2011 рр.).

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

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

Провести аналіз методів розрахунку ймовірності безвідмовної роботи ВБС різних типів. Виконати аналіз відомих моделей відображення реакції ВБС на появу відмов. Обґрунтувати вибір методу розрахунку ІБР відмовостійкої системи шляхом виконання статистичних експериментів з GL_моделями.

Виконати порівняльний аналіз складності канонічної GL-моделі та 2р-моделі за параметрами: кількість базових ребер, прогнозована кількість додаткових ребер після трансформації, сумарне кількість булевих операцій у записі реберних функцій моделі. Обґрунтувати використання 2р-моделі для проведення статистичних експериментів.

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

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

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

Розробити методику прогнозування складності небазової ВБС на основі існуючих попарних реберних циклів (ПРЦ) в 2р-моделі базової ВБС.

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

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

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

Предметом дослідження є алгоритми та апаратно-програмні засоби формування та підтримки використання GL-моделі при розрахунку ймовірності безвідмовної роботи ВБС шляхом проведення статистичних експериментів.

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

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

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

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

Вперше отримані і доведені співвідношення для оцінки складності канонічної GL_моделі та 2р_моделі базових ВБС за параметрами кількості базових ребер і сумарної складності реберних функцій. Ці співвідношення дозволяють вибрати простішу GL_модель, використання якої дозволяє скоротити час проведення одного експерименту, що в кінцевому підсумку підвищує точність розрахунку ІБР.

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

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

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

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

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

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

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

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

- Науково-технічних семінарах кафедри спеціалізованих комп'ютерних систем НТУУ «КПІ», м. Київ (2007-2011 рр.);

- 17-й (вересень 2004 р.), 21-й (вересень 2008 р.), 22-й (вересень 2009 р.), 23-й (вересень 2010 р.) міжнародних науково-практичних конференціях «Перспективні комп'ютерні, керуючі і телекомунікаційні системи для залізничного транспорту України », м. Алушта;

- 7-й міжнародній науково-практичній конференції «Сучасні інформаційні та електронні технології», м. Одеса, травень 2007;

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

- 2-й науково-практичній конференції магістрантів та аспірантів «Прикладна математика та комп'ютінг», м.Київ, квітень 2010 р.

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

Структура та обсяг дисертації. Дисертаційна робота складається зі вступу, п'яти розділів, висновків і додатків. Загальний обсяг роботи становить 163 сторінок друкованого тексту, 31 рисунка, 8 таблиць та списку використаної літератури на 130 найменувань.

Основний зміст работи

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

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

Для різних систем вигляду k-out-of-n (k-out-of-n - система з n елементів, яка зберігає працездатність, якщо залишаються працездатними щонайменше k її елементів) розрахунок ІБР здійснюєт6ься на основі простих формул і співвідношень без складних обчислень. Однак, для розглянутих у роботі ВБС управління складними об'єктами зазначені формули дозволяють отримати лише досить грубу оцінку показника надійності, або не можуть бути застосовані взагалі.

Розглянуто відомий підхід до розрахунку показників надійності, що полягає у використанні RBD (reliability block diagrams - блок діаграм надійності) або структурної функції (логічної моделі, логічної функції працездатності) для формування ймовірнісної моделі, за якою вже виконується розрахунок ІБР. Такий метод зазвичай застосовується для ВБС, які в плані реакції на появу відмов мають порівняно невелике відхилення від базових систем k-out-of-n. Для складних ВБС управління застосування зазначеного підходу пов'язано або з великими обчислювальними витратами для побудови ймовірнісної моделі, або з великою похибкою кінцевого результату. З тих же причин для складних небазових ВБС недоцільне використання безпосереднього розрахунку показника надійності по FT (fault tree) - дереву відмов.

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

В якості моделі реакції (працездатності) системи на появу відмов пропонується використовувати розроблену на кафедрі спеціалізованих комп'ютерних систем НТУУ «КПІ» графо-логічну модель (GL-модель).

GL-модель представляє собою неорієнтований граф, в якому ребра маркуються певним чином сформованими булевими функціями f_i. Реберні функції f_i залежать від індикаторних змінних x₁, x₂,.., x_n, кожна з яких відображає стан свого елемента системи (0 - відмову, 1 - працездатний), сукупність значень (x₁, x₂,…, x_n) називається вектором стану системи і позначається X. Якщо f_i(X) = 0, то i-те ребро виключається з графа моделі. Зв'язність графа GL-моделі на векторі X відповідає працездатності системи в цьому стані. Таким чином GL-модель ставить у відповідність стан системи, що описується вектором X, і працездатність системи у цьому стані.

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

Приводяться існуючі алгоритми побудови канонічної та спеціальної GL_моделі - 2р-моделі для базових ВБС. ВБС називається базовою, якщо вона стійка (зберігає працездатність) до всіх і тільки до таких відмов, кратність яких не перевищує фіксовану величину m. Такі системи позначені через K(m, n), що відповідає (n_m)_out-of-n системам. Детально властивості канонічної GL-моделі та 2р-моделі аналізуються в другому і третьому розділах відповідно.

Небазовою називається ВБС, яка зберігає працездатність на всіх векторах X з (X)im та додатково на деякій множині векторів W={w₁,w₂,w₃,...}, причому для всіх w_i W виконується (w_i)>m, де (X) - кількість нулів у векторі X.

Розглянуто відомий метод трансформації GL-моделі базової ВБС до моделі небазової ВБС шляхом введення в граф моделі додаткових ребер зі своїми функціями.

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

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

В основу базової канонічної GL_моделі покладено граф циклічного типу, а реберні функції формуються відомим методом з послідовним поділом множини індикаторних змінних с _r={x₁, x₂,..., x_n} на дві рівні або майже рівні частини.

У роботі запропоновано спосіб нумерації множин індикаторних змінних, згідно з яким с _abс _daс _dafr. Також, завдяки введеним в роботі додатковим умовам множину с _a можна визначити за її номером (без поетапного поділу) відповідно до виразу: с _a={x_t}, t[aj+bc+1..a(j+1)+b(c+1)+1], де j=a-2ⁱ, i=[log₂a], a=n/2ⁱ, b= j/(2ⁱ_{n/2ⁱ}), c= j-2ⁱ+{n/2ⁱ}, a - номер множини.

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

.(1)

де f, g - реберні функції, f, g, |с _a|>m_x, m_x-ii|с _2a|, ii|с _2a+1|, а - множина реберних функцій канонічної GL-моделі системи K(m_x_1,с _a).

Виводиться рекурсивна формула для визначення кількості базових ребер канонічної GL-моделі r=r(m,с ₁):

.(2)

Далі в роботі виконується дослідження (прогнозування) складності моделі небазової ВБС після її трансформації від GL-моделі базової ВБС за параметром кількості додаткових ребер. Розглянемо це питання докладніше.

Нехай, задана множина векторів стану системи W={w₁,w₂,w₃,...}, при чому w_i W граф моделі втрачає два ребра. Множина таких пар ребер позначається як L, в загальному випадку |L|i |W|.

Введемо поняття графа V={A, L}, де множина вершин V-графа A - множина базових ребер GL-моделі, а ребра проводяться відповідно до множини L. S_підмножина - це множина ребер моделі базовї ВБС, вибірка по два з якої не збігається ні з одним елементом множини L (фактично внутрішньо стійка множина вершин графа V).

За відомим алгоритмом трансформації оптимальна кількість додаткових ребер, проведення яких дозволяє блокувати втрату зв'язності графа моделі при появі векторів з W, дорівнює [s/2], де s - кількість S-підмножин. Формування самих S_підмножин здійснюється на основі розфарбовування графа V.

Фактично розбиття множини А на S-підмножини визначає проведення додаткових ребер, і, як наслідок, складність канонічної GL-моделі можна оцінити на основі кількості S-підмножин. В роботі доведено, що:

.(3)

У кінці розділу виводиться формула оцінки складності базової канонічної GL_моделі по параметру сумарного числа операцій в аналітичному записі реберних функцій, і порівнюється зі складністю запису відповідної структурної функції у вигляді ДНФ. На прикладі базових систем K(m,15) показується, що канонічна модель має меншу складність.

Показано, що використання канонічної GL-моделі для розрахунку ймовірності безвідмовної роботи ВБС пов'язано з великою обчислювальною складністю.

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

Базова 2р-модель - це спеціальна циклічна GL-модель системи K(m,n), основною перевагою якої є втрата строго двох ребер при появі вектора стану системи X з (X)=m+1. Відомий алгоритм формування 2р-моделі шляхом мінімізації канонічної моделі за допомогою операцій склеювання має велику складність, тому в роботі пропонується модифікація зазначеного алгоритму формування базових ребер 2р_моделі, в якій виключена складна процедура мінімізації та, що більш важливо, проміжна побудова канонічної GL_моделі:

K'(m_x,с _a)= K'(m_x,с _2a) f(K'(m_x-i,с _2a)) f(K'(i,с _2a+1))]K'(m_x-i,с _2a+1),(4)

де f(K'(m_x,с _a))=, f(K'(1,с _a))=, f(K'(|с _a|,с _a))=,K'(m_x-1,с _a) - множина реберних функцій 2р-моделі системи K(m_x-1,с _a). Оцінити часову складність представленого алгоритму можна величиною O(n•m^log2(n/m)).

В подальшому wW виконується (w)=m+1.

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

Рис. 1. Дерево ієрархії реберних функцій 2р-моделі K(4,15)

Також пропонується і доводиться положення, на основі якого можна зменшити складність 2р-моделі небазової ВБС.

Твердження 1. При появі вектора X при (X)=m+1 з множини функцій 2р_моделі базової ВБС K(m,n) приймають нульові значення тільки такі дві функції, яким відповідають вершини на дереві ієрархії з наступними властивостями:

а) або вони розташовані на одній гілці дерева,

б) або є сусідніми.

Отримана формула для визначення кількості базових ребер 2р-моделі:

.(5)

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

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

Оскільки проведення додаткових ребер визначається оптимальним розфарбуванням вершин V-графа, то за аналогією з виразом (3) задачу пошуку границі кількості додаткових ребер можна звести до задачі визначення граничного значення s за заданими значеннями n, m та l.

Функція максимального значення величини s для 2р_моделі збігається з її верхньою границею для канонічної GL-моделі у формулі (3), однак обмеження твердження 1 на пари ребер, що можуть вилучатися, вносить свою корекцію:

s_max(l)= и s_max(l)?k+1,(6)

де k=]log₂(n/m)[.

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

.(7)

В роботі доводиться, що s_min(l) та l_max(s) - суть взаємно обернені функції. Враховуючи це, на основі графіка виразу (7) можна оцінити значення s_min(l). Приведені вирази (6) та (7) дають можливість прогнозувати складність 2р-моделі небазової системи, а також, при порівнянні з виразом (3), показують явну перевагу 2р-моделі над канонічною.

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

для >m.(8)

Таким чином, вираз (8) узагальнює відому властивість втрати графом 2р_моделі двох ребер на векторах X з (X)=m+1 для векторів з довільним числом відмов і дозволяє зменшити складність проведення одного експерименту з цією моделлю.

Далі розглядаються попарні реберні цикли (ПРЦ). ПРЦ представляють собою сукупність ребер 2р-моделі, які в графі V, що побудований на основі множини L, утворюють елементарний цикл. Наявність ПРЦ ускладнює процедуру трансформації, а також збільшує складність 2р-моделі небазової ВБС, яка отримується внаслідок проведення трансформації.

У роботі пропонується ряд тверджень, які дозволяють на ранніх етапах проектування моделі оцінити необхідну і достатню кількість додаткових ребер, проведення яких забезпечує її адекватність. Твердження ґрунтуються на аналізі можливих ПРЦ у 2р-моделі, що проектується.

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

K'(m_x,с _a)= K'(m_x,с _2a) f(m_x-i,с _2a) f(i,с _2a+1)]K'(m_x-i,с _2a+1),(9)

де |с _a|>m_x, m_x-ii|с _2a|, ii|с _2a+1|.

Згідно (9) формування функцій f(m_x-i,с _2a) та f(i,с _2a+1) виконується в порівнянні з (4) без побудови відповідних множин K'. Запропонований алгоритм має часову складність порядку O(nm), що при >2 менше складності алгоритму, котрый реалізує вираз (4).

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

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

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

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

В основу запропонованого генератора покладений керований зсувний регістр. Нехай n - кількість розрядів регістра, тобто довжина генерованих векторів, k - вага кожного такого вектора. Нехай x₁, x₂,…, x_n - булеві змінні, що відображають стан відповідних розрядів регістра, а X = (x₁, x₂,…, x_n) - генерований двійковий вектор.

В загальному випадку для кожного розряду може бути визначена функція затримки таким чином, що значення i-го розряду в наступному (t+1) такті визначається з виразу: x_i(t+1)=x_l(t), де l=, при умові , або l=якщо , а f_j - значення функції затримки для j-го розряду генератора в поточному такті t. В роботі детально розглядається окремий випадок такого генератора з f_i= 0, i=2..n, при цьому f₁ = f визначається особливим чином, за запропонованими в роботі алгоритмами. Структурна схема такого генератора представлена на рис.2.

Рис. 2. Структура автономного генератора

Ключовим при побудові генератора є формування функції затримки (управління). Позначимо B_n - множина всіх двійкових векторів довжини n, - множина всіх векторів довжини n, вага яких дорівнює k, B_n. Визначимо F як множину функцій затримки f(X), таких, що для f(X)F період генератора є максимальним та дорівнює ||= тактів. Операцію конкатенації векторів будемо позначати як «+».

Доводиться існування хоча б однієї f(X)F, для чого вводиться поняття графа переходів, який відображає можливі зміни стану генератора у відповідності зі значенням функції управління.

Нехай Y=(x₂, x₃,…, x_n-1) , причому f(Y)= f((0)+Y+(1))= f((1)+Y+(0)). Доводиться положення про те, що значення будь-якої f(X)F не визначено на векторах, що належать множині B_n\.

Виводиться наступний вираз:

NumS(n,k)-1i rang(f)i-NumD(n,k)+1,(10)

де rang(f)=, NumS(n,k)= , NumD(n,k) = NumS(n_1,k) + NumS(n_1, k_1), r(n, k)=_.

Аналітичне подання f(X)F у вигляді ДНФ після запропонованих в роботі спрощень містить не більше ніж (k-1)rang(f) букв.

Розроблено алгоритми перевірки функції затримки f на приналежність множині F. Показано, що задачу пошуку функції затримки f(X)F можна звести до пошуку гамільтонового циклу в графі переходів.

Пропонується формула, що породжує всі можливі функції затримки f(X)F для випадку k=2 (n>]k/2[):

f =,(11)

де t(i) для кожного значення i може приймати одне з двох значень i+1 або n_i.

Також знайдено загальний вигляд виразу для формування певної множини функцій затримки для випадку k=3 (n>]k/2[):

f =, (12)

де t=x_[n/2]x_[n/2]+1, якщо n=3[n/3]-1, та 0 в протилежному випадку.

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

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

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

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

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

В основу статистичного розрахунку покладено відомий алгоритм, згідно з яким експеримент виконується послідовно, для векторів кожної кратності відмов k окремо, і зводиться до визначення ІБР за наступною формулою:

P(y=1) =,(13)

де y - булева змінна, що відображає стан працездатності ВБС, значення S_k= достатньо легко визначається відомими алгоритмами (розділ 1), причому у векторі X відмові елемента відповідає одиничне значення індикаторної змінної, k_min та k_max визначаються або оператором (розробником), або обчислювальною системою.

Значення ймовірності безвідмовної роботи системи на множині векторів :

P_k=.(14)

де = , - номер змінної, яка стоїть на i-му місці в списку змінних вектора X, чиє значення дорівнює 1.

На рис.3 приводиться структурна схема пропонованої обчислювальної системи.

Рис. 3. Структурна схема обчислювальної системи

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

Запропонована система дозволяє досить ефективно розраховувати ІБР відмовостійких систем доступними засобами, з необхідною точністю.

ВИСНОВКИ

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

Основні результати роботи полягають у наступному:

Виконано порівняльний аналіз відомих методів розрахунку показників надійності систем, у тому числі статистичних. Встановлено, що для розрахунку ІБР складних ВБС управління відповідальними об'єктами доцільно використовувати статистичний метод з використанням GL_моделей, проте в цьому напрямку необхідні додаткові дослідження.

Запропонована формалізація методів побудови канонічної GL_моделі та 2р_моделі базових ВБС. Отримано формули для визначення складності цих моделей, на основі яких обґрунтовано вибір проведення статистичних експериментів саме з 2р-моделями. Наприклад, для системи K(4,15) складність канонічної моделі в 2.85 рази перевищує складність 2р-моделі.

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

На основі дослідження різних властивостей та особливостей 2р-моделі розроблено більш прості алгоритми формування і розрахунку реберних функцій 2р_моделі базової ВБС, що дозволяє скоротити час проведення статистичного експерименту. Розрахунок всіх функцій 2р-моделі системи K(4,15) запропонованим алгоритмом вимагає в 2.4 рази меншої кількості операцій у порівнянні з прямим розрахунком.

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

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

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

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

Майданюк И.В. Граничные оценки числа рёбер GL_моделей поведения отказоустойчивых многопроцессорных систем в потоке отказов / А.М. Романкевич, В.А. Романкевич, И.В. Майданюк // Электронное моделирование. - 2008. - Т. 30, № 1. - С. 59-70. Дисертантом сформульоване та доведене твердження про кількість ребер 2р_моделі базової ВБС, а також знайдено верхню оцінку числа додаткових ребер при перетворенні канонічної GL-моделі.

Майданюк И.В. О сложности преобразования GL_моделей на ранних этапах проектирования отказоустойчивых многопроцессорных систем / А.М. Романкевич, И.В. Майданюк, Е.Р. Потапова // Радіоелектронні і комп'ютерні системи. - Харків : «ХАІ», 2009. - №7. - С. 74-77. Здобувачем отримано ряд тверджень про достатню кількість додаткових ребер при перетворенні циклічної GL_моделі на основі попарних реберних циклів.

Майданюк И.В. Частный случай граничных оценок при построении и преобразовании GL-модели / А.М. Романкевич, В.А. Романкевич, И.В. Майданюк // Радіоелектронні і комп'ютерні системи. - Харків : «ХАІ», 2010. - №6. - С. 236-243. Дисертантом сформульоване и доведене узагальнене твердження про пари ребер, що випадають, базової 2р_моделі на дереві ієрархії реберних функцій. Розроблено алгоритм побудови дерева ієрархії реберних функцій 2р-моделі будь-якої базової системи.

Майданюк И.В. Об одном алгоритме формирования реберных функций GL_моделей отказоустойчивых многопроцессорных систем / А.М. Романкевич, В.А. Романкевич, И.В. Майданюк // Радіоелектронні і комп'ютерні системи. - Харків : «ХАІ», 2010. - №3. - С. 56-61. Автором дисертації розроблено алгоритм нумерації множин індикаторних змінних. Запропонована модифікація відомого алгоритму формування 2р_моделі та його формалізація, прискорений алгоритм формування реберних функцій 2р_моделі.

Майданюк И.В. Об одном свойстве GL_модели с минимальным числом теряемых ребер / И.В. Майданюк, К.В. Морозов, Е.Р. Потапова, А.В. Шурига // Науковий вісник Чернівецького університету. Серія : Комп'ютерні системі та компоненти. - 2010. - Т.1, № 2. - С. 31-34. . Автором дисертації сформульована постановка задачі, а також доведено твердження про кількість функцій, що приймають нульове значення для першого з розглянутих випадків.

Майданюк І.В. Генератор рівноважних векторів для проведення статистичних експериментів з GL_моделями / В.О. Романкевич, І.В. Майданюк, А.П. Фесенюк, Д.С. Шкира // Науковий вісник Чернівецького університету. Серія : Комп'ютерні системі та компоненти. - 2010. - Т.1, № 2. - С. 28-30. Здобувачу належить спосіб формування двійкових векторів заданої ваги.

Майданюк И.В. О некоторых особенностях построения и преобразования GL_моделей / А.М. Романкевич, В.А. Романкевич, И.В. Майданюк, А.П. Фесенюк // Современные информационные и электронные технологии : труды 8-й междунар. науч._прак. конф., 21-25 мая 2007 г., Одеса. - 2007.- С. 172. Дисертантом досліджені особливості побудови GL-моделей та можливості їх перетворення.

Майданюк И.В. Об оценке числа внутренних рёбер при преобразовании GL_моделей / А.М. Романкевич, В.В. Иванов, И.А. Перерва, И.В. Майданюк // Інформаційно_керуючі системи на залізничному транспорті. - 2004.- №4,5. - С. 82. Здобувачем знайдено співвідношення що дозволяють оцінити складність GL_моделі небазової ВБС до проведення процедури модифікації.

Майданюк И.В. О граничных оценках числа дополнительных ребер GL_модели / В.А. Романкевич, К.М. Чернявськая, И.В. Майданюк // Інформаційно-керуючі системи на залізничному транспорті. - 2008. - №4(додаток). - С. 26-27. Автором дисертації досліджено деякі питання трансформації 2р-моделей базових систем до небазових.

Майданюк И.В. Об одной оценке числа дополнительных ребер GL-модели / В.В. Гроль, В.А. Романкевич, И.В. Майданюк // Інформаційно-керуючі системи на залізничному транспорті. - 2009. - №4 (додаток). - С. 15-16. Дисертантом отримано співвідношення для розрахунку мінімальної кількості додаткових ребер при перетворенні 2р_моделі. Розроблено алгоритм розфарбування V-графа.

Майданюк І.В. Про алгоритм формування розрахунку GL_моделі поведінки відмовостійких багатопроцесорних систем у потоці відмов / І.В Майданюк, К.Р. Потапова, С.В. Ладнюк // Інформаційно_керуючі системи на залізничному транспорті. - 2010.- №4 (додаток).- С. 7-8. Здобувачем запропоновано алгоритм прискореного розрахунку значень усіх реберних функцій 2р-моделі базової ВБС.

Майданюк І.В. Програмна реалізація прискореного алгоритму формування мінімізованої GL-моделі поведінки ВБС у потоці відмов / М.І. Хаітов, В.В Гроль, І.В. Майданюк // Прикладна математика та комп'ютинг : 2-га наук._практ. конф. магістрантів та аспірантів, Київ, 14-16 квіт. 2010 р. : зб. тез доп. - К.: Просвіта, 2010. - С. 377-380. Автором дисертації досліджені питання прискорення програмної реалізації алгоритму формування реберних функцій 2р_моделі.

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

...