Типи паралельних обчислень
 | У цій статті відсутній вступний розділ, що має містити визначення предмета і стислий огляд найважливіших аспектів статті. (вересень 2020) |
Паралелізм за задачами та паралелізм за даними[ред. | ред. код]
Щоб мати можливість використовувати паралелізм як такий в наявності мають бути програмні та апаратні засоби для забезпечення можливості одночасного виконання двох та більше завдань. Є два важливі типи паралельних обчислень:
-паралелізм за командами або їх сукупністю (задачами) – можливість одночасно виконувати різні команди (задачі) одночасно;
-паралелізм з даними – можливість виконувати одну і ту ж команду (задачу) з-над різними наборами даних одночасно.
Для нетривіальних проблем, важливо мати формалізовані концепції розподілу (декомпозиції) паралелізму, тому при розпаралелюванні обчислень використовують наступні концепції декомпозиції:
-розподіл за командами (задачами): розбиття алгоритму на незалежні задачі (без фокусування уваги на даних);
-розподіл за даними: розбиття набору даних на окремі частини, які можна опрацьовувати паралельно.
Розподіл за задачами спрощує алгоритм на функціонально незалежні частини, але виникають ситуації, коли задачі можуть бути залежні від інших задач:
-якщо вхідні (початкові) дані задачі В залежать від вихідних (кінцевих) даних задачі А, то задача В залежна від задачі А;
-задачі, що є незалежними (або залежності яких є завершеними) можуть бути виконані в будь-який час незалежно одна від одної для досягнення паралелізму;
Для опису зв’язків між задачами використовуються графи залежності за задачами (рисунок 1.1, а, б).
Для наочнішого прикладу розробимо граф залежності за задачами для випічки печива (рисунок 2.2).
Кожне завдання, яке не є залежним в графі залежностей може бути виконано паралельно (наприклад, розігрівання печі та купівля продуктів). Розподіл за даними застосовується або для результуючих даних, або для початкових.
Для більшості наукових та інженерних застосунків декомпозуються результуючі дані, наприклад:
- Кожен отриманий піксель зображення згортки отримується шляхом застосування фільтру до деякої області вхідних пікселів.
- Кожен отриманий елемент перемноження матриць, що отриманий множенням рядку на стовпчик вхідних матриць.
Дуже добре мати цикли, в яких за кожної ітерації обчислюється одне значення матриці чи масиву. Такі типи алгоритмів найкраще відповідають декомпозиції по результуючим даним.
Така методика застосовується кожного разу, коли алгоритм базується на функціях із відношенням один-до-одного чи багато-до-одного.
Декомпозиція по початковим даним подібна до попередньої, за винятком того, що вона буде корисною, коли алгоритм є функцією із відношенням один-до-багатьох, наприклад:
-Гістограма будується шляхом розміщення кожного початкового даного в один із фіксованого числа контейнерів.
-Функція пошуку може отримувати строку для пошуку як вхідні дані та здійснювати пошук у інших строках.
Вибір того, яким чином здійснювати декомпозицію поставленого завдання базується виключно на алгоритмі. Тим не менш, коли стає актуальною реалізація паралельного алгоритму, до уваги потрібно брати міркування як щодо програмної реалізації, так і щодо апаратного забезпечення цієї реалізації[1].
Апаратний та програмний паралелізм[ред. | ред. код]
В попередньому питанні було розглянуто поділ паралелізму подібно до моделі Флінна: за командами (задачами) та даними. В попередній темі (тема 2) була розглянута архітектура апаратних засобів для паралельних обчислень. Також існують програмні засоби, що дозволяють здійснювати паралельні обчислення. Як апаратні, так і програмні засоби можуть досягати паралелізму і за допомогою паралелізму по задачам, і за допомогою паралелізму по даним, за допомогою об’єднання цих підходів. В той же час самі апаратні та програмні засоби можуть використовуватись разом чи окремо (в рідкісних випадках).
Більшість 90’х років ХХ століття було витрачено на отримання центральних процесорів (CPU) з автоматичним використанням паралелізму на рівні інструкцій – Instruction Level Parallelism (ILP): декілька інструкцій (без залежностей) видаються та виконуються паралельно[2].
Паралелізм високого рівня автоматично важко досягнути без використання різноманітних програмних конструкцій, за допомогою яких апаратному забезпеченню вказується «місця», де будуть виконуватись паралельні обчислення. При паралельному програмуванні програміст повинен вибрати програмну модель та апаратне забезпечення, що підходять для вирішення наявної проблеми.
В загальному випадку одні апаратні засоби підходять для вирішення якихось типів паралельних обчислень краще, ніж інші (таблиця ).
| Тип апаратного забезпечення |
|---|
| Багатоядерні суперскалярні процесори (Multi-core superscalar processors) |
| Векторний (Vector ) або SIMD процесори |
| Багатоядерні SIMD процесори (Multi-core SIMD processors — GPU) |
Паралельне програмне і апаратне забезпечення[ред. | ред. код]
Стрімкого розвитку набули також і графічні процесори (англ. Graphic Processing Unit – GPU). GPU програми називаються ядрами, які описуються програмною моделлю під назвою Single Program Multiple Data (SPMD)[3].
SPMD – Single-Program, Multiple Data – «одна програма – багато [потоків] даних»; архітектура SPMD — різновид архітектури MIMD.
SPMD виконує деяку кількість екземплярів однієї і тієї ж програми незалежно і кожен екземпляр опрацьовує різний набір даних.
Наведемо існуючі підходи для розробки паралельних програм:
— Бібліотеки передачі повідомлень: Message Passing Interface (MPI) — інтерфейс передачі повідомлень, де використовується архітектура SPMD на розподілених кластерах. — Бібліотеки потоків (нитей):
POSIX threads (pthreads) — стандарт POSIX реалізації нитей виконання, який визначає API для створення та керування ними. Використовується для реалізації SPMD архітектури на системах із єдиною спільною пам'яттю (shared-memory system).
— Набір директив компілятора та бібліотечних процедур:
Open Multi-Processing (OpenMP) — стандарт розпаралелювання програм, що описує сукупність директив компілятора, бібліотечних процедур та змінних оточення, які призначені для програмування багатопоточних застосунків на багатопроцесорних системах із єдиною спільною пам’яттю (shared-memory system).
•Робота ядер за архітектурами SPMD, SIMD та SIMT на GPU за допомогою програмно-апаратної архітектури CUDA, фреймворка OpenCL, інтерфейсу програмування застосунків DirectCompute.
Розглянемо приклад додавання векторів (Рисунок 3.1)
Поєднання SPMD із стрічковим розбиттям в циклі дозволяє перемножити копії програми виконуючи обрахунки над різними даними паралельно (рисунок 4.2)
В прикладі додавання векторів кожен кусок даних може бути обробленим як незалежний потік (нить – thread).
На сучасних CPU, накладні витрати на створення потоків (threads) настільки великі, що куски даних повинні бути великими. Зазвичай, на практиці це декілька потоків (threads) (кількість така ж, як кількість ядер CPU) і кожному приходиться опрацьовувати великий об'єм даних.
При програмуванні на GPU, накладні витрати на створення потоків (thread) незначні, тому можна створювати один потік (thread) на кожну ітерацію в циклі.
Порівняння затрат часу на операцію додавання векторів при використанні різних підходів та архітектур (Рисунок 5.3)
Кожен виконувач елемент (елементарний процесор) в моделі процесора SIMD – обробляє однакову команду з різною частиною набору даних одночасно. Одна команда (інструкція) видається на виконання одночасно багатьом АЛП (арифметико-логічний пристрій) – ALU. Мається на увазі, що число ALU є шириною SIMD пристрою.
SIMD процесори ефективні для даих паралельних алгоритмів. Вони зменшують об'єм потоку управління та команд апаратного забезпечення за рахунок ALU.
Апаратна реалізація SIMD моделі (Рисунок 6.4)
Одна команда, що поступає повинна бути виконана на всіх елементарних процесорах (processing elements – PE). Один потік (thread) виконується на кожному елементарному процесорі (processing element).
В прикладі додавання векторів SIMD пристрій з шириною в чотири може виконати чотири ітерації циклу відразу.
Всі наявні GPU базуються на SIMD апаратному виконанні:
•GPU апаратно неявно відображає кожен SPMD потік (thread) в SIMD «ядро». Програмісту не потрібно звертати увагу на правильність апаратної складової SPMD моделі, основним тут є продуктивність.
•Ця модель запуску потоків (threads) на SIMD апаратному забезпеченні називається SingleInstructionMultipleThreads (SIMT).
На завершення слід ще раз звернути увагу на відмінності підтримки паралелізму на CPU та GPU:
•На CPU апаратна підтримка атомарних операцій використовується для паралелізму. Атомарні операції дозволяють даним бути зчитаними і записаними без втручання зі сторони іншого потоку.
•GPU розглядається як спеціалізований обчислювальний пристрій, що є сопроцесором до CPU, володіє власною пам’яттю, володіє мможливістю паралельного виконання великої кількості окремих потоків (нитей). Деякі GPU підтримують загальносистемні атомарні операції, але з великим компромісом у продуктивності. Зазвичай код, який вимагає глобальної синхронізації не дуже добре підходить для GPU (чи його слід реорганізувати).
Примітки[ред. | ред. код]
- ↑ Жуков І., Корочкін О. Паралельні та розподілені обчислення – К. Корнійчук, 2005. – 226 с.
- ↑ P. Mehrotra and J. Van Rosendale. Programming distributed memory architectures. In Advances in Languages and Compilers for Parallel Computing. MIT Press, 1991
- ↑ Программирование на параллельных обчислювальних системах: Пер с англ. / Под ред. Р. Бэбба. М.: Мир, 1991.
Література[ред. | ред. код]
| ||||||||||||||||||||||||||||||||