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

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

УДК 519.718

Автореферат

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

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

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

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

Бахтарі Хедаятоллах

Київ 2008

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

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

Науковий керівник: доктор технічних наук, професор Романкевич Олексій Михайлович,НТУУ “КПІ”, професор кафедри СКС

Офіційні опоненти: доктор технічних наук, професор Дрозд Олександр Валентинович, Одеський національний політехнічний університет, професор кафедри комп'ютерних інтелектуальних систем та мереж кандидат технічних наук Селігей Олександр Минович, Кременчуцький державний політехнічний університет, доцент кафедри комп'ютерних та інформаційних систем

Захист відбудеться “08” грудня 2008 р. о 16:00 на засіданні спеціалізованої вченої ради Д 26.002.02 у НТУУ “КПІ” (м. Київ, пр. Перемоги, 37, корп. 18, ауд. 306)

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

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

Автореферат розісланий “ 06 ” листопада 2008 р.

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

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

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

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

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

Зв'язок роботи з науковими програмами, планами, темами. Результати дисертаційної роботи отримані в рамках двох напрямків наукових досліджень кафедри спеціалізованих комп'ютерних систем НТУУ «Київський політехнічний інститут»: «Проектування і тестування цифрових схем і систем на всіх етапах циклу їхнього існування», а також «Моделювання поведінки відмовостійких багатопроцесорних систем у потоці відмов». Дослідження в цих напрямках проводяться кафедрою протягом останніх 35 і 15 років відповідно. Зокрема, у рамках тем НДР №0107U002168 «Методи та засоби оцінки надійності реконфігуровних відмовостійких багатопроцесорних систем» та НДР №0104U000686 «Методи та засоби побудови тестопридатних цифрових об'єктів», одним з підрозділів якої є підвищення ефективності засобів генерації псевдовипадкових іспитових послідовностей двійкових векторів.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В роботі [1] - доведення твердження про можливість склеювання ребер разом зі своїми функціями не лише в канонічній моделі; в роботі [4] - перевірка правильності основного положення, виконання експериментів з моделями K(3,n); в роботах [3,9] - дослідження питань, пов'язаних з проблемами перетворення базових моделей в небазові; в роботі [2] - доведення положення про відсутність ПРЦ в новій моделі, експериментальна перевірка справедливості основних положень; в роботі [6,10] - аналіз і відмінності k-out-of-n та K(m,n) систем; в роботі [7] - особливості моделювання K(3,n); в роботі [8] - алгоритм пошуку ПРЦ в моделях K(3,n); в роботі [5] проаналізовано результати моделювання структури генератора та одержані основні його імовірнісні характеристики.

Апробація результатів дисертації. Основні результати роботи доповідались і обговорювались на науково-технічних семінарах кафедри спеціалізованих комп'ютерних систем НТУУ «КПІ» (жовтень 2006, жовтень 2007, вересень 2008), на 19-й (вересень 2006) і 20-й (вересень 2007) міжнародних школах-семінарах «Перспективні системи управління на залізничному, промисловому і міському транспорті» (ХарГАЖТ - УЗ - НАНУ), 7-й міжнародний науково-практичній конференції «Сучасні інформаційні і електронні технології» (травень 2006, ОНПУ), на міжнародній науковій конференції, посвяченій пам'яті проф. А. М. Богомолова (2007, Саратов), на міжнародних конференціях EWDTW-2006 (Сочі) і EWDTW-2007 (Ереван), а також на 3-й Міжнародній науково-технічній конференції «Гарантоздатні (надійні і безпечні) системи, сервіси і технології» (2008, Кіровоград).

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

Структура і об'єм дисертації. Дисертаційна робота включає вступ, чотири глави, висновок та список літератури. Загальний об'єм роботи складає 145 сторінок друкованого тексту, 31 рисунок, 26 таблиць та список використаної літератури на 87 найменувань.

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

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

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

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

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

