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

ЗМІСТ.

• ВСТУП
• 1. ЗАГАЛЬНІ ВІДОМОСТІ ПРО ОБЧИСЛЮВАЛЬНИЙ КЛАСТЕР
• 1.1 Способи завантаження обчислювальної потужності кластера
• 1.2 Модель передачі повідомлень — message passing
• 1.3 Модель обчислювального кластера
• 2. МОДЕЛЬ КЕРУЮЧОЇ СИСТЕМИ ОБЧИСЛЮВАЛЬНОГО КЛАСТЕРА
• 2.1 Класична архітектура керуючої системи
• 2.2 Структура керуючої системи обчислювального кластера
• 3. АЛГОРИТМИ ПЛАНУВАННЯ
• 3.1 Схема роботи алгоритмів планування
• 3.2 Досліджувані алгоритми планування завдань на обчислювальному кластері.
• 4. СИМУЛЯТОР ОБЧИСЛЮВАЛЬНОГО КЛАСТЕРУ ТА ЙОГО КЕРУЮЧОЇ СИСТЕМИ
• 4.1 Симулятор TopSimity
• 4.2 Обчислювальне завантаження кластеру
• 4.3 Структура програми паралельної задачі
• 4.4 Комунікаційні патерни
• 4.4.1 Практичне застосування патерну All-to-all
• 4.5 Симуляція роботи кластеру та його керуючої системи
• 5. КЛАСТЕР ЦЕНТРУ СУПЕРКОМП’ЮТЕРНИХ ОБЧИСЛЕНЬ
• 5.1 Центр суперкомп’ютерних обчислень
• 5.2 Стратегічні проекти НТУУ «КПІ»
• 5.3 Поточна конфігурація кластеру НТУУ «КПІ»
• 6. РЕЗУЛЬТАТИ ЕКСПЕРИМЕНТАЛЬНОГО ДОСЛІДЖЕННЯ.
• ВИСНОВОК
• СПИСОК ВИКОРИСТАНОЇ ЛІТЕРАТУРИ

ВСТУП

обчислювальний кластер алгоритм планування

У даному проекті проводяться результати дослідження запропонованих та існуючих алгоритмів планування завдань для обчислювального кластера з урахуванням мережі і багатопроцесорності вузлів. Дослідження проводилося за допомогою розробленого симулятора обчислювального кластеру та його керуючої системи, в основу якої лягла запропонована модель обчислювальної системи, модель керуючої системи, імітаційна схема роботи кластера, а також модель завантаження системи потоком задач.

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

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

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

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

1 ЗАГАЛЬНІ ВІДОМОСТІ ПРО ОБЧИСЛЮВАЛЬНИЙ КЛАСТЕР.

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

Найпоширенішим є використання однорідних кластерів, тобто таких, де всі вузли абсолютно однакові по своїй архітектурі й продуктивності.

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

Користувачі мають домашні каталоги на сервері доступу — шлюзі (цей сервер забезпечує зв’язок кластера із зовнішнім світом через корпоративну локальну обчислювальну мережу або Інтернет), безпосередній доступ користувачів на керуючий вузол виключається, а доступ на обчислювальні вузли кластера можливий (наприклад, для ручного керування компіляцією завдання).

Обчислювальний кластер, як правило, працює під керуванням однієї з різновидів ОС Unix — багатокористувацької багатозадачної мережевої операційної системи.

1.1 Способи завантаження обчислювальної потужності кластера.

Існує декілька способів завантаження обчислювальної потужності кластера:

— Запускання багатьох однопроцесорних завдань. Це може бути сприятливим варіантом, якщо потрібно провести багато незалежних обчислювальних експериментів з різними вхідними даними, причому час проведення кожного окремого розрахунку не має значення, а всі дані розміщуються в об'ємі пам’яті, доступному одному процесу.

— Запускання готових паралельних програм. Для деяких завдань доступні безкоштовні або комерційні паралельні програми, які при необхідності можна використовувати на кластері.

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

