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

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

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

Київський політехнічний інститут

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

Автореферат

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

Тема:

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

Фесенюк Андрій Петрович

Київ - 2011

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

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

Науковий керівник:

доктор технічних наук, професор Романкевич Олексій Михайлович, НТУУ «КПІ», професор кафедри спеціалізованих комп'ютерних систем.

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

доктор технічних наук, професор Широчин Валерій Павлович, Національний технічний університет України «Київський політехнічний інститут», професор кафедри обчислювальної техніки

доктор технічних наук, професор Куц Юрій Васильович, Національний авіаційний університет, завідувач кафедри інформаційно-вимірювальних систем

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

З дисертацією можна ознайомитись в бібліотеці Національного технічного університету України «Київський політехнічний інститут» (м. Київ, пр. Перемоги, 37).

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



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

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

Розрахунок надійності ВБС представляє собою окрему науково-технічну задачу, яка ускладнюється такими особливостями реальних ВБС, як значна кількість та різнотипність складових елементів, використання різних видів надлишковості, складна процедура реконфігурації, ієрархічна структура системи. Застосування до ВБС відомих методів розрахунку надійності комп'ютерних систем пов'язані з великою обчислювальною складністю або низьким рівнем точності отриманих результатів. Метод паралельної та послідовної редукції придатний лише для систем, що мають незмінну паралельну або послідовну структуру. Методи, пов'язані з перетворенням графа надійності, метод мінімальних шляхів і розрізів потребують побудови графа надійності, однак далеко не всі ВБС можуть бути представлені таким графом у зв'язку з неприйнятно великою кількістю вершин і ребер. Застосування прямого перебору, методу розкладання відносно особливого елемента та застосування ланцюгів Маркова потребують врахування всіх можливих станів ВБС, що, з огляду на велику кількість елементів у сучасних ВБС, обумовлює високу обчислювальну складність означених методів. Метод Рушді, метод Барлоу-Хейдмана та метод Белфора можуть бути застосовані лише для систем типу «k-out-of-n», однак реальні ВБС зазвичай характеризуються значно складнішою поведінкою при появі відмов. Точність відомих модифікацій методу статистичних експериментів не перевищує 1%-10%, і підвищення їх точності потребує значного збільшення кількості експериментів.

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

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

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

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

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

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

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

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

3. Розробка аналітичних співвідношень та статистичних оцінок для визначення різних складових похибки оцінки надійності ВБС.

4. Розробка алгоритму та відповідних співвідношень для визначення необхідної кількості статистичних експериментів і необхідної кількості розрядів представлення чисел в ЕОМ для забезпечення заданого рівня точності оцінки надійності ВБС.

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

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

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

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

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

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

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

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

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

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

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

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

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

Особистий внесок здобувача. Всі основні результати, що приводяться в дисертаційній роботі, отримані здобувачем самостійно.

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

Апробація результатів дисертації. Основні результати дисертації доповідались та обговорювались на науково-технічних семінарах кафедри спеціалізованих комп'ютерних систем НТУУ «КПІ» (2008, 2009, 2010 рр., м. Київ), 7-й міжнародній науково-практичній конференції «Современные информационные и электронные технологии» (2006 р., м. Одеса), міжнародній науково-практичній конференції «Комп'ютерні системи в автоматизації виробничих процесів» (2007 р., Хмельницький), 19-й, 22-й та 23-й міжнародній науково-практичній конференції «Перспективные системы управления на железнодорожном, промышленном и городском транспорте» (2006 р., 2009 р., 2010 р., м. Алушта), 12-му міжнародному молодіжному форумі “Радиоэлектроника и молодежь в XXI веке” (2008 р., м. Харків), 6-й і 7-й міжнародній науково-технічній конференції «Гарантоздатні (надійні та безпечні) системи, сервіси і технології» (2009 р., 2010 р., м. Кіровоград), 2-й науковій конференції «Прикладна математика та компютинг» (2010 р., м. Київ).

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

Структура та об'єм роботи. Дисертаційна робота складається зі вступу, чотирьох розділів, висновків та додатків. Загальний обсяг роботи складає 157 сторінок, містить 22 рисунка та список використаної літератури на 118 найменувань, 2 додатки.

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

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

У першому розділі дисертації проведено аналіз методів розрахунку показників надійності технічних систем. Як окремий клас технічних систем виділено ВБС, визначено характерні особливості ВБС: використання різних видів надлишковості, значна кількість складових елементів, наявність різнотипних елементів (неоднорідність), складна поведінка у потоці відмов, ієрархічна структура системи.

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

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

Імовірність безвідмовної роботи ВБС може бути записана як:

,(1)

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