Графо-логічна модель (GL-модель) поведінки відмовостійкої багатопроцесорної системи в потоці відмов являє собою неорієнтований граф G, кожному ребру якого відповідає булева функція. Аргументами реберних функцій є індикаторні змінні x_i (i = 1 , … , n), що дорівнюють 1 (i-й елемент системи працездатний) або 0 (i-й елемент системи вийшов з ладу). Ребро видаляється з графу певної GL-моделі, якщо відповідна йому реберна функція набуває значення 0. Зв'язність графа моделює працездатність ВБС.

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

. (1)

Недолік методу: функції F₁ і F₂ є функціями канонічного представлення моделі. Крім того, залишився незрозумілим порядок виконання цієї операції «склеювання». відмовостійкий багатопроцесорний система поведінка

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

Далі в главі аналізуються можливості отримання оптимальних GL-моделей циклічного типу по заданому критерію, у тому числі по критерію складності. Для цього пропонується, не здійснюючи заміни реберних функцій, виконувати склеювання згідно із запропонованим вдосконаленням. Далі пропонується скласти 2 таблиці, рядки яких - це всі отримані по ходу мінімізації функції. Стовпці першої таблиці позначаються двійковими векторами, що містять m нулів, а другої - (m+1) нулів. Якщо функція даного рядка набуде значення 0 на наборі (двійковому векторі), що позначає стовпець, то відповідний елемент таблиці відмічається. Далі слід здійснити вибір (подібно до того, як це було запропоновано Квайном у його відомому методі мінімізації булевих функцій) такої сукупності реберних функцій, яка в першій таблиці має не більш однієї відмітки в кожному із стовпців, а в другій -- не менше двох, і при цьому відповідає заданому критерію. Це і будуть реберні функції GL-моделі циклічного типу, яку потрібно побудувати. Такий вибір повністю відповідає вимогам формування GL-моделей в загальному випадку. Як приклад, в дисертації приведено декілька таблиць (для випадків К(3,7) і К(3,8)), що ілюструють можливості застосування методу для пошуку базових моделей по критеріях мінімального числа ребер моделі і мінімального числа ребер, що втрачаються при появі вектора стану ВБС, що має 4 відмови. У дисертації відмічається (і наводиться приклад), що оптимізація моделей по різних критеріях може вимагати різних канонічних виразів.

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

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

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

2. Для кожної зі складених канонічних моделей виконати всі можливі склеювання.

3. Для кожного з розбиттів скласти та відмітити, як вказано вище, по 2 таблиці: стовпці -- всі вектори стану ВБС з m і m+1 нульовими компонентами, рядки -- всі реберні функції, включаючи канонічні та отримані в результаті склеювання.

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

5. Оптимальна модель -- та, яка зі всіх вибраних в більшій мірі відповідає заданому критерію.

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

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

K^?(m₁, n₁)K^?(m₂, n₂), (2)

де m₁+m₂=m і n₁+n₂=n, а K^? -- сукупність ребер зі своїми функціями відповідної канонічної моделі. При цьому, якщо модель K^?(m₁,n₁) містить r₁ ребер, а модель K^?(m₂, n₂) -- r₂ ребер, то в канонічній моделі K(m,n) виразу (2) відповідатиме r=r₁•r₂ ребер.

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

Множина ребер (зі своїми функціями), що відповідають виразу (2), завжди може бути зведена до одного ребра зі своєю функцією.

Алгоритм заснований на вдосконаленому методі мінімізації, і його головна перевага -- відсутність перебору.

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

Відомі методи побудови GL-моделей небазових ВБС ґрунтуються на ідеї перетворення базових моделей. Один з методів перетворення - введення додаткових ребер, які забезпечують побудову моделей для ВБС, стійких до відмов підвищеної кратності. Додаткове ребро в циклічному графові повинне запобігти втраті зв'язності графом GL-моделі при появі того чи іншого вектора стану w_i. Називатимемо це блокуванням вектора w_i. Позначимо множину всіх векторів станів ВБС, що містять m+1 нульову компоненту, через W.

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

