Первая страница
Наша команда
Контакты
О нас

    Головна сторінка



Програмні засоби формування gl-моделей для ієрархічних систем

Скачати 455.91 Kb.

Програмні засоби формування gl-моделей для ієрархічних систем




Скачати 455.91 Kb.
Сторінка3/5
Дата конвертації02.05.2017
Розмір455.91 Kb.
1   2   3   4   5
багатокутника без будь-яких внутрішніх ребер.

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

Многоку́тник[К 1] (багатоку́тник, поліго́н) - геометрична фігура, замкнена ламана (сама, або разом із точками, що лежать усередині). Вершини цієї ламаної називають вершинами многокутника, а відрізки ламаної - сторонами многокутника.
Кори́стува́ч - той, хто користується чим-небудь - майном, землею, комп'ютером тощо.
Редагува́ння - це приведення об'єкта редагування у відповідність із чинними у певний час у конкретному суспільстві нормами, а також його творча оптимізація, метою яких є отримання заданого соціального ефекту.
Генерація - покоління, що представлене більш чи менш одноманітними особинами, які змінюються наступним поколінням, яке при диференціації життєвого циклу може істотно відрізнятися від попереднього. Наприклад: при чергуванні поколінь (гетерогонії, метагенезі) у тлі (Aphidoidea), галиць (Cecidomyiidae) та деяких інших комах.
Як сказано вище, структура графа GL-моделі ніяк не залежить від топології ВБС, яку вона відображає. Тому можна зробити висновок, що для побудови K(m, n) моделі достатньо ввести кратність відмов системи (m) та загальну кількість елементів системи (n) як вхідні дані.

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

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

