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

G₃={ a₄, a₈, a₉, a₁₂}.

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

1. Шматок G₁

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

G₁={ a₁, …}.

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

та обчислюємо їх відносні ваги

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.4. Будуємо множину Гa₁UГa₆ UГa₂ = { a₂, a₄, a₆, a₇, a₁₂}U U { a₁, a₇} U { a₁, a₃, a₇}={ a₄, a₇, a₃, a₁₂}

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

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

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

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

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

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

G₁={ a₁, a₆ , a₂, a₇}.

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

G₂={ a₁₀,….}.

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

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

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

G₁ G₂ G₃

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

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

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

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

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

4.2. Структури кластерних ос

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

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

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

Обладнання, прилади та матеріали

В ЛР розв’язується задача синтезу кластера та кластерної ОС. Для виконання роботи використовується клас ПК.

Заходи безпеки при виконанні ЛР

Заходи безпеки відповідають вимогам, яким необхідно дотримуватись при роботі в комп’ютерному класі.

Порядок виконання роботи

1. В лабораторному зошиті наводяться мета, завдання та синтез кластерної ОС.

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

3. В ЛР використовується ПП «Розрізання графу» для контролю відповідності мінімального розрізу графа задачі отриманого у домашньому завданні

4. В ЛР визначаються архітектури та топології паралельних ОС у відповідності до класифікації Фліна, способи використання пам’яті.

5. Розробка структур кластера та кластерної ОС складається із послідовності кроків:

• На основі загального графа задачі G та матриці сумісності D формується граф G' та матриця D' варіанта завдання ЛР;

• визначаються шматки G₁, G₂, … та будується мінімальний розріз графа G'. При чому враховуються наявність або відсутність заборонених вершин;

• з урахуванням топології кластера, числа та розмірів шматків G₁, G₂, … розробляється структура кластера.

6. Варіанти завдань представлені в табл. 1. Вони містять кількісні параметри, що необхідні для побудови кластерної ОС.

Таблиця 1

Варіанти завдань

№ варіанта	P	M	N	Q	Топологія кластера	Топологія ОС
1	9	3	3,4,2	Ø	Решітка	Комутатор
2	10	3	4,3,3	1,9	Загальна пам'ять (ЗП)	Мережа
3	11	3	3,3,5	10	Решітка	Решітка
4	12	4	3,3,4,2	5,12	Повнозв'язана	Комутатор
5	10	3	3,3,4	Ø	Комутатор ЗП	Мережа
6	11	3	5,3,3	10,11	ЗП	Решітка
7	12	4	3,3,3,3	9,7,11	Решітка	Мережа
8	12	4	5,3,3,1	12,10	Повнозв'язана	Комутатор
9	10	3	3,3,3	Ø	ЗП	Решітка
10	10	3	2,5,3	6,10	Комутатор ЛП	Мережа
11	11	3	4,3,4	Ø	ЗП	Решітка
12	12	3	4,4,4	6,9,11	Повнозв'язана	Мережа
13	12	4	4,3,3,2	2,4,7,6	Комутатор ЗП	Комутатор

Вихідними даними для ЛР є: матриця суміжності D', граф задачі G', порядок матриці Р; число шматків (підграфів) М; число вершин в шматках N; закріплені (заборонені) вершини Q.

На рис. 11 та Рис. 12 показані загальні граф G та відповідна йому матриця суміжності D. Вершини графа a_i є підзадачі (потоки), а ребра взаємозв’язки між ними. Порядок матриці D дорівнює 12. Для отримання графа G' та матриці D' необхідно в графі G викреслити вершини a_i … та ребра зв’язків отримаємо граф задачі, що відповідає варіанту ЛР. Тотожність матриці D' графу G' досягається видаленням відповідних стовпців та рядків. При цьому корегуються також елементи матриці D', стовпці δ(a_i) та m(a_i).

Рис. 11. Граф задачі G.

			1		2		3		4		5		6		7		8		9		10		11		12					δ(аі)				m(аі)
		1				1				1				2		3										1			8				3
		2		1				1								1													3				1
		3				1						2										1							4				2
		4		1														1		1						1			4				1
		5						2														3		1					6				3
D	=	6		2												1													3				2
		7		3		1								1						1				1					7				3
		8								1										1						3			5				3
		9								1						1		1				1				1			5				1
		10						1				3								1				2					7				3
		11										1				1						2							4				2
		12		1						1								3		1									6				3

Рис. 12. Матриця суміжності D, локальна ступінь - δ(а_і), максимальне число кратних дуг - m(а_і)

Оформлення результатів експерименту

Результатом ЛР є структура кластера та кластерної ОС.

Обробка експериментальних даних

Наводяться та порівнюються результати отримані в домашньому завданні та ПП «Розрізання графу».

Аналіз одержаних результатів

Формулюються висновки по результатам виконання ЛР.

Запитання для самоперевірки

1. Як формується граф задачі в лабораторній роботі?

2. Як формується матриця суміжності?

3. Основні кроки послідовного алгоритму розрізання графа.

4. Типи архітектур паралельних ОС.

5. Способи організації структур кластерів та кластер них ОС.

Джерела

[3, 5].

СПИСОК Літератури

1. Угрюмов Е. П. Цифровая схемотехника / Е. П. Угрюмов – СПб. : БХВ – Петербург, 2001. – 528 с.

2. Микропроцессорные системы: Учебное пособие для вузов / Е. А. Александров, Р. И. Грушвицкий, М. С. Куприенов и др; Под. общ. ред. Пузанкова. – СПб. : Политехника, 2002. – 935 с.

3. Цилькер Б. Я. Организация ЭВМ и систем : учебник / Б. Я. Цилькер, С. А. Орлов. – СПб. : Питер, 2006. – 668 с.

4. Єфимець В. М. ЦЕОМ. Інтегральні мікросхеми серії КР1533. : Практичний порадник / В. М. Єфимець, ін. – К. : НАУ, 2003. – 36 с.

5. Ортега Д. Введение в параллельные и векторные методы решения линейных систем : пер. с англ. / Д. Ортега. – М. : МИР, 1991. – 367 с.