Нехай є 3 вектори стану ВБС, що належать множині W. Якщо при появі першого вектора стану з графа моделі видаляються ребра i та j, при появі другого вектора стану - ребра j та k, при появі третього вектора стану - ребра i та k, то ребра i, j, k складають своєрідний цикл, який і називатимемо попарним реберним циклом (ПРЦ). У таких випадках для блокування одного додаткового ребра недостатньо. Пропонується робити попередній аналіз моделі і заданої множини векторів W_i W, які потрібно блокувати при трансформації моделі, на предмет появи ПРЦ. З метою зменшення перебору при пошуку ПРЦ пропонується ввести деяку ієрархічну впорядкованість реберних функцій. Верхнім (першим) рівнем ієрархії вважатимемо ребра з функціями, залежними від n змінних. До другого рівня віднесемо ті ребра, функції яких залежать від або (це залежить від парності n) змінних і так далі. Отримаємо деяку досить однозначну ієрархію реберних функцій.

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

ѓ=ц₁(2,n_i1) \/ ц₂ (1,n_i2) (3)

де ц₁ і ц₂ двійкові функції, що дорівнюють 0 при появі вектора стану ВБС, в якому нульові компоненти розміщені таким чином: 2 компоненти в підмножині n_i1 і одна в підмножині n_i2.

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

ѓ₁₁=ц₁(2,б₁₁) \/ ц₂(1,б₁₂) ,

то для функцій наступного рівня ієрархії

ѓ₁₁₁=ш₁(2,б₁₁₁) \/ ш₂(1,б₁₁₂)

ѓ₁₁₂=о₁(1,б₁₁₁) \/ о₂(2,б₁₁₂).

Тут б_i - відповідні підмножини змінних.

₀ = {x₁, x₂, … , x₃₁}

₁ = {x₁, x₂, … , x₁₅}

₂ = {x₁₆, x₁₇, … , x₃₁}

₁₁ = {x₁, x₂, … , x₇}

₁₂ = {x₈, x₉, … , x₁₅}

₂₁ = {x₁₆, x₁₇, … , x₂₃}

₂₂ = {x₂₄, x₂₅, … , x₃₁}

₁₁₁ = {x₁, x₂, x₃}

₁₂₁ = {x₈, x₉, x₁₀, x₁₁}

₁₁₂ = {x₄, x₅, x₆, x₇}

₁₂₂ = {x₁₂, x₁₃, x₁₄, x₁₅}

₂₁₁ = {x₁₆, x₁₇, x₁₈, x₁₉}

₂₁₂ = {x₂₀, x₂₁, x₂₂, x₂₃}

₂₂₁ = {x₂₄, x₂₅, x₂₆, x₂₇}

₂₂₂ = {x₂₈, x₂₉, x₃₀, x₃₁}

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

Твердження 3.2.

2 ребра GL-моделі базової ВБС К(3,n) можуть одночасно випадати при появі вектора стану w_iW тоді і лише тоді, коли вони відповідають двом вершинам дерева ієрархії, які

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

б) або розташовані на одному рівні ієрархії і мають загальну суміжну вершину на дереві ієрархії.

Це твердження слугує основою для доведення твердження про умови існування ПРЦ.

Твердження 3.3.

Для трійки ребер GL-моделі і відповідних їм трьом вершинам а,b,c дерева ієрархії ПРЦ можливий тоді і лише тоді, коли

1) одна з вершин дерева (припустимо вершина “a”) лежить ближче двох інших до кореня дерева,

2.1) або існує ланцюжок на дереві, на якому лежать всі 3 вершини,

2.2)або вершини b і с є суміжними до вершини d, і вершини а і d лежать на одній гілці.

Наведемо алгоритм, що дозволяє знаходити все 3-реберні ПРЦ, використовуючи отримані вище результати. Нехай є ВБС K(3,n) і її GL-модель, побудована згідно алгоритму побудови моделі, що втрачає мінімум ребер. Нехай є множина W_j векторів стану ВБС, що містять по 4 нульових компоненти. Визначимо всі ПРЦ, які виникають при перетворенні моделі.

Алгоритм.

1. Побудувати дерево ієрархії ребер моделі.

2. Визначити множину S ребер та множину P пар ребер, які випадають при появі векторів стану ВБС із заданої множини W_j векторів стану ВБС.

