Лабораторна робота

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

Мета роботи: закріплення теоретичних знань по синтезу структур кластер них обчислювальних систем (ОС).

Підготовка до роботи.

1. Вивчити теоретичну частину роботи.

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

Домашнє завдання

1. Викласти ціль роботи та основні теоретичні положення.

2. Визначити мінімальний розмір графа задачі G.

3. Відповідно до завдання підготовити структури кластерів кластерної ОС.

4. Підготувати дані до прикладної програми (ПП) «Розрізання графа».

5. Підготовити письмові відповіді на контрольні питання.

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

1. Представити викладачу результати домашнього завдання та отримати дозвіл на виконання роботи.

2. Завантажити дані для ПП «Розрізання графа» та отримати результати розрахунку.

3. Порівняти результати машинного та домашнього обчислення. У випадку не співпадання результатів обчислення, зробити аналіз, виправити помилку.

Зміст звіту.

1. Пункти 1-5 «Домашнього завдання».

2. Протокол результатів розрізу графа.

3. Висновки.

Контрольні запитання.

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

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

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

4. Типи архітектури паралельних ОС та способи організації пам’яті.

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

6. Паралелізм та його вимір.

Контрольна робота

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

Мета роботи: розробка структури паралельної обчислювальної системи (ОС) з кластерною архітектурою.

В контрольній роботі необхідно визначити та проаналізувати:

• архітектури і топології паралельних ОС;

• взаємодії процесорів в ОС з локальною пам’яттю;

• паралелізм та його виміри ;

• розробити структуру кластерної ОС з мінімальними передачами данних між кластерами.

Варіанти завдань наведені у табл 1. Вихідними даними для контрольної роботи (КР) є:

D – матриця суміжності (граф G) (рис 1); P – порядок матриці D;

M – число шматків (підграфів); N – число вершин в шматках;

Q – закріплені (заборонені) вершини; топологія кластера ,топологія ОС.

В стовпчику Q числа є значення індексів в назві вершини (9 и→а₉ і т.д.) Знаком Ø позначається відсутність вершин. ЗП – загальна пам'ять, ЛП – локальна пам'ять.

Таблиця 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	Комутатор ЗП	Комутатор

На рис. 1 зображений граф G задачі. Вершини графа а_і є під задачі (потоки), а ребра – взаємозв’язки між ними. Графу G відповідає квадратна матриця суміжності D (рис. 2), порядок якої визначається числом вершин в графі G. В нашому випадку, максимальний порядок матриці D дорівнює 12. Викреслюючи в графі G вершини а_і та ребра, отримаємо граф задачі, що відповідає варіанту КР. Тотожніть матриці D графу G досягається шляхом видалення відповідних стовпчиків та рядків. При цьому корегуються також елементи матриці D, стовпчики δ(а_і) та m(а_і).

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

Матриця суміжності D представлена на рис. 2.

			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

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

Методичні вказівки

1. Архітектури ос

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

По способу керування процесорами ОС бувають типів SIMD (один потік команд, багато потоків даних) та MIMD (багато потоків команд, багато потоків даних) (рис. 3).

В SIMD ОС (рис. 3.а.) процесори П_і знаходяться під керуванням HOST-процесора (контролера) і в кожний момент часу виконують одну команду або знаходяться в стані очікування.

В MIMD ОС (рис 3.б.) процесори функціонують під керуванням власних програм. В таких ОС виникає проблема синхронізації виконуваних процесорами завдань у відповідному порядку та з правильними даними.

Рис. 3. Архітектури ОС: а – SIMD, б – MIMD

2. Організація пам’яті

Важливою проблемою паралельних ОС є організація пам’яті. Вона може бути загальною або локальною (рис. 4)

Рис. 4. Пам'ять ОС: а – ОС із ЗП; б – ОС із ЛП

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

У випадку ОС із локальною пам’яттю (рис. 4,б.) кожний процесор має доступ тільки до власної пам'яті. Обмін між процесорами виконується шляхом передачі відповідних повідомлень.

3. Топології ос

В паралельних ОС важливим є спосіб з’єднань окремих процесорів між собою. Це актуально для ОС як з локальною так і з загальною пам’яттю. Наведемо (розглянемо) деякі топології ОС.

3.1. Повнозв’язана ОС. Процесори П_i мають безпосередні зв’язки між собою (рис. 5).

Рис. 5. Повнозв’язана ОС

0. 3.2. ОС з комутатором. Доступ процесорів до модулів пам'яті забезпечують перемикачі, що входять до складу комутатора (рис. 6.).

Рис. 6. ОС з комутатором

0. 3.3. ОС із загальною шиною. Усі процесори з’єднані за допомогою швидкісної загальної шини (ЗШ) (рис. 7.)

Рис. 7. ОС із ЗШ

0. 3.4.Решітка процесорів. В цій топології кожен процесор з’єднується з декількома сусідніми (рис. 8).

Рис. 8. Решітка процесорів: а – лінійний масив; б – площинний масив (решітка)

3.5. Гіперкуб. Зображений на рис. 9 тривимірний куб, у вершинах якого розміщені процесори П_і, а ребра виконують функцію локальних зв’язків між ними.

Рис. 9. Гіперкуб

3.6. Кластери. Кластерна ОС (рис. 10) складається із «р» кластерів (пучків процесорів), які об’єднані шиною. Кластер, в свою чергу, об’єднує «m» процесорів. З’єднання в кластері називаються локальними, а між кластерами – глобальними. Функціонування ОС базується на поєднанні цих двох типів взаємозв’язків. Для кожного кластера домінуючими обмінами є в межах відповідного кластера. Обміни між кластерами виникають значно рідше.

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

Кластерна ОС може бути реалізована різними способами. В межах кластера зв’язки процесорів можна організувати за допомогою шини (швидкісна мережа), решітки, гіперкуба і т. д. Названі схеми можуть бути використані і для з’єднання кластерів.