Загальні відомості про обчислювальний кластер. Розробка імітаційної схеми кластера, моделі обчислювальної системи, керуючої системи, обчислювального завантаження потоком задач. Схема роботи алгоритмів планування. Результати експериментального дослідження.
Аннотация к работе
У даному проекті проводяться результати дослідження запропонованих та існуючих алгоритмів планування завдань для обчислювального кластера з урахуванням мережі і багатопроцесорності вузлів. Дослідження проводилося за допомогою розробленого симулятора обчислювального кластеру та його керуючої системи, в основу якої лягла запропонована модель обчислювальної системи, модель керуючої системи, імітаційна схема роботи кластера, а також модель завантаження системи потоком задач. Алгоритми планування завдань, використані в існуючих керуючих системах обчислювальних кластерів, демонструють непогану ефективність роботи.Кожний обчислювальний вузол має свою оперативну память і працює під керуванням своєї операційної системи. Користувачі мають домашні каталоги на сервері доступу - шлюзі (цей сервер забезпечує звязок кластера із зовнішнім світом через корпоративну локальну обчислювальну мережу або Інтернет), безпосередній доступ користувачів на керуючий вузол виключається, а доступ на обчислювальні вузли кластера можливий (наприклад, для ручного керування компіляцією завдання).Існує декілька способів завантаження обчислювальної потужності кластера: - Запускання багатьох однопроцесорних завдань. Це може бути сприятливим варіантом, якщо потрібно провести багато незалежних обчислювальних експериментів з різними вхідними даними, причому час проведення кожного окремого розрахунку не має значення, а всі дані розміщуються в обємі памяті, доступному одному процесу. Якщо звертання до таких підзадач становить більшу частину обчислювальних операцій програми, то використання такої паралельної бібліотеки дозволить одержати паралельну програму практично без написання власного паралельного коду.Причому безпосередній доступ до памяті іншого процесу неможливий, а обмін даними між процесами відбувається за допомогою операцій приймання й посилання повідомлень. Тобто процес, який повинен одержати дані, викликає операцію receive (прийняти повідомлення), і вказує, від якого саме процесу він повинен одержати дані, а процес, який повинен передати дані іншому, викликає операцію send (послати повідомлення) і вказує, якому саме процесу потрібно передати ці дані.Довільна кластерна обчислювальна система може бути описана за допомогою орієнтованого графа: де - множина обчислювальних вузлів, - множина комутаторів, - множина спрямованих мережевих звязків між ними, - відображення, що характеризує пропускну здатність кожного мережевого звязку в байтах за секунду. Функції визначають для кожного обчислювального вузла відповідно - кількість його обчислювальних ядер , обсяги оперативної і дискової памяті в кілобайтах. Відображення для вузла задає відносну продуктивність кожного його обчислювального ядра, яка визначає, у скільки разів ядра даного вузла працюють швидше обчислювальних ядер найнепродуктивнішого вузла кластера. Нехай - множина обчислювальних ядер вузла , - множина обчислювальних ядер всіх вузлів кластера, тоді позначимо в якості номер задачі, виконаної на ядрі в момент часу . Значення динамічних параметрів-го вузла в момент часу можуть бути обчислені за такими формулами: де і - відповідно обєми оперативної і дискової памяті, необхідні кожному процесу-ої паралельної задачі.IMG_aa7457c8-5eff-4d99-8392-e05b7c17df7fУ рамках цього проекту розглядається класична архітектура керуючої системи обчислювального кластера (КСОК), що припускає наявність наступних основних компонент (див. рисунок 2.1): 1.Вона включає: планування (складання розкладу для завдань), доставку необхідних файлів на виконавчі вузли, моніторинг процесу виконання і збір його результатів. Планувальник в процесі своєї роботи складає розклад запуску паралельних завдань з черги відповідно до закладеного в нього онлайнового алгоритму планування.IMG_90f4d6f9-d080-4a59-a814-2a6f9b4de457При кожному запуску циклу планування алгоритм вибору наступного завдання з черги на основі поточного розкладу Schedule і на основі черги очікуваних завдань Q динамічно формує на момент часу t список вікон планування W. У процесі своєї роботи останній формує для J вікно запуску R, на основі якого оновлюються WL і Schedule. Підсумковий розклад після запуску всіх завдань з черги Q може бути представлений у вигляді безлічі впорядкованих пар Schedule = {(У рамках проведеного дослідження були розглянуті алгоритми планування завдань, що представляють собою поєднання алгоритму вибору наступного завдання з черги 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 1x1 (MC1x1) і Minimizing message-passing Contention 1x1 Incremental (MC1x1 Inc); для топології зірки - Sorting Nodes by Performance (SNP) i Sorting Nodes by Speed
План
ЗМІСТ
ВСТУП
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 Симуляція роботи кластеру та його керуючої системи