Імовірність вектора стану системи , яка використовується у співвідношенні (1), дорівнює:

,

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

,

де _ імовірність безвідмовної роботи -го елемента, _ імовірність відмови -го елемента.

Імовірність безвідмовної роботи -го елемента системи в інтервалі часу від 0 до обчислюється на основі відомого співвідношення , де - інтенсивність відмов -го елемента системи. Величини табульовані, наприклад, інтенсивності відмов сучасних процесорів та блоків пам'яті складають 10^-7-10^-6 1/год, інтенсивності відмов сучасних шин - 10^-9-10^-8 1/год.

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

В розділі проведено аналіз можливості застосування відомих методів розрахунку показників надійності технічних систем до реальних ВБС (Табл. 1).

Таблиця 1

Порівняльний аналіз методів розрахунку надійності систем

Метод	Структура системи	Характеристика методу
Паралельна та послідовна редукція	Паралельні та послідовні структури	Часова складність: O(n).
Перебір усіх станів системи	Довільна	Часова складність: O(n•2n).
Розкладання відносно особливого елемента	Довільна	Часова складність: O(n•2n).
Застосування ланцюгів Маркова	Довільна	Потребує побудови системи диференціальних рівнянь, що враховує всі стани системи.
Перетворення графа надійності	Довільна	Потребує побудови і перетворення графа надійності.
Мінімальні шляхи та розрізи	Довільна	Потребує побудови графа надійності і пошуку всіх мінімальних шляхів та розрізів.
Метод Рушді	k-out-of-n	Часова складність: O(k(n-k)).
Метод Барлоу-Хейдмана	k-out-of-n	Часова складність: O(k(n-k)).
Метод Белфора	k-out-of-n	Часова складність: O(n(log2n)2).
Метод статистичних експериментів	Довільна	Часова складність визначається кількістю експериментів. Точність оцінки надійності 1%-10%.

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

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

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

,

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

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

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

,

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

,

_ кількість проведених статистичних експериментів,

_ вага двійкового вектора ,

_ константа для конкретної ВБС

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

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

,

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

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

,

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

В якості прикладу застосування запропонованих модифікацій в дисертації розглядається ВБС зі спільною шиною (рис. 1). ВБС містить 20 процесорів з інтенсивністю відмов 1ч5•10^-6 1/год, 20 оперативних запам'ятовуючих пристроїв (ОЗП) з інтенсивністю відмов 1ч5 • 10^-6 1/год. Імовірність відмови шини в даному прикладі вважається значно меншою, ніж імовірність відмови решти елементів. Проміжок робочого часу ВБС - 1000 год. ВБС спроектована таким чином, що може зберігати роботознатність при відмові будь-яких двох процесорів і певних трьох процесорів, а також при відмові будь-яких двох ОЗП, певних трьох ОЗП і певних чотирьох ОЗП.

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

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

Рис. 1. ВБС зі спільною шиною

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

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

,

,

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

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

Ймовірність безвідмовної роботи ієрархічної ВБС може бути записана у такому вигляді:

, (2)

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

;

_ імовірність того, що підсистеми знаходяться в станах, які описуються вектором , при умові, що спільні елементи знаходяться в станах, які описуються вектором

;(3)

_ умовні ймовірності стану підсистем, що дорівнюють

;

;

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

; (4)

_ імовірність вектора , яка дорівнює

;

- множина індексів елементів ВБС, які входять до -тої підсистеми і не входять до жодної іншої підсистеми; ; .

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

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



,

,

,

.

Для обчислення ймовірності безвідмовної роботи ієрархічної ВБС необхідно за допомогою (3) та (4) визначити умовні ймовірності та для кожного значення векторів та . В результаті отримуємо .

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

Рис. 2. Ієрархічна ВБС зі спільними елементами

програмний надійність відмовостійкий багатопроцесорний

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

Методична похибка розрахунку надійності ВБС пов'язана з використанням статистичних оцінок і має ймовірнісний характер. Для статистичних оцінок методична похибка може бути записана як

,

де - номер відповідної статистичної оцінки ().

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

,

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

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

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

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

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

,

де і - похибки вхідних даних.



Рис. 3. Аналітичні оцінки похибки розрахунку надійності

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

,

де - похибки округлення величин .

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

,

де та - похибки округлення величин та .

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

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

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

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

Для даної ВБС використання статистичних оцінок та дозволило зменшити похибку оцінки надійності на 12% та 10% відповідно у порівнянні з відомою статистичною оцінкою .

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

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

Рис. 4. Похибка оцінки надійності ВБС

