Знайомство з рівнями розпаралелювання

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

Розпаралелювання на рівні завдань

Часто розпаралелювання на цьому рівні є найпростішим і при цьому найефективнішим. Таке розпаралелювання можливе в тих випадках, коли вирішуване завдання природним чином складається з незалежних підзавдань, кожну з яких можна вирішити окремо. Хорошим прикладом може бути стиснення аудіо-альбому. Кожен запис може оброблятися окремо, оскільки він не пов'язані з іншими.

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

Іншими прикладами розпаралелювання на цьому рівні абстракції є паралельна компіляція файлів у Visual Studio 2008, обробка даних у пакетних режимах.

Рівень паралелізму даних

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

Цей вид паралелізму широко використовується під час вирішення завдань чисельного моделювання. Рахункова область представлена у вигляді осередків, що описують стансередовища у відповідних точках простору - тиск, щільність, відсоткове співвідношення газів, температура тощо. Кількість таких осередків може бути величезною — мільйони та мільярди. Кожна з цих осередків повинна бути оброблена одним і тим самим способом. Тут модель паралелізму за даними дуже зручна, оскільки дозволяє завантажити кожне ядро, виділивши йому певний набір осередків. Рахункова область розбивається на геометричні об'єкти, наприклад паралелепіпеди, і комірки, що увійшли до цієї області, віддаються обробку певному ядру. У математичній фізиці такий тип паралелізму називають геометричним паралелізмом.

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

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

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

Рівень розпаралелювання алгоритмів

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

OpenMP (Open Multi-Processing) — це набір директив компілятора, бібліотечних процедур та змінних оточення, які призначені для програмування багатопотокових додатків на багатопроцесорних системах. В OpenMP використовується модель паралельного виконання «розгалуження-злиття». Програма OpenMP починається як єдиний потік виконання, який називається початковим потоком. Коли потік зустрічає паралельну конструкцію, він створює нову групу потоків, що складається з деякого числа додаткових потоків, і стає головним у новій групі. Усі члени нової групи (включаючи головний потік) виконують код усередині паралельної конструкції. Наприкінці паралельної конструкції є неявний бар'єр. Після паралельної конструкції виконання користувача коду продовжує тільки головний потік. У паралельний регіон можуть бути вкладені інші паралельні регіони.

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

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

Паралелізм на рівні інструкцій

Найбільш низький рівень паралелізму, що здійснюється нарівні паралельної обробки процесором кількох інструкцій На цьому рівні знаходиться пакетна обробка декількох елементів даних однією командою процесора. Йдеться про технології MMX, SSE, SSE2 тощо. Цей вид паралельності іноді виділяють ще більш глибокий рівень розпаралелювання - паралелізм на рівні бітів.

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

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