3. Виділити в множині S множину Q трійок ребер, які задовольняють умовам 1 та 2.1 або 1 та 2.2 твердження 3.3.

4. Для кожного елемента q_і множини Q виділити підмножину R_і елементів p_і множини P, для яких виконується .

5. Виділити в кожній множині R_і підмножини T_i, які задовольняють умовам твердження 3.1. Поява відповідних трійок векторів стану ВБС, які викликають зникнення ребер множини T_i, призводить до утворення ПРЦ в моделі.

В кінці глави пропонується нова модель, характерною особливістю якої є її ієрархічне представлення у вигляді кількох 4-реберних графів. Для випадку m=3 модель типу D будується згідно з наступними положеннями:

Положення 1:

D-модель будується на базі 4-реберних графів наступного вигляду

де функції f_i1 та f_i2 - реберні функції GL-моделі, отриманої після мінімізації, які залежать від тих самих змінних; a_i1 та a_i2 - реберні функції нової моделі, які віддзеркалюють стан GL-моделей К(3, n_i) певного етапу формування.

Положення 2:

Функції a_i1 та a_i2 утворюються наступним чином:

функція a_i1=

a_i2=

n_i1 - це підмножина множини змінних функції f_i1, у яких на i-ому етапі формування моделі припускається наявність 2-х відмов.

n_i2 - це підмножина множини змінних функції f_i2, у яких на i-ому етапі формування моделі припускається наявність 2-х відмов.

Моделі K(3, n_i1) та K(3, n_i2) представлені у відповідності з положенням 1.

Положення 3:

Для випадку 3? n_i ?5 модель D формується іншим чином:

n_i=3 => на місці функції виду «a_i» в 4-реберном графі записується безпосередньо функція .

n_i=4 => для формування функції «a_i» будується наступний граф з реберними функціями (рис. 3):

n_i=5 => для формування функції «a_i» будується наступний граф.Зрозуміло, що йдеться про графи останнього рівня ієрархії моделі D.

Положення 4:

Втрата працездатності ВБС відображається втратою зв`язності у будь-якому з графів моделі D.

Серед особливостей токаї моделі найбільш важливою є те, що вона не містить ПРЦ.

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

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

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

Т_м=max( ),

причому у загальному випадку припускається, що кожна підсистема моделюється на відмовах певної (відмінної від інших підсистем) кратності відмов i, j, причому i ? j, i, j=1,2,…,m (ki ? kj), тоді умова формування всіх

Т_м= наборів на інтервалі T_r с заданою ймовірністю P_g можна записати у вигляді [1-(1-Р_н)^Тr]^Тм ?Р_g,. Тоді величина інтервалу T_r визначається наступним чином:

T_r ? .

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

Висновки

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

1. Вдосконалений метод мінімізації базових GL-моделей, який дозволяє здійснювати більш глибоку мінімізацію моделі.

2. Вдосконалений та адаптований для GL-моделей метод скорочення перебору при виборі оптимальних рішень. Запропоновано використовувати 2 таблиці, стовпці яких охоплюють всі двійкові вектори з m та m+1 нульовими компонентами. Метод дозволяє знаходити оптимальну по будь-якому з відомих критеріїв модель.

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

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

5. Запропонована нова GL-модель ієрархічного типу та метод її побудови для випадку m=3. Характерними особливостями моделі є наступні: вона складається з декількох простих графів, значно спрощує алгоритм перетворення базової моделі в небазову шляхом проведення додаткових ребер в графі моделі та не містить ПРЦ, проте має більшу кількість ребер.

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

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

1. Романкевич В.А., Потапова Е.Р., Бахтари Хедаятоллах, Назаренко В.В. GL-модель поведения отказоустойчивых многопроцессорных систем с минимальным числом теряемых рёбер // Вісник НТУУ “КПІ”.- Інформатика, управління та ОТ.-2006.- №45.-С.93-100 (Автором дисертації виконано доведення твердження про можливість склеювання ребер моделі з власними функціями не тільки у канонічному вигляді).

2. Романкевич В.А., Потапова Е.Р., Бахтари Хедаятоллах. Иерархическая модель поведения ОМС в потоке отказов // Электронное моделирование.- 2008.- т.30, №4.- с.75-82 (Дисертантом доведено положення про відсутність ПРЦ у новій моделі, виконана експериментальна перевірка).

3. Романкевич В.А., Кононова А.А., Бахтари Хедаятоллах. Условия существования попарных рёберных циклов в GL-моделях K(3,n) // Вісник НТУУ “КПІ”.- Інформатика, управління та ОТ.-2007.- №46.-С.54-61 (Автором сформульовано та доведено умови існування ПРЦ у моделях K(3,n)).

4. А.М. Романкевич, В.А. Романкевич, Бахтари Хедаятоллах. Об одном способе оптимизации моделей поведения отказоустойчивых многопроцессорных систем // Радіоелектронні і комп`ютерні системи.- 2008.- №7.- с.49-52 (Автором дисертації виконано перевірку вірності головного положення та проведено необхідні експерименти з моделями K(3,n)).