У розділі дається коротке описання розробленого в процесі роботи над дисертацією програмного забезпечення, в якому реалізовано відомі та запропоновані в дисертації модифікації методу статистичних експериментів для розрахунку показників надійності ВБС та засоби для оцінки похибки розрахунку. Програмне забезпечення отримало назву SERC (Statistical Experiments for Reliability Calculation). При розробці програмного забезпечення використовувалась мова програмування C#. Обсяг програмного коду складає понад 5000 рядків.



Висновки

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

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

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

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

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

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

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

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



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

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

2. Фесенюк А.П. Оценка погрешности статистического расчета надежности ОМС, которым соответствуют иерархические GL-модели / А.М. Романкевич, В.В. Гроль, В.А. Романкевич, А.П. Фесенюк // Радіоелектронні і комп'ютерні системи. -- Харків: «ХАІ», 2010. -- №7. -- С. 142--146. - Дисертантом запропоновано ієрархічні GL-моделі та співвідношення для оцінки методичної похибки, трансформованої похибки і похибки округлення.

3. Фесенюк А.П. Про розрахунок надійності відмовостійких багатопроцесорних систем, підсистеми яких мають спільні процесори / В.О. Романкевич, А.П. Фесенюк // Радіоелектронні і комп'ютерні системи. - №3 2010. - С. 62-67. - Дисертантом запропоновано ієрархічні GL-моделі для ВБС, підсистем яких мають спільні процесори та співвідношення для оцінки похибки обчислень.

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

5. Фесенюк А.П. Об оценке погрешности расчета надежности отказоустойчивых многопроцессорных систем / В.В. Гроль, В.А. Романкевич, А.П. Фесенюк // Радіоелектронні і комп'ютерні системи. -- Харків: «ХАІ», 2009. -- №5. -- С. 56--59. - Дисертантом запропоновано співвідношення для розрахунку ймовірності безвідмовної роботи ВБС та співвідношення для оцінки похибки обчислень.

6. Фесенюк А.П. Оценка погрешности формирования управляемых псевдослучайных последовательностей / В.В. Гроль, В.А. Романкевич, Али Фаллаги, А.П. Фесенюк. // Вісник ХНУ, т.1 "Технічні науки".- Хмельницький 2007.- С.149-152 - Дисертантом запропоновано співвідношення для оцінки похибки формування результуючої послідовності, що враховують одночасний вплив і взаємну компенсацію різних чинників виникнення похибки.

7. Фесенюк А.П. Об оценке погрешности расчета надежности отказоустойчивых многопроцессорных систем с иерархической структурой / А.М. Романкевич, А.П. Фесенюк // Інформаційно-керуючі системи на залізничному транспорті. Тези доповідей.- 2009.- №4.- С. 37. - Дисертантом запропоновано методику розрахунку імовірності безвідмовної роботи ієрархічних ВБС.

8. Фесенюк А.П. О расчете надежности ОМС, подсистемы которых имеют общие процессоры, с помощью иерархических GL-моделей / В.А. Романкевич, А.П. Фесенюк, К.В. Морозов // Інформаційно-керуючі системи на залізничному транспорті. Тези доповідей. - 2010. -№4. - С.6. - Дисертантом запропоновано методику розрахунку ймовірності безвідмовної роботи ієрархічних ВБС, підсистеми яких можуть мати спільні процесори.

9. Фесенюк А.П. Один підхід до оцінки похибки обчислення надійності ВБС, що описуються ієрархічними GL-моделями / Є.В. Слюсар, В.О. Романкевич, А.П. Фесенюк // Друга наукова конференція «Прикладна математика та комою'тинг ПМК 2010»: зб. тез. доп. - К.: Просвіта. - 2010. - С.357-362. - Дисертантом запропоновано співвідношення для довірчої ймовірності відхилення результатів розрахунку надійності.

10. Фесенюк А. П. Оцінка складності алгоритму розрахунку надійності ВБС на основі виконання статистичних експериментів з GL-моделями / Д.О. Суліменко, А.П. Фесенюк, В.В. Гроль // Друга наукова конференція «Прикладна математика та компютинг ПМК 2010»: зб. тез. доп. - К.: Просвіта. - 2010. - С.367-371. - Дисертантом запропоновано співвідношення для визначення необхідної кількості статистичних експериментів.

11. Фесенюк А.П. О погрешности генератора псевдослучайных последовательностей, управляемого по двум параметрам / А.М. Романкевич, Фаллаги Али, А.В. Скрицкий, А.П. Фесенюк // Інформаційно-керуючі системи на залізничному транспорті. Тези доповідей.- 2006.- №4(додаток).- С. 11. - Дисертантом запропоновано методику оцінки похибки генерування вихідної послідовності з урахування трьох джерел виникнення похибки.