Алгори́тм (латинізов. Algorithmi за араб. ім'ям узб. математика аль-Хорезмі) - набір інструкцій, які описують порядок дій виконавця, щоб досягти результату розв'язання задачі за скінченну кількість дій; система правил виконання дискретного процесу, яка досягає поставленої мети за скінченний час.
Симетрíя (від грец. συμμετρεῖν - міряти разом) - властивість об'єкта відтворювати себе при певних змінах, перетвореннях чи трансформаціях, які називаються операціями симетрії. Розрізняють симетрію тіл, симетрію властивостей і симетрію відношень.
Інакше кажучи, кількість елементів кожної підмножини будемо брати

n/2 ± 1.



Даний алгоритм має рекурсивний характер, тобто для побудови K(m, n) моделі необхідно буде створити інші Ki(mi, ni) моделі, що характеризуються іншими вхідними параметрами mi і ni, і в залежності від їх структури графу моделі формуватиметься граф шуканої K(m, n) моделі.
Рекурсія (лат. Recursion) - метод визначення класу чи об'єктів методів попереднім заданням одного чи декількох (звичайно простих) його базових випадків чи методів, а потім заданням на їхній основі правила побудови класу, який визначається.
Перш, ніж переходити безпосередньо до генерації реберних функцій графу K(m, n) моделі, варто звернути увагу на три особливі випадки, які можуть виникнути при розгляді всіх можливих варіантів розподілення непрацюючих елементів:

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


  2. m = n – це значить, що система стійка до n відмов, тобто до відмов будь-якого елементу системи. Відповідно до критерію обов’язкової адекватності моделі системі граф моделі має не втрачати зв’язність при виході з ладу будь-якої кількості будь-яких елементів системи, іншими словами, залишатися постійно зв’язним. Проте існує виключний випадок, коли граф системи має втратити зв’язність. Оскільки відмовостійкість систем побудована на концепції надлишковості та досягається за рахунок введення резервних елементів у систему та організації в систем здатності до реконфігурації (виключення елементу системи, що відмовив, та перерозподіл його функцій між працюючими модулями, що здатні їх виконувати), то при виході з ладу всіх елементів системи, включаючи резервні, система не зможе виконати реконфігурацію з метою повернення до робочого стану, оскільки не залишиться робочих елементів, на які можна було б перекласти функції елементів системи, що перейшли у стан відмови.
    Розпо́діл в еконо́міці - стадія відтворення сукупного суспільного продукту, що зв'язує виробництво і споживання; розподіл засобів виробництва і продуктів споживання між класами суспільства й робочої сили за сферами діяльності.
    Отже вихід за ладу всіх елементів системи - це виключний випадок, коли система K(n,n) перейде у стан відмови. Таким чином відповідно граф моделі такої системи має бути завжди зв’язним, крім випадку, коли всі елементи системи перейдуть у стан відмови, тобто для підтримання роботоздатності системи завжди має залишатися роботоздатним принаймні один з її компонентів. Тому граф системи K(n, n) просто зобразити у вигляді двох вершин, зв’язаних між собою одним ребром. У якості булевої функції єдиного ребра графа цієї моделі буде виступати диз’юнкція станів усіх елементів системи з вхідного вектору станів компонентів системи.

  3. m = 1 – такий випадок у деякому сенсі є протилежним до попереднього. У разі, коли m = 1, то така система являється стійкою лише до однієї відмови. Тобто система буде залишатися роботоздатною тільки в тому випадку, коли кількість компонентів, що перейшли у стан відмови, не перевищуватиме одного. Граф моделі системи K(1, n) матиме циклічну будову замкненого контуру, як і граф типової базової моделі K(m, n) системи. Кількість ребер і кількість вершин графа в такому випадку буде складати n. Значення кожної реберної функції буде дублювати стан відповідного компоненту з вектору станів елементів системи (fi = xi).
    Дублюва́ння, дубльо́ваний пере́клад або дубля́ж (від фр. double «подвійний») - вид перекладу фільмів, мультфільмів та серіалів, за якого відбувається повна заміна оригінального мовлення на іншу мову з метою транслювання фільму в країнах, у котрих не користуються мовою, якою говорять персонажі аудіовізуального твору.
    Таким чином при виході з ладу будь-якого одного компоненту відповідне ребро графа видаляється з подальшого аналізу його зв’язності і граф моделі втрачає циклічність, але залишається зв’язним. При подальшому переході будь-якого елементу системи у стан відмови граф стає незв’язним, а система відповідно стає нероботоздатною.

У загальному випадку, коли m < n, вхідний вектор станів елементів системи поділяється на два під вектора приблизно однакової довжини (±1 елемент) з кількістю елементів відповідно n1=[n/2] та n2=n-n1. Тоді модель K(m, n) будується на основі наступних реберних функцій:

Як видно, кожна функція K(m, n) моделі базуються на функціях моделей Ki(mi, ni). Реберні функції моделей Ki(mi, ni) знаходяться таким самим чином, як було описано вище. Але для кожної моделі Ki(mi, ni) буде свій вхідний вектор стану елементів системи, який в свою чергу являє собою певну частину загального вектору стану елементів системи K(m, n).
Вектор стану - сукупність характеристик, що однозначно визначають стан квантової системи.
Таким чином реберні функції моделі K(m, n) вираховуються за допомогою рекурсивної функції, умовами виходу з якою являються описані вище три крайніх випадки, а саме m > n, m = n, m = 1.

Вирази виду K1(m-i, n1) v K2(i, n2) вираховуються наступним чином. Позначимо реберні функції моделі K1(m-i, n1) як A1, A2, ..., Ap, а реберні функції K2(i, n2) як B1, B2, ..., Bq. Тоді весь вираз виду K1(m-i, n1) v K2(i, n2) буде представлятися у вигляді реберної функції f=A1A2..Ap v B1B2...Bq.

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

f6

f1

f5

f2

f4

f3

Рис. 1 Графо-логічна модель базової ВБС з 6 реберних функцій

Розглянемо приклад побудови моделі K(3,7).

Поділимо вхідний вектор станів елементів системи, що складається з семи елементів, на два підвектори, довжиною відповідно n1 = 4 і n2 = 3 елементи. Знайдемо реберні функції моделі K(3,7) :









Будуємо K1(3,4):







.

Будуємо K1(2,4):





.

K2(1,3) та K1(1,4) повернуть відповідно три та чотири функції, які будуть дублювати значення станів останніх трьох та перших чотирьох елементів.

Будуємо K2(2,3):





K2(3,3) дасть .

Таким чином граф K(3,7) моделі буде мати 5 ребер з наступними функціями:









.

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

6.5Поняття інверсної моделі

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

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

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

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




.

(2.1)

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

Таким чином, множина реберних функцій інверсної моделі може бути побудована так:








(2.2)

де






(2.3)

–множина вхідних змінних моделі.

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


6.5.1 Інверсна модель на базі кон’юнкцій та диз’юнкцій

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

Доведемо дане твердження. Розглянемо в загальному вигляді реберну функцію моделі . Вона може мати вигляд або:








(2.4)

або:






(2.5)










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






(2.6)

а для другого:






(2.7)

де , а – множина вхідних змінних моделі.

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


.

Як бачимо, завдяки перетворенням (2.6) і (2.7) ми позбавилися від необхідності виконання операцій логічної інверсії у виразах реберних функцій моделі. Фактично, ці перетворення полягали в заміні у виразі відповідної реберної функції моделі всіх кон’юнкцій диз’юнкціями і, навпаки, всіх диз’юнкцій кон’юнкціями.

Наведемо приклад реберних функцій моделі , побудованої таким способом на базі 2р-моделі:














.




Модель містить 6 ребер і на векторах із одиницями отримує рівно ребер, де:






(2.8)

6.6Нуль-моделі

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

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






(2.9)

де – множина вхідних змінних.

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








(2.10)

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

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











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

6.7Ієрархічні GL-моделі

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

1   2   3   4   5


Скачати 455.91 Kb.