5. Гроль В.В., Хедаятоллах Бахтари, Фаллаги Али. Структурный метод формирования последовательностей двоичных псевдослучайных (n,k)-векторов при моделировании ОМС // Теоретические проблемы информатики и ее приложения: Сб.науч.тр., Под ред. проф. А.А.Сытника.-Изд-во Сарат. ун-та.- 2006.- Вып. 7.-С.36-43 (Дисертантом проаналізовано результати моделювання структури генератора та одержані основні його ймовірносні характеристики).

6. Romankevych V., Potapova K., Hedayatollah Bakhtari. K-out-of-n and K(m,n) systems and their models // Proceedings of IEEE East-West Design & Test Workshop,- Russia, Sochi, September 2006,- p.189 (Дисертантом виконано порівняльний аналіз k-out-of-n и K(m,n) систем).

7. В.А. Романкевич, Е.Р. Потапова, Хедаятоллах Бахтари, А.А. Кононова. О моделировании поведения отказоустойчивых многопроцессорных систем в потоке отказов // Труды 7-й МНПК СИЭТ-2006 Одесса.- 2006.- С. 154 (Автором дисертації досліджені особливості моделей K(3,n)).

8. Горожин А.Д., Кононова А.А., Новак Е.И., Бахтари Хедаятоллах. Алгоритмы поиска попарных реберных циклов в небазовых GL-моделях // Інформаційно-керуючі системи на залізничному транспорті. Тези доповідей.- 2006.- №4(додаток).- С. 7 (Дисертантом розроблено алгоритм пошуку ПРЦ у моделях K(3,n)).

9. А.М. Романкевич, В.А. Романкевич, Бахтари Хедаятоллах. Дерево иерархии ребер GL-модели // Компьютерные науки и информационные технологии: Тезисы докладов Междунар. научной конференции, посвящённой памяти проф. А.М.Богомолова.- Саратов: Изд-во Сарат.ун-та, 2007.- С.98-99 (Дисертант сформулював вимоги до вектора стану ВБС у випадках втрати моделлю пари ребер).

10. Romankevich V., Potapova K., Hedayatollah Bakhtari. The some properties of model's of k-out-of-n system's behavior in the stream of faults // Proceedings of IEEE East-West Design & Test Symposium.- Armenia, Yerevan, September 2007.- p.763 (Дисертантом виконано дослідження особливостей K(m,n) моделей у потоці відмов).

Анотації

Бахтарі Хедаятоллах. Методи та засоби підвищення ефективності розрахунку надійності відмовостійких багатопроцесорних систем. - Рукопис.

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

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

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

Для випадку m=3 будується спеціальне дерево, яке дозволяє сформулювати умови існування попарних реберних циклів (ПРЦ), що ускладнюють перетворення моделей.

На базі цих умов запропоновано алгоритм пошуку ПРЦ, що виникають при перетворенні моделей.

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

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

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

Бахтари Хедаятоллах. Методы и средства повышения эффективности расчёта надёжности отказоустойчивых многопроцессорных систем. - Рукопись.

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

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

