Тема 6. Паралельні обчислювальні системи Лабораторна робота

КЛАСТЕРНА ОБЧИСЛЮВАЛЬНА СИСТЕМА

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

Основні завдання роботи

1. Отримати варіант домашнього завдання.

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

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

Основні теоретичні відомості

1. Архітектури ОС. Для паралельних обчислювальних систем (ОС) важливим є спосіб керування процесорами та способи їх взаємодії.

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

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

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

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

2. Топології ОС. В паралельних ОС важливим є спосіб з’єднань окремих процесорів між собою.

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

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

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

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

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

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

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

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

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

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

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

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

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

3.Мінімізація міжкластерних обмінів. Для кластерної ОС актуальним є мінімізація кластерних обмінів. Розв’язання цієї проблеми можна звести до пошуку мінімального розрізу графа задачі. Граф задачі G розрізається на підграфи (шматки) G_i, що відповідають підзадачам, їх обчислення виконують кластери. Для пошуку мінімального розрізу графа використовуємо один із послідовних алгоритмів [2]. Зробимо деякі визначення.

Граф G (без петель), у якого існує мінімум одна пара вершин, з’єднаних m ребрами називають мультиграфом, а максимальне m – мультичислом графа G.

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

Число ребер, що інцидентні вершині a_i називають локальною ступінню цієї вершини.

Кожному графу G відповідає квадратна матриця суміжності D, елементи якої визначаються так:

Критерії розрізу графа G є мінімальна кількість ребер між шматками G_i. Підграф у шматку має максимальну кількість ребер.

Деякі вершини графа G можуть попередньо бути закріпленими за шматками G_i. Тому маємо два варіанти пошуку мінімального розрізу графа:закріплені вершини є (Q≠Ø); закріплені вершини відсутні (Q=Ø).