Моделі паралельних обчислень
Паралельне програмування пов'язане з додатковими труднощами – необхідно явно керувати роботою тисяч процесорів, координувати мільйони міжпроцесорних взаємодій. Для того щоб вирішити задачу на паралельному комп’ютері необхідно розподілити обчислення між процесорами системи так, щоб кожен процесор розв'язував частини задачі. Крім того, бажано, щоб як найменший обсяг даних передавався між процесорами, оскільки комунікації значно повільніші, ніж обчислення. Часто виникають конфлікти між ступенем розпаралелювання і обсягом комунікацій, тобто – чим більше процесорів використовуються для обчислення розпаралеленої задачі, тим більший обсяг даних необхідно передавати між ними. Середовище паралельного програмування має надавати адекватне керування розпаралелюванням і комунікаціями даних. Через складність паралельних комп’ютерів і їх значну відмінність від традиційних однопроцесорних комп’ютерів – не можна просто скористатись традиційними мовами програмування і очікувати високої продуктивності.
Методи паралельного програмування Процес\канал
В цій моделі програми складаються з одного та більше процесів, розподілених між процесорами. Процеси виконуються одночасно, їх кількість може змінюватись протягом часу виконання програми. Процеси обмінюються даними через канали, які представляють собою одно направлені комунікаційні лінії, які з’єднують тільки два процеси. Канали можна створювати та видаляти. Модель процес\канал характеризується наступними властивостями: 1. Паралельне обчислення складається з одного та більше одночасно виконуваних процесів, число яких може змінюватись під час виконування програми 2. Процес – це послідовна програма з локальними даними. Процес має вхідні та вихідні порти, які служать інтерфейсом до середовища процесу. 3. В додаток до звичайних операцій процес може виконувати наступні дії: Надіслати повідомлення через вихідний порт, отримати повідомлення з вхідного порту, створити новий процес та завершити процес. 4. Операція відправлення асинхронна – вона завершується відразу, не очікуючи того, коли данні будуть отримані. Операція отримання синхронна – вона блокує процес до моменту отримання повідомлення. 5. Пари з вхідного та вихідного портів з’єднуються чергами повідомлень, які називаються каналами. Канали можна створювати та видаляти. Посилання на канали можна включати в повідомлення, так що зв’язність може змінюватись динамічно. 6. Процеси можна розподіляти між фізичними процесорами різними способами, до того ж відображення (розподілення) не впливає на семантику програми.
Поняття процесу дозволяє говорити про розташування даних : дані, які зберігаються в локальній пам’яті процесу – розташовуються «близько», інші дані «віддалені». Поняття каналу забезпечує механізм для визначення залежностей між процесами на основі даних, тобто – аби продовжити виконання одному процесу необхідні дані іншого.
Обмін повідомленнями (Message Passing) В цій моделі, програми, написані на традиційній послідовній мові, виконуються процесорами комп’ютера. Кожна програма має доступ до пам’яті виконуючого процесора. Програми обмінюються між собою даними, використовуючи підпрограми приймання\передачі даних деякої комунікаційної системи. Програми, які використовують обмін повідомленнями можуть виконуватись тільки на MIMD комп’ютерах. Нині модель обміну повідомленнями є найбільш широко використовуваною моделлю паралельного програмування. Програми цієї моделі подібні до програм моделі процес\канал, створюють множину процесів, де з кожним асоційовані локальні дані. Кожен процес можна ідентифікувати за унікальним іменем. Процеси взаємодіють, надсилаючи та отримуючи повідомлення. З цієї точки зору, модель «обмін повідомленнями» є різновидом моделі «процес\канал» і відрізняється лише механізмом, який використовується при передачі даних. Наприклад, замість відправлення повідомлення в канал «channel 2» можна відправити повідомлення процесу «process 3».
Модель «обмін повідомленнями» не накладає обмежень ні на динамічне створення процесів, ні на виконання декількох процесів одним процесором, ні на використання різних програм для різних процесів. Формальний опис систем «обміну повідомленнями» не розглядає питань, які стосуються маніпулювання процесами, однак при реалізації таких систем доводиться приймати відповідні рішення. На практиці склалось так, що більшість систем «обміну повідомленнями» при запуску паралельної програми створюють фіксоване число ідентичних процесів і не дозволяють створювати та знищувати процеси впродовж роботи програми. У таких системах кожен процес виконує одну і ту саму програму (параметризовану відносно ідентифікатора процесу або процесора), але працює з різними даними, тому про такі системи кажуть, що вони реалізують SPMD (Single Program Multiple Data – одна програма багато даних) модель програмування, яка достатньо зручна для широкого діапазону додатків паралельного програмування, але вона ускладнює розробку деяких типів паралельних алгоритмів.
Паралелізм даних (Data Parallel) У цій моделі єдина програма задає розподілення даних між усіма процесорами комп’ютера і операції над ними. Розподілюваними даними зазвичай є масиви. Як правило, мови програмування, які підтримують дану модель допускають операції над масивами, дозволяють використовувати у виразах цілі масиви або окремі їх частини. Розпаралелювання операцій над масивами та циклів опрацювання масивів дозволяє збільшити продуктивність програми. Компілятор відповідає за генерування коду, який розподіляє елементи масивів і обчислень між процесорами. Кожен процесор відповідає за ту підмножину елементів масиву, яка знаходиться в його локальній пам’яті. Програми з паралелізмом даних можуть бути трансльовані і виконуватись як на MIMD, так і на SIMD комп’ютерах.
Назва моделі походить від того, що вона експлуатує паралелізм, який полягає у використанні однієї операції для багатьох елементів структур даних. Програма з паралелізмом даних складається з послідовностей подібних операцій. Оскільки операції над кожним елементом даних можна розглядати як незалежні процеси, то ступінь деталізації таких обчислень дуже великий, а поняття «локальності» відсутнє. Тому, компілятори мов з паралелізмом даних часто вимагають, щоб програміст надавав інформацію щодо того, як дані повинні бути розподілені між процесорами, іншими словами, як програма має бути розбита на процеси. Компілятор транслює програму з паралелізмом даних в SPMD програму, генеруючи комунікаційний код автоматично.
Спільна пам'ять (Shared Memory) У цій моделі всі процеси сумісно використовують спільний адресний простір. Процеси асинхронно звертаються до спільної пам’яті з запитами читання та запису, що створює проблеми при виборі моменту для переміщення даних в пам'ять та видалення цих даних. Для керування доступом до спільної пам’яті використовуються стандартні механізми синхронізації – семафори і блокування процесів. Перевага цієї моделі з точки зору програмування полягає в тому, що поняття власності даних (монопольного володіння даними) відсутнє, тому не потрібно явно задавати обмін даними між виробниками даних та їх користувачами. Ця модель з однієї сторони спрощує розробку програми, але з іншої – ускладнює розуміння і керування локальністю даних, а також написання детермінованих програм. Загалом, ця модель використовується при програмуванні для архітектур з загальнодоступною пам’яттю.