12. Фесенюк А.П. О формировании псевдослучайных последовательностей с управляемыми параметрами / А.М. Романкевич, Фаллаги Али, Р.И. Лупанова, А.П. Фесенюк // Сб. науч. тр. седьмой международной научно-практической конференции «Современная информатика и электронные технологии» СИЭТ 2006.- Одесса, 2006.- С. 152. - Дисертантом запропоновано методику розподілу двійкових векторів на групи, алгоритм вибору двійкових векторів для формування результуючої послідовності.

13. Фесенюк А.П. О точности вероятностных характеристик управляемого по двум параметрам ГПСП / А.П. Фесенюк, И.В. Майданюк // Збірник матеріалів 12-го міжнародного молодіжного форуму “Радиоэлектроника и молодежь в XXI веке”. - Харків: ХНУРЕ, 2008, Ч.2, С.13.

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



Анотації

Фесенюк Андрій Петрович. Методи і засоби підвищення точності оцінки надійності відмовостійких багатопроцесорних систем. - Рукопис

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

Дисертація присвячена проблемі підвищення точності оцінки надійності відмовостійких багатопроцесорних систем (ВБС) шляхом модифікації методу статистичних експериментів з урахуванням характерних особливостей ВБС.

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

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

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

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

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

Фесенюк Андрей Петрович. Методы и средства повышения точности оценки надежности отказоустойчивых многопроцессорных систем. - Рукопись

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

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

Проведен анализ известных методов расчета показателей надежности компьютерных систем. Установлено, что применение известных методов к ОМС связано со значительной вычислительной сложностью или низким уровнем точности полученных результатов. Для оценки показателей надежности ОМС со сложным поведением в потоке отказов эффективным оказывается только метод статистических экспериментов.

Предложены модификации метода статистических экспериментов, ориентированные на такие особенности ОМС как: значительное количество составных элементов, использование различных видов избыточности, сложная процедура реконфигурации, иерархическая структура системы. Предложенные модификации основываются на проведении статистических экспериментов с двоичными векторами состояния системы, которые имеют наибольшее влияние на величину вероятности безотказной работы ОМС, что позволяет повысить точность оценки надежности ОМС. В диссертации приведены примеры ОМС, для которых повышение точности составляет 10%-12%.

Первая модификация отличается проведением статистических экспериментов на бесповторной последовательности псевдослучайных двоичных векторов состояния системы с заданным весом (количеством единичных компонент).

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

В диссертации приведены соотношения, на основании которых могут быть определены минимальный и максимальный вес двоичных векторов состояния системы, для которых необходимо проводить статистические эксперименты.

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

Предложен метод анализа показателей надежности иерархических ОМС, подсистемы которых могут иметь общие элементы, который позволяет проводить статистические эксперименты независимо для каждой подсистемы, что дает возможность значительно сократить общее время расчета показателей надежности иерархических ОМС в сравнении с проведением статистических экспериментов для всех подсистем одновременно.

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

При анализе погрешности оценки вероятности безотказной работы ОМС учтены следующие составляющие погрешности: погрешность, связанная с методом (методическая погрешность); погрешность в исходных данных (трансформированная погрешность); погрешность, связанная с ограниченным числом двоичных разрядов, используемых для представления чисел в ЭВМ (погрешность округления).

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

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

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

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

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



Feseniuk Andrii Petrovich. Methods and tools for improving the accuracy of reliability estimation of fault-tolerant multiprocessors systems. - Manuscript

Thesis for the PhD degree, specialty 05.13.05 - Computer systems and components. - National Technical University of Ukraine "Kyiv Polytechnic Institute", Kyiv, 2011.

The dissertation is devoted to improve the accuracy of estimating the reliability of fault-tolerant multiprocessor systems (FTMS) by modifying the method of statistical experiments, taking into account the characteristics of the FTMS.

A modifications of the method of statistical experiments has been proposed that focused on such features of FTMS as: a significant number of elements, different types of redundancy, a complex procedure of reconfiguration, the hierarchical structure of the system.

A method for calculating the reliability of hierarchical FTMS with elements in common has been proposed. The method allows to conduct statistical experiments independently for each subsystem that makes it possible to significantly reduce the total time of calculating the reliability of hierarchical FTMS.

The analytical and statistical estimators for the various type of the error of calculation the reliability of FTMS has been proposed. That allows to define the total error of calculating the reliability of the FTMS.

Conditions are formulated that allows for the specified FTMS to determine the modification of the method of statistical experiments having the smallest error before the statistical experiments executing.

Keywords: fault-tolerant multiprocessor systems, reliability, a method of statistical experiments, statistical estimators, the error of estimation, controllable generators of binary vectors.

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

...