— Створювати власні паралельні програми. Це найбільш трудомісткий, але й найбільш універсальний спосіб. Існує кілька варіантів такої роботи, зокрема, вкладати паралельні конструкції в готові паралельні програми або створювати з «нуля» паралельну програму.

1.2 Модель передачі повідомлень — message passing.

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

Тобто процес, який повинен одержати дані, викликає операцію receive (прийняти повідомлення), і вказує, від якого саме процесу він повинен одержати дані, а процес, який повинен передати дані іншому, викликає операцію send (послати повідомлення) і вказує, якому саме процесу потрібно передати ці дані.

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

Як правило, MPI-програми побудовані по моделі SPMD (Single Process Multiple Data або Single Program Multiple Data — одна програма працює в різних процесах зі своїми даними), тобто для всіх процесів є тільки один код програми, а різні процеси зберігають різні дані й виконують свої дії залежно від порядкового номера процесу.

1.3 Модель обчислювального кластера.

Довільна кластерна обчислювальна система може бути описана за допомогою орієнтованого графа:

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

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

Значення і є статичними параметрамиго вузла обчислювального кластерa. До числа його динамічних характеристик відносяться величини, які відповідно визначають завантаженість його обчислювальних ядер, обсяг доступної оперативної і дискової пам’яті в момент часу [0;+?).

Нехай — множина обчислювальних ядер вузла , — множина обчислювальних ядер всіх вузлів кластера, тоді позначимо в якості номер задачі, виконаної на ядрі в момент часу. Якщо ж ядро в момент часу було вільним, то = 0. Значення динамічних параметрівго вузла в момент часу можуть бути обчислені за такими формулами:

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

Структура типового обчислювального SMP-вузла зображена на рисунку 1.1.

Рис. 1.1 — Структура SMP-вузла Обчислювальні ядра можуть відноситися як до окремих процесорів (по одному ядру на кожного), так і до декількох багатоядерних процесорів. З метою спрощення моделі вони розглядаються, як єдина множина. Процеси, що виконуються на обчислювальних ядрах, можуть безпосередньо зчитувати та записувати інформацію в оперативну та дискову пам’ять даного вузла, взаємодіючи з ними через системну шину або комутатор. При необхідності передачі повідомлення іншому обчислювальному вузлу залучається мережева підсистема, яка здійснює розбиття повідомлення на пакети і передачу їх по високопродуктивній комунікаційній мережі. Мережева підсистема кожного вузла також містить комутатор, який виконує функції маршрутизації власних і транзитних пакетів.

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

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

2. МОДЕЛЬ КЕРУЮЧОЇ СИСТЕМИ ОБЧИСЛЮВАЛЬНОГО КЛАСТЕРА.

2.1 Класична архітектура керуючої системи.

У рамках цього проекту розглядається класична архітектура керуючої системи обчислювального кластера (КСОК), що припускає наявність наступних основних компонент (див. рисунок 2.1):

1. Черга представляє собою накопичувач завдань користувачів, відправлених на запуск.

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

3. Менеджер ресурсів збирає інформацію про стан обчислювальних вузлів (їх доступність, завантаженість та ін.).

4. Агенти на обчислювальних вузлах виконують три основні функції: запуск завдань на обчислювальних ядрах, контроль їх виконання та збір інформації про доступність ресурсів.

2.2 Структура керуючої системи обчислювального кластера.

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

Рис. 2.1 — Структура керуючої системи обчислювального кластеру Планувальник в процесі своєї роботи складає розклад запуску паралельних завдань з черги відповідно до закладеного в нього онлайнового алгоритму планування. У його структурі зазвичай виділяють: алгоритм вибору наступного завдання з черги і метод його призначення на вільні ядра, підходящі по ресурсах обчислювальних вузлів.

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

3. АЛГОРИТМИ ПЛАНУВАННЯ.

3.1 Схема роботи алгоритмів планування.

На рисунку 3.1 представлена узагальнена схема роботи всіх розглянутих у цьому проекті алгоритмів планування.