GL-модель представляет собой неориентированный граф G, каждому ребру которого соответствует булева функция. Аргументами рёберных функций являются индикаторные переменные x_i (i = 1 , … , n), равные 1 (i-й элемент системы работоспособен) или 0 (i-й элемент системы вышел из строя). Ребро удаляется из графа определённой GL-модели, если соответствующая ему рёберная функция принимает значение 0. Связность графа моделирует работоспособность ОМС.

Исследуется возможность упрощения GL-модели как один из способов повышения точности расчета надежности ОМС, поскольку, чем проще модель, тем больше статистических экспериментов с ней можно выполнить в единицу времени. Усовершенствуется известный метод минимизации базовых моделей циклического типа, что позволяет проводить более глубокую минимизацию. С целью оптимизации моделей исследуется возможность использования идеи, предложенной Квайном для минимизации булевых функций. Предлагается строить 2 таблицы, строки которых - реберные функции, а столбцы - все векторы состояния ОМС, содержащие m и m+1 нулевую компоненту. Это дает возможность уменьшить перебор при выборе оптимальной по заданному критерию модели ОМС.

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

Исследуются задачи трансформации базовых моделей в небазовые. Особенностью базовых ОМС K(m,n) является потеря работоспособности при появлении числа отказов, превышающего определенную кратность - величину m. Небазовые могут продолжать функционировать при появлении некоторых r>m отказов и оказаться неисправными при появлении некоторых r?m неисправных процессоров. Одним из путей построения адекватных моделей является проведение в циклическом графе базовой GL-модели внутренних ребер. Рассматривается возможность осуществления предварительного анализа моделей на предмет появления попарных реберных циклов (ПРЦ), которые усложняют процесс преобразования моделей и увеличивают число дополнительных ребер. Вводится понятие определенной упорядоченности реберных функций, предлагается дерево их иерархии, на основании которого формулируются условия существования ПРЦ. Это позволяет резко уменьшить перебор при их выявлении, предлагается соответствующий алгоритм. Предлагается новая GL-модель, одной из особенностей которой является отсутствие ПРЦ. Модель состоит из нескольких 4-реберных графов, что значительно упрощает ее анализ и преобразование.

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

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

Bakhtari Hedayatollah. Methods and means of efficiency increasing of reliability calculation for fault-tolerant multiprocessor systems. - Manuscript.

Thesis for the PhD degree by the specialty 05.13.05 - computer systems and components. - National Technical University of Ukraine “Kiev Polytechnic Institute”.- Kiev, 2008.

Dissertation is devoted to the subsequent evolution of the theoretical principal of development and use of GL-models of the fault-tolerant multiprocessor systems (FMS) behavior in the stream of faults for the calculation of these systems' reliability by implementation of statistical experiments with the models. The problems of models' simplification are probed: than the model has less complexity, the more statistical experiments it is possible to execute with it and the more correct will be a reliability calculation. Perfection of minimization method and also surplus attenuation during the search of optimal on one or another model criterion are offered. On criterion of minimum of ribs being lost by the model when vector of a state which has m+1 zero components appears, FMS that is proof to m faults, an algorithm which gives an optimal model without any surplus is developed. Simplification possibilities of further model transformations using their previous analysis are examined. The concept of model ribs functions order is introduced. For the case when m = 3 the special tree that allows to lay down conditions existence of pair ribs cycles (PRC) which complicate model transformation is built. On the base of these terms the algorithm of searching of PRC which arise up at model transformation is offered. A new GL-model that is built on the base of some 4-ribs graphs is offered. There are not PRC in this model and it considerably simplifies transformation of models.

Considered issues of development and research of the specialized structural facilities of support of procedures for behavior design of FMS in the stream of different (set) multiplicity faults. It is showed that tacking into account possible dependence of FMC subsystems frequently results in significant rise in productivity of both specialized structural means of the faults' attributes and (as a result) of algorithms for modeling FTMS' behavior procedures implementation in fault flow as whole.

Keywords: failsafe multiprocessor systems, graphs, Boolean functions, controllable generator of pseudorandom vectors, reliability.

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