4. Вершини графа g, що залишились складають в шматок

G₂={ a_4, a_8, a_9, a₁₂}.

Приклад 2. Необхідно знайти мінімальний розріз графа G (рис. 1) при умовах як і в прикладі 1, але Q = ø.

1. Шматок G₁

Першою вершиною G_1­ вибираємо вершину з найбільшим значенням m(a_і) (рис.2), наприклад, a_і.

G₁={ a_{1, ….}}.

2. Будуємо множинуГa₁={ a₂, a₄, a₆, a_7, a_12,}

та обчислюємо відносні ваги вершин

h (a₂)= δ (a₂) - m(a₁)=3-0=3,

h (a₄)= δ (a₄) - m(a₁)=4-1=3,

h (a₆)= δ (a₆) - m(a₁)=3-2=1,

h (a₇)= δ (a₇) - m(a₁)=7-3=4,

h (a₁₂)= δ (a₁₂) - m(a₁)=6-1=5.

Вибираємо вершину h (a_i)_min= h (a₆)=1

G₁={ a_1, a₆ ,….}.

2. Будуємо множину Гa₁UГa₆ ={ a₂, a₄, a_7, a₁₂ }U{ a₇}={ a_2, a_4, a_7, a₁₂} та обчислюємо відносні ваги вершин

h (a₂)= δ (a₂) - m(a₁) - m(a₆) =3-1-0=2,

h (a₄)= δ (a₄) - - m(a₁) - m(a₆) =4-1-0=3,

h a₇)= δ (a₇) - m(a₁) - m(a₆) =7-3-1=3,

h (a₁₂)= δ (a₁₂) - - m(a₁) - m(a₆) =6-1-0=5.

Вибираємо вершину h (a₂)=2

G₁={ a_1, a₆ , a₂….}.

2. Будуємо множину Гa₁UГa₆ UГa₂ = { a₂, a₄, a₆, a_7, a₁₂}U{ a_1, a₇} U { a₁, a_3, a₇}={ a_4, a_7, a_3, a₁₂}

та обчислюємо відносні ваги вершин

h (a₄)= δ (a₄) - m(a₁) - m(a₆) - m(a₂) =4-1-0-0=3,

h (a₇)= δ (a₇) - m(a₁) - m(a₆) - m(a₂) =7-3-1-1=2,

h (a₃)= δ (a₃) - m(a₁) - m(a₆) - m(a₂) =4-0-0-1=3,

м(a₁₂)= δ (a₁₂) - m(a₁) - m(a₆) - m(a₂) =6-1-0=5.

Вибираємо вершину з H(a_i)_min= H(a₇)=2 це остання вершина шматка G₁

G₁={ a_1, a₆ , a_2, a₇….}.

Першою вершиною шматка G₂ вибираємо вершину за максимальним m(a_i) та δ(a_i). Це буде вершина a_10.

G₂={ a_10,….}.

Подальші кроки визначення шматків G_2, G₃ будуть аналогічними.

8. Кластерні ос.

Загальна структура кластерної ОС представлена на Рис. 11.

Рис. 11. Кластерна ОС

ОС складається з трьох кластерів G₁ – G₃, які об’єднані через комунікаційне середовище. Кожний кластер об’єднує чотири процесора П₁-П₄, які ототожнюються з підзадачами (потоками) a_i. Наприклад для G₁ це будуть (а₁, а₂, а₆, а₇).

8.1. Структури кластерів.

Взаємодії процесорів П₁-П₄ кластера G₁ можуть забезпечувати такі топології: повноз’вязана; комутатор ЗП (загальна пам'ять); решітка (лінійка); загальна пам'ять; комутатор ЛП (локальна пам'ять). Структури кластерів представлені на Рис. 12.

Рис. 12. Структури кластерів: а - повнозв’язана; б – комутатор ЗП; в – решітка (лінійка); г – ЗП; д – комутатор ЛП.

8.2. Структури кластерних ОС

Взаємозв’язки кластерів в кластерній ОС (рис. 13.) можуть бути подібними до зв’язків процесорів у кластері: повнозв’язними; через комутатор; решітка; швидкодіюча мережа (загальна шина).

В ОС (рис. 13.а.) взаємодію кластерів забезпечує швидка діюча мережа (F. Ethernet, Myrinet та ін.) На (рис. 13.б.) об’єднання кластерів виконує комутатор. ОС на (рис. 13.в.) реалізує топологію решітка. В усіх ОС сервер забезпечує інтерфейс користувачів з системою через інтерфейсні адаптери А.

Рис. 13. Структури кластерних ОС: а – мережна; б- комутатор; в – решітка.

Додаток А

Структура та зміст КР

«Кластерна обчислювальна система»

Завдання

№ варіанту	P	М	N	Q	Топологія кластера	Топологія ОС
*	10	3	3, 3, 4	6, 7, 10	ЗП	Решітка

1. Архітектури і топології паралельних ОС. Наводяться та аналізуються у відповідності до класифікації. Фліна архітектури ОС, а також можливі топології.

2. Розглядаються варіанти використання загальної пам’яті (ЗП) та локальних пам’ятей.

3. Розробка структури кластерної ОС.

   1. Визначення матриці D, δ(a_i), m (a_i) на основі загального графа задачі G (рис. 1) з урахуванням варіанту КР формується граф задачі KPG та відповідна йому матриця суміжності D, локальні ступіні вершин δ(a_i) та максимальні числа кратних дуг m (a_i).

   2. Визначення мінімального розрізу графа задачі G. Відповідно до завдання КР визначаються шматки G_1, G₂ та будується мінімальний розріз графа. При цьому враховується наявність або відсутність заборонених (закріплених) вершин.

   3. Структура кластера. З урахуванням топології кластера, розмірів шматків G_1, G_{2, …} представляється (розробляється) структура кластера.

   4. Крастерна ОС. Топологія ОС базується на варіанті КР. Розробляється структура кластерної ОС.

Література

1. Ортега Дж. Введение в параллельные и векторные методы решения линейных систем :Пер. с англ. –Мир, 1991. -367 с.

2. Мелехов А.Н., Берштейн Л.С., Курейчик В.М Применение графов для проектирования дискретных устройств.–М.: Наука, 1974. – 256 с..

3. Ефимец В.Н., Нагорный Л.Я. Проектирование управляющих автоматов на программируемых логических матрицах. – К.: КИИГА, 1981. – 33 с.

4. Кулик М.С. , Полухін А.В. Положення про дипломні роботи (проекти) випускників Національного авіаційного університету.- К.: НАУ-друк, 2 011. – 72с.

Додаток Б

Оформлення КР

1. Контрольна робота «Кластерна обчислювальна система» оформляється у вигляді пояснювальної записки (ПЗ) на аркушах А4 і має структуру: титульний аркуш; завдання; зміст; текст ПЗ; література..

2. Оформлення ПЗ виконується відповідно до вимог [4].

3. Титульний аркуш має формат :

ІЗДН Кафедра комп’ютерних систем та мереж Контрольна робота з дисципліни «……» на тему : “ Кластерна обчислювальна система “ Виконав Прийняв Оцінка Київ – 201