При кожному запуску циклу планування алгоритм вибору наступного завдання з черги на основі поточного розкладу Schedule і на основі черги очікуваних завдань Q динамічно формує на момент часу t список вікон планування W. Потім виконується цикл, на кожній ітерації якого по деякому принципу з Q вибирається чергове завдання J, для якого на основі списку вікон планування WL складається список відповідних вікон WL?, який потім передається методу призначення. У процесі своєї роботи останній формує для J вікно запуску R, на основі якого оновлюються WL і Schedule. Підсумком роботи алгоритму є оновлений розклад Schedule і список обраних завдань U.

Підсумковий розклад після запуску всіх завдань з черги Q може бути представлений у вигляді безлічі впорядкованих пар Schedule = {(), де — вікно запуску роботи .

Рис. 3.1 — Узагальнена блок-схема роботи алгоритму планування.

3.2 Досліджувані алгоритми планування завдань на обчислювальному кластері.

У рамках проведеного дослідження були розглянуті алгоритми планування завдань, що представляють собою поєднання алгоритму вибору наступного завдання з черги Most Processors First Served Scan (MPFS Scan) або алгоритм зворотнього заповнення Backfill з методом його призначення на обчислювальні ядра, які враховують топологію обчислювальної системи для топології товстого дерева — Sorting Nodes by Performance (SNP), Fat Tree Sorting Commutators by Performance (FTSCP), Fat Tree Sorting Commutators by Cores (FTSC); для топології двовимірного тору — модифіковані варіанти алгоритмів Minimizing message-passing Contention 1×1 (MC1x1) і Minimizing message-passing Contention 1×1 Incremental (MC1x1+Inc); для топології зірки — Sorting Nodes by Performance (SNP) i Sorting Nodes by Speed (SNS).

Також розглядалися поєднання алгоритмів MPFS Scan і Backfill з методами призначення, які не приймають топологію до уваги: First Fit (FF), Best Fit (BF), Fastest Node Fist (FNF) i Random First (RF).

В процесі дослідження були запропоновані власні алгоритми планування, що представляють собою поєднання алгоритму MPFS Scan або Backfill з розробленими методами призначення Summed Distance Minimization (SDM) i Maximum Distance Minimization (MDM). Дані методи враховують топологію обчислювальної системи, мережеву конкуренцію між одночасно виконуваними завданнями і багатопроцесорністю обчислювальних вузлів.

Нехай методу призначення передається вибране із черги завдання, потрібне для свого виконання обчислювальних ядер. Далі опишемо принцип роботи алгоритмів SDM і MDM.

Метод призначення SDM для кожного допустимого вікна планування WWL? перебирає всі мережеві пристрої d кластера (комутатори і вузли) і визначає для кожного з них найблищих обчислювальних ядер вікна W, які підходять по конфігурації для задачі. Ці обчислювальні ядра формують можливе вікно запуску задачі. Для призначення в якості результату R вибирається вікно з мінімальною сумарною попарною відстанню, якщо таких декілька, то обирається вікно з більшою сумарною продуктивністю обчислювальних ядер.

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

Метод призначення MDM для кожного допустимого вікна планування WWL? перебирає всі мережеві пристрої d кластера і для кожного з них запускає алгоритм пошуку в ширину. В процесі його роботи формується множина досягнутих обчислювальних ядер вузлів вікна W, які підходять по конфігурації для задачі, до тих пір, поки не буде отримано ядер. При цьому серед ядер, які знаходяться на однаковій відстані від початкового мережевого пристрою в першу чергу вибираються ті, які мають більшу швидкість. Результатом роботи пошуку в ширину є сформоване можливе вікно запуску. Для призначення завданню, як результат R вибирається вікно з мінімальною максимальною відстанню від першого початкового мережевого пристрою d.

Даний метод є аналогом алгоритму MC1x1 для довільних топологій. За рахунок компактного розміщення процесів паралельної задачі алгоритм MDM намагається мінімізувати максимальну відстань від вибраного центрального мережевого пристрою до призначених задачі обчислювальних ядер.

4. СИМУЛЯТОР ОБЧИСЛЮВАЛЬНОГО КЛАСТЕРУ ТА ЙОГО КЕРУЮЧОЇ СИСТЕМИ.

4.1 Симулятор TopSimity.

Для дослідження ефективності роботи запропоновано симулятор обчислювального кластеру та його керуючої системи — TopSimity. Він був реалізованим на мові С++ з використанням стандартної бібліотеки шаблонів STL.

Імітаційна схема роботи симулятора представлена на рисунку 4.1. Джерело генерує потік паралельних завдань, що відправляються користувачам в чергу Q керуючого вузла. Канал S являє собою планувальник, який відповідно до закладеного в нього алгоритму здійснює вилучення задач з Q і призначення їх на вільні обчислювальні ядра, які підходять по конфігурації вузлів.

Рис. 4.1 — Імітаційна схема керуючої системи обчислювального кластера.

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

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

В якості алгоритму роботи симулятора використовується алгоритм моделювання по принципу особливих станів (подій).

Рис. 4.2 — Імітаційна схема вузла, комутатора і двосторонній мережевий зв’язок.

4.2 Обчислювальне завантаження кластеру.

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

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

де — безліч номерів вузлів, ядра яких були віддані завданню.

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

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

4.3 Структура програми паралельної задачі.

Структура програми кожної паралельної задачі може бути представлена наступною SPMD-моделлю:

Process u:

for i=1 to do.

{.

Communication (i, j);

Computation (i, j);

}.

Виконання кожного процесу паралельної задачі являє собою чергування фаз комунікації і обчислень.

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

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

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

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

Розглянемо ще яким чином можна знайти реальний час виконання задачі .

Нехай функція дозволяє визначити для кожного процесу завдання. Для простоти припустимо, що кожен процес витрачає однаковий час на виконання обчислювальної частини кожної ітерації SPMD-моделі задачі. Тоді час виконання обчислювальної фази Computation (i, j) процесом можна обчислити за формулою:

Нехай — час виконання комунікаційної фази Communication (i, j) процесом задачі, тоді реальний час виконання даної задачі може бути обчислено за формулою:

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

4.4 Комунікаційні патерни.

Типовими комунікаційними патернами, що зустрічаються в науковій літературі [5−7], вважаються:

1. Random. Кожен процес пересилає повідомлення першому і другому випадково вибраному процесу.

2. Pairs. Процеси випадково розбиваються на пари і обмінюються повідомленнями між собою.

3. Ring. Процеси об'єднуються в кільце. Кожен процес посилає повідомлення наступному і приймає дані від попереднього.

4. One-to-all. Один випадково обраний процес розсилає повідомлення всім іншим.

5. All-to-all. Кожен процес відправляє повідомлення процесам, які залишилися.

У рамках проведеного дослідження застосовували комунікаційний патерн All-to-all, тому що він забезпечує максимальне завантаження обчислювальної мережі і мережеву конкуренцію.

4.4.1 Практичне застосування патерну All-to-all.

Розглянемо детальніше практичне застосування патерну All-to-all (передає дані від усіх всім процесам).

Список функцій MPI_All-to-all: Int MPI_Alltoall (void * sendbuf, int sendcount, MPI_Datatype sendtype, void * recvbuf, int recvcount, MPI_Datatype recvtype, MPI_Comm comm);

Параметрами MPI_All-to-all є:

sendbuf — [in] початковий адрес буфера передачі (за вибором);

sendcount — [in] кількість елементів, що посилаються для кожного процесу (цілі);

sendtype — [in] тип даних буфера відправки елементів;

recvbuf — [out] адреса буфера прийому (на вибір);

recvcount — [in] кількість елементів, отриманих від будь-якого процесу (цілi);

recvtype — [in] тип даних буфера елементів;

comm. — [in] комунікатор.

Зауваження. MPI_All-to-all є розширенням MPI_ALLGATHER, на випадок, коли кожен процес посилає різні дані для кожного з приймачів. J-ий блок спрямований від процесу i отриманий процесом j і знаходиться в i-ому блоці recvbuf.

У типі підпису пов’язаному з sendcount, sendtype, процес повинен бути рівним типу підпису, пов’язаному з recvcount, recvtype в будь-якому іншому процесі. Це означає, що обсяг переданих даних повинен дорівнювати сумі отриманих даних, попарно між кожною парою процесів. Як правило, тип карти може бути різним.

Всі аргументи на всіх процесах є багатозначними. Аргумент comm повинен мати однакові значення на всіх процесах.

Якщо comm є інтеркомунікатором, то результатом є кожен процес у групі А, який відправляє повідомлення для кожного процесу в групі В, і навпаки. J-ий буфер відправки процесу в групі А повинен бути сумісним з i-им буфером прийому процесу j в групі В, і навпаки.

Поради користувачам патерну MPI_All-to-all. Коли all-to-all виконано, то кількість даних відправлень з процесів у групі А до процесів у групі В може не бути рівним числу відправлень у зворотньому напрямку. Зокрема, може бути односпрямований зв’язок, вказавши sendcount = 0 в зворотньому напрямку.

Зв’язок і переривання безпеки. Ця процедура є поточно-орієнтованою. Це означає, що ця процедура може безпечно використовуватися декількома потоками. Як правило, це пов’язано з використанням процедури розподілу пам’яті, такої як Malloc або інших не-MPICH виконання процедур.

Усі процедури в MPI Fortran (за винятком MPI_Wtime і MPI_Wtick) мають додаткові IERR-аргументи в кінці списку аргументів.

Всі MPI об'єкти (наприклад, MPI_Datatype, MPI_Comm) мають тип INTEGER в Fortran.

Помилки, які можуть виникнути при роботі з MPI_All-to-all. Всі процедури MPI (за винятком MPI_Wtime і MPI_Wtick) повертають значення помилки. Перед поверненням значення, потік MPI-помилок називається процесором (оброблювачем). За умовчанням цей процесор помилок перериває роботу MPI. Оброблювач помилок може бути зміненим з MPI_Comm_set_errhandler (для комунікаторів), MPI_File_set_errhandler (для файлів), та MPI_Win_set_errhandler (RMA для Windows). MPI-1 процедури MPI_Errhandler_set можуть бути використані, але його використання не рекомендується. Варто звернути увагу на те, що MPI не гарантує, що програма MPI може продовжувати роботу після помилки, однак MPI реалізація буде намагатися продовжувати роботу по мірі можливості.

Найпоширенішими помилками є:

MPI_ERR_COMM — невірний комунікатор (навіть не допускаються в MPI_Comm_rank).

MPI_ERR_COUNT — хибна кількість аргументів. Кількість аргументів повинна бути невід'ємною, нулі часто дійсні.

MPI_ERR_TYPE — невірний тип даних аргументу. Може бути незавершений MPI_Datatype.

MPI_ERR_BUFFER — невірний показник на буфер. Зазвичай порожній буфер.

Наступний приклад коду ілюструє MPI_All-to-all:

#include «mpi.h» #include <stdlib.h>#include <stdio.h>#include <string.h>#include <errno.h>#ifndef EXIT_SUCCESS#define EXIT_SUCCESS 0#define EXIT_FAILURE 1#endifint main (int argc, char *argv[]){ int rank, size; int chunk = 128; int i; int *sb; int *rb; int status, gstatus; MPI_Init (&argc,&argv); MPI_Comm_rank (MPI_COMM_WORLD,&rank); MPI_Comm_size (MPI_COMM_WORLD,&size); for (i=1; i < argc; ++i) { if (argv[i][0] ≠ '-') continue; switch (argv[i][1]) { case 'm': chunk = atoi (argv[++i]); break; default: fprintf (stderr, «Nevuznachenuj argument %sn», argv[i]);fflush (stderr); MPI_Abort (MPI_COMM_WORLD, EXIT_FAILURE); } } sb = (int *)malloc (size*chunk*sizeof (int)); if (!sb) { perror («Nemogluvo vudilutu buffer peredachi»);fflush (stderr); MPI_Abort (MPI_COMM_WORLD, EXIT_FAILURE); } rb = (int *)malloc (size*chunk*sizeof (int)); if (!rb) { perror («can't allocate recv buffer»);fflush (stderr); free (sb); MPI_Abort (MPI_COMM_WORLD, EXIT_FAILURE); } for (i=0; i < size*chunk; ++i) { sb[i] = rank + 1; rb[i] = 0; } status = MPI_Alltoall (sb, chunk, MPI_INT, rb, chunk, MPI_INT, MPI_COMM_WORLD); MPI_Allreduce (&status, &gstatus, 1, MPI_INT, MPI_SUM, MPI_COMM_WORLD); if (rank == 0) { if (gstatus ≠ 0) { printf («all_to_all povertajet’cja %dn», gstatus);fflush (stdout); } } free (sb); free (rb); MPI_Finalize (); return (EXIT_SUCCESS);}.

Зауважимо, що в рамках моделі All-to-all розглядаються тільки комунікації виду «точка-точка». Моделювати колективні операції досить складно, тому що спосіб їх виконання у вигляді сукупності точкових операцій залежить від кількох факторів: алгоритмів, що використовуються, характеристик обчислювальної системи і переданих повідомлень. Зокрема, колективні операції МРІ по-різному реалізовані в бібліотеках різних виробників, а також у різних версіях бібліотеки одного виробника. У майбутньому планується розширення даної моделі за рахунок урахування колективних операцій.

4.5 Симуляція роботи кластеру та його керуючої системи.

Всі описані нище кількісні параметри генеруються на основі певних законів розподілу випадкових величин, підібраних в результаті аналізу реальних трас, зібраних на кластерних обчислювальних системах (див.таблицю 4.1).

Таблиця 4.1. Закони розподілу параметрів моделі.

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

5. КЛАСТЕР ЦЕНТРУ СУПЕРКОМП’ЮТЕРНИХ ОБЧИСЛЕНЬ.

5.1 Центр суперкомп’ютерних обчислень.

Центр суперкомп’ютерних обчислень (ЦСО) створений з метою розбудови інформаційної інфраструктури освіти і науки, реалізації положень Указу Президента України від 20 жовтня 2005 року № 1497.2005 «Про першочергові завдання щодо впровадження новітніх інформаційних технологій», завдань Державної цільової програми «Інформаційні та комунікаційні технології в освіті і науці на 2006;2010 роки» та на виконання відповідного розпорядження Кабінету Міністрів України № 301-р від 31 травня 2006 року.

На технічному майданчику ЦСО розташовується обладнання Світового центру даних (СЦД) з геоінформатики та сталого розвитку. СЦД має окремий зовнішній канал доступу до інтернет. Функціонування СЦД забезпечується службовими серверами, що об'єднані в окрему підмережу, та серверами зберігання на основі ПЗ.

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

За свою історію кластерний суперкомп’ютер НТУУ КПІ (кластер ЦСО) пройшов два оновлення, кожне з яких збільшувало його обчислювальну потужність: починаючи з 44 вузлів, що мали пікову продуктивність близько 2 Тфлопс, основний кластер наразі має 112 вузлів із 624 процесорами, пікова продуктивність яких складає 7 Тфлопс (linpack 5,7 Тфлопс).

5.2 Стратегічні проекти НТУУ «КПІ»

Стратегічними проектами, що виконуються з використанням кластеру НТУУ «КПІ» є:

— розбудова високоякісної національної GRID-інфраструктури з відповідними сервісами для надання можливості вітчизняним науковцям плідно співпрацювати в Європейському науковому просторі (European Research Area, ERA), що сприятиме створенню економіки інформаційного суспільства, заснованої на знаннях, шляхом впровадження наукових концепцій GRID і найбільш вагомих наукових додатків, які використовуються в GRID-середовищі;

— Українська філія Світового Центру Даних («УФ СЦД»), що є складовою частиною системи Світових Центрів Даних, яка створена та підтримується Міжнародною Радою з Науки (ICSU). Діяльність УФ СЦД координується Комісією Міжнародної Ради з Науки і здійснюється відповідно до Керівництва для системи СЦД. Створення єдиного центру даних дозволяє українським науковцям отримати своєчасний доступ до світових даних у різноманітних галузях науки. Дослідження таких об'єктів, як тектонічні платформи, океани, сонячна активність, космічні проміні та інші, неможливо здійснити зусиллями лише однієї країни, проте ці об'єкти мають великий вплив на всі прояви життя, тому об'єднання зусиль та обмін інформацією при таких дослідженнях є необхідною умовою для отримання унікальних результатів світового масштабу;

— проведення сучасних квантово-хімічних розрахунків, зокрема комп’ютерне моделювання реакційної здібності метал-оксо сполук та металопорфіринів, моделювання селективної активності алканів тощо;

— класична молекулярна динаміка (класичне моделювання динамічних властивостей рідин, поверхонь твердих тіл та границь розділу кристал/рідина на атомному рівні) та молекулярна динаміка ab initio (системи ті ж, що і в класичному випадку, але додатково приймається до уваги динаміка електронної підсистеми — на кожному кроці розраховуються хвильові функції електронів);

— сплайн-інтерполяція цифрової рельєфної та батиметричної моделі земної кори для задач глобального екологічного моніторингу;

— симуляція масштабування, стійкості до відмов та стресових навантажень на пірінгові мережі та ін.

5.3 Поточна конфігурація кластеру НТУУ «КПІ».

Поточна конфігурація кластеру НТУУ «КПІ» має в своєму складі 2 системи. Перша забезпечує основу потужності і працює під управлінням ОС Linux, а саме CentOS release 5.2. На базі другої функціонує кластер під управлінням ОС MS Windows HPC Edition, а також навчальний кластер, що слугує для проведення учбових курсів та забезпечення лабораторних робіт. Внутрішній інтерконнект в обох системах реалізований на базі окремих комутаторів технології Infiniband. Службова мережа, що поєднує кластер, сервісні сервери та обслуговуючу лабораторію, збудована за технологією Gigabit Ethernet. Зовнішній канал зв’язку забезпечується оптоволоконною лінією КПІ-телеком, через яку кластер має доступ до ресурсів мережі URAN.

На відміну від другої системи в першій наявні: компілятори C++ - intel 10.1, gcc 4.1.2; та прикладне програмне забезпечення: GROMACS 4.0.2, fftw 3.2, GAMESS.

Нижче наведені й інші технічні характеристики систем кластеру (див. таблицю 5.1).

Таблиця 5.1 — Технічні характеристики систем кластеру.

Схема кластеру ЦСО зображена на рисунку 5.1.

Рис. 5.1 — Схема кластеру ЦСО.

6. РЕЗУЛЬТАТИ ЕКСПЕРИМЕНТАЛЬНОГО ДОСЛІДЖЕННЯ.

Дослідження проводилось для двох груп сценаріїв: обчислювальний кластер з однорідними вузлами і однорідною високопродуктивною мережею та обчислювальний кластер з неоднорідними вузлами і однорідною мережею.

В першому випадку моделювався кластер з 12 вузлів, кожен з яких має 2 обчислювальні ядра, 2Гб оперативної пам’яті, 40Гб локальної дискової пам’яті, одиничну відносну обчислювальну швидкість. В другому — використовувалася конфігурація з 12 вузлів з сумарною кількістю обчислювальних ядер 24, різними об'ємами оперативної і дискової пам’яті, різною відносною обчислювальною швидкістю.

Кожна група сценаріїв розглядалася для трьох топологій: товсте дерево (два 6-портових кореневих комутатори і три 8-портових листових комутатори (4 висхідних портів і 4 вузлових портів на кожному)), зірка (один 12-портовий комутатор), двовимірний тор розміром 34 вузла.

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

Зокрема критерій продуктивності включає наступні метрики: середня завантаженість обчислювальних ядер вузлів кластера, втрата продуктивності кластера CL, максимальний час завершення задачі, середній час очікування задач в черзі і середнє обмежене уповільнення задач .

Для отримання достовірних результатів симуляція проводилася в кожному сценарії 100 разів для різних потоків із 500 випадково згенерованих задач. Всі обчислювальні значення метрик усереднювалися по всіх потоках.

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

Рис. 6.1 — Графіки залежності значень метрики продуктивності і від величини системної загрузки L.

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

Отримані результати експериментального дослідження занесені в таблицю 6.1. Для кожного сценарію в залежності від топології системи і величини системного завантаження L може бути рекомендований свій алгоритм планування, що представляє собою поєднання алгоритму вибору наступної задачі з черги Backfill з запропонованими методами її призначення на обчислювальні ядра MDM або SDM.

Таблиця 6.1 — Алгоритми планування, які показали кращі результати в кожному сценарії.

ВИСНОВОК.

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

А також акцентувалася увага на комунікаційних патернах, зокрема патерні MPI_All-to-all, його практичному застосуванні. Патерн MPI_All-to-all характерний тим, що в ньому кожен процес відправляє повідомлення процесам, які залишилися.

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

Проведене дослідження показало ефективність роботи алгоритмів планування, що представляють собою поєднання алгоритму Backfill з запропонованими методами призначення на MDM і SDM.

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

СПИСОК ВИКОРИСТАНОЇ ЛІТЕРАТУРИ.

Топорков В. В. Модели распределенных вычислений. М.: ФИЗМАТЛИТ, 2004. — 320 c.

Гергель, В. П. Теоретические основы экспериментального исследования алгоритмов плани-рования задач для вычислительного кластера с помощью симулятора / В. П. Гергель, П. Н. Полежаев // Журнал «Вестник Оренбургского государственного университета», № 9(115), 2010. — С. 114−120.

Полежаев П. Н. Исследование алгоритмов планирования параллельных задач для кластер-ных вычислительных систем с помощью симулятора // Параллельные вычислительные тех-нологии (ПАВТ'2010): Труды международной конференции. — Челябинск: Изд. ЮУрГУ, 2010 г. стр. 287 — 298.

Симулятор высокопроизводительного кластера TopSimity с учетом топологии системы и многопроцессорности узлов / Полежаев П. Н. Свидетельство Федеральной службы по интеллектуальной собственности, патентам и товарным знакам № 2 010 617 255 от 29 октября 2010 г.

Полежаев П. Н. Симулятор вычислительного кластера и его управляющей системы, используемый для исследования алгоритмов планирования задач. // Журнал «Вестник ЮУрГУ», № 35(211). Серия «Математическое моделирование и программирование», вып. 6, 2010. стр. 79 — 90.

Moore S.Q., Lionel M.N. The Effects of Network Contention on Processor Allocation Strategies // Proceedings of the 10th International Parallel Processing Symposium. — Washington, DC: EEE Computer Society, 1996. — P. 268−273.

Bani-Mohammad S., Ould-Khaoua M., Abaneh, I. An efficient processor allocation strategy that maintains a high degree of contiguity among processors in 2D mesh connected multicomputers // Proceedings of ACS/IEEE International Conference on Computer Systems and Applications, AICCSA. — 2007. — P. 934−941.

Центр суперкомп’ютерних обчислень НТУУ «Київський політехнічний інститут» [Електронний ресурс]. — Режим доступу: URL: http://www.uran.net.ua/projects/hpcc-kpi/index.htm — Назва з екрану Центр суперкомп’ютерних обчислень [Електронний ресурс]. — Режим доступу: URL: http://grid.kpi.ua/index.php/uk/national-resource-centre/10-centr-superkompyuternih-obchislen.html — Назва з екрану.

Навчально-науковий комплекс. «Інститут прикланого ситемного аналізу». ЦСО [Електронний ресурс]. — Режим доступу: URL: http://iasa.kpi.ua/collaboration-uk/international-relations/high-performance-computing-center — Назва з екрану

Cluster [Електронний ресурс]. — Режим доступу: URL: http://hpcc.org.ua/index.php/Cluster — Назва з екрану

MPI_Alltoall [Електронний ресурс]. — Режим доступу: URL: http://mpi.deino.net/mpi_functions/MPI_Alltoall.html — Назва з екрану

Allbest