Основи технології паралельних обчислень

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

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

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

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

1. Взаємодія через пам'ять, що розділяється (наприклад, в Java або C #). Даний вид паралельного програмування зазвичай вимагає якоїсь форми захоплення управління для координації потоків між собою.

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

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

1. OpenMP використовується в паралельних системах із загальною пам'яттю (наприклад, сучасні комп'ютери з багатоядерними процесорами);

2. MPI (Message Passing Interface) є стандартом систем передачі повідомлень між паралельно виконуваними процесами, використовується при розробці програм для суперкомп'ютерів;

3. POSIX Threads є стандартом реалізації потоків виконання;

4. Операційна система Windows має вбудовану підтримку багатопотокових додатків для C ++ на рівні API;

5. PVM (Parallel Virtual Machine) дозволяє поєднувати різнорідні пов'язані мережею комп'ютери в загальний обчислювальний ресурс.

Системи на базі декількох комп'ютерів відносять до класу систем для розподілених обчислень. Подібні рішення використовуються досить давно. Найбільш яскравий приклад технології розподілених обчислень - MPI (Message Passing Interface - інтерфейс передачі повідомлень). MPI є найбільш поширеним стандартом інтерфейсу обміну даними в паралельному програмуванні, існують його реалізації для величезного числа комп'ютерних платформ. MPI надає програмісту єдиний механізм взаємодії гілок всередині паралельного додатка незалежно від машинної архітектури (однопроцесорні / багатопроцесорні із загальною / роздільною пам'яттю), взаємного розташування гілок (на одному процесорі або на різних).

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

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

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

OpenMP (Open Multi-Processing) - це набір директив компілятора, бібліотечних процедур і змінних оточення, які призначені для програмування багатопотокових додатків на багатопроцесорних системах із загальною пам'яттю.

Розробку специфікації OpenMP ведуть кілька великих виробників обчислювальної техніки і програмного забезпечення, чия робота регулюється некомерційною організацією, званої OpenMP Architecture Review Board (ARB).

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

Завдання, що виконуються потоками паралельно, також як і дані, необхідні для виконання цих завдань, описуються за допомогою спеціальних директив препроцесора відповідної мови - прагм. Наприклад, ділянка коду на мові Fortran, який повинен виконуватися декількома потоками, кожен з яких має свою копію змінної N, передує наступній директивою. $ OMP PARALLEL PRIVATE (N)

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

Ключовими елементами OpenMP є

1. конструкції для створення потоків (директива parallel);

2. конструкції розподілу роботи між потоками (директиви DO / for і section);

3. конструкції для управління роботою з даними (вираження shared і private для визначення класу пам'яті змінних);

4. конструкції для синхронізації потоків (директиви critical, atomic і barrier);

5. процедури бібліотеки підтримки часу виконання (наприклад, omp_get_thread_num);

6. змінні оточення (наприклад, OMP_NUM_THREADS).

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

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

У цій програмі два масиви (a і b) складаються паралельно десятьма потоками.

int main (int argc, char * argv [])

Цю програму можна скомпілювати, використовуючи gcc-4.4 і новіші з прапором -fopenmp. Очевидно, якщо прибрати підключення заголовки omp.h, а також виклики функції настройки OpenMP, програму можливо скомпілювати на будь-якому компіляторі З як звичайну послідовну програму.

OpenMP підтримується багатьма сучасними компіляторами:

1. Компілятори Sun Studio підтримують офіційну специфікацію - OpenMP 2.5 - з поліпшеною продуктивністю під ОС Solaris; підтримка Linux запланована на наступний реліз.

3. GCC 4.2 підтримує OpenMP, а деякі дистрибутиви (такі як Fedora Core 5 gcc) включили підтримку в свої версії GCC 4.1.

4. Intel C ++ Compiler, включаючи версію Intel Cluster OpenMP для програмування в системах з розподіленою пам'яттю.

Message Passing Interface (MPI, інтерфейс передачі повідомлень) - програмний інтерфейс (API) для передачі інформації, який дозволяє обмінюватися повідомленнями між процесами, які виконують одну задачу. Розроблено Вільямом Гроуппом, Евін ласки (англ.) І іншими.

MPI є найбільш поширеним стандартом інтерфейсу обміну даними в паралельному програмуванні, існують його реалізації для великого числа комп'ютерних платформ. Використовується при розробці програм для кластерів і суперкомп'ютерів. Основним засобом комунікації між процесами в MPI є передача повідомлень один одному. Стандартизацією MPI займається MPI Forum. У стандарті MPI описаний інтерфейс передачі повідомлень, який повинен підтримуватися як на платформі, так і в додатках користувача. В даний час існує велика кількість безкоштовних і комерційних реалізацій MPI. Існують реалізації для мов Фортран 77/90, Сі і Сі ++.

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

Більшість сучасних реалізацій MPI підтримують версію 1.1. Стандарт MPI версії 2.0 підтримується більшістю сучасних реалізацій, але деякі функції можуть бути реалізовані не до кінця.

передача і отримання повідомлень між окремими процесами;

колективні взаємодії процесів;

взаємодії в групах процесів;

реалізація топологій процесів;

динамічне породження процесів і управління процесами;

односторонні комунікації (Get / Put);

паралельний введення і виведення;

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

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

1. відправник - ранг (номер в групі) відправника повідомлення;

2. одержувач - ранг одержувача;

3. ознака - може використовуватися для поділу різних видів повідомлень;

4. комунікатор - код групи процесів.

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

Нижче наведено приклад програми обчислення числа π на мові C з використанням MPI:

// Підключення необхідних заголовків

// Підключення заголовки MPI

// Функція для проміжних обчислень

double f (double a)

return (4.0 / (1.0+ a * a));

// Звільнення підсистеми MPI

Найбільш поширеними реалізаціями MPI на сьогоднішній день є:

MPICH - найпоширеніша безкоштовна реалізація, працює на UNIX-системах і Windows NT

Підтримуються різні комунікаційні системи (в тому числі Myrinet).

WMPI - реалізація MPI для Windows

MPI / PRO for Windows NT - комерційна реалізація для Windows NT

Intel MPI - комерційна реалізація для Windows / Linux

Microsoft MPI входить до складу Compute Cluster Pack SDK. Заснований на MPICH2, але включає додаткові засоби управління завданнями. Підтримується специфікація MPI-2.

HP-MPI - комерційна реалізація від HP

SGI MPT - платна бібліотека MPI від SGI

Mvapich - безкоштовна реалізація MPI для Infiniband

Open MPI - безкоштовна реалізація MPI, спадкоємець LAM / MPI

Oracle HPC ClusterTools - безкоштовна реалізація для Solaris SPARC / x86 і Linux на основі Open MPI

MPJ - MPI for Java

POSIX Threads - стандарт POSIX реалізації потоків виконання, що визначає API для створення і управління ними.

Бібліотеки, які реалізують цей стандарт (і функції цього стандарту), зазвичай називаються Pthreads (функції мають приставку «pthread_»). Хоча найбільш відомі варіанти для Unix-подібних операційних систем, таких як Linux або Solaris, але існує і реалізація для Microsoft Windows (Pthreads-w32)

Pthreads визначає набір типів і функцій на мові програмування Сі. Заголовки - pthread.h.

1. pthread_t - дескриптор потоку;

2. pthread_attr_t - перелік атрибутів потоку.

Функції управління потоками:

1. pthread_create () - створення потоку;

2. pthread_exit () - завершення потоку (повинна викликатися функцією потоку при завершенні);

3. pthread_cancel () - скасування потоку;

4. pthread_join () - заблокувати виконання потоку до припинення іншого потоку, зазначеного у виклику функції;

5. pthread_detach () - звільнити ресурси займані потоком (якщо потік виконується, то звільнення ресурсів відбудеться після його завершення);

6. pthread_attr_init () - форматувати структуру атрибутів потоку;

7. pthread_attr_setdetachstate () - вказати системі, що після завершення потоку вона може автоматично звільнити ресурси, які займає потоком;

8. pthread_attr_destroy () - звільнити пам'ять від структури атрибутів потоку (знищити дескриптор).

Функції синхронізації потоків:

2. pthread_mutex_init (), pthread_mutex_destroy (), pthread_mutex_lock (), pthread_mutex_trylock (), pthread_mutex_unlock ();

3. pthread_cond_init (), pthread_cond_signal (), pthread_cond_wait ().

Приклад використання потоків на мові C:

static void wait_thread (void)