Аналітичний огляд технології проектування паралельних застосувань: Open MP

Аналітичний огляд технології проектування паралельних застосувань: Open MP

технологія комп’ютер пам’ять операційний

Одним з найбільш популярних засобів програмування комп’ютерів із загальною пам’яттю, що базуються на традиційних мовах програмування і використання спеціальних коментарів, в даний час є технологія OpenMP. Інтерфейс OpenMP задуманий як стандарт для програмування на масштабованих SMP-системах в моделі загальної пам’яті (shared memory model). У стандарт OpenMP входять специфікації набору директив компілятора, процедур і змінних середовища. Розробкою стандарту займається організація OpenMP ARB (ARchitecture Board), до якої увійшли представники найбільших компаній — розробників SMP-архітектур і програмного забезпечення.

До появи OpenMP не було відповідного стандарту для ефективного програмування на SMP-системах. Найбільш гнучким, мобільним і загальноприйнятим інтерфейсом паралельного програмування є MPI (інтерфейс передачі повідомлень). Проте модель передачі повідомлень недостатньо ефективна на SMP-системах та відносно складна в освоєнні.

Проект стандарту X3H5 провалився, оскільки був запропонований під час загального інтересу до MPP-систем, а також через те, що в ньому підтримується тільки паралелізм на рівні циклів. OpenMP розвиває багато ідей X3H5.

POSIX-інтерфейс для організації ниток (Pthreads) підтримується широко (практично на всіх UNIX-системах), однак з багатьох причин не підходить для практичного паралельного програмування: немає підтримки Fortranа, занадто низький рівень, немає підтримки паралелізму за даними, механізм ниток спочатку розроблявся не для цілей організації паралелізму.

OpenMP можна розглядати як високо рівневу надбудову над Pthreads (чи аналогічними бібліотеками). Багато постачальників SMP-архітектур (Sun, HP, SGI) у своїх компіляторах підтримують спец директиви для розпаралелювання циклів. Однак ці набори директив, як правило дуже обмежені, несумісні між собою; в результаті чого розробникам доводиться розпаралелювать застосування окремо для кожної платформи. OpenMP є багато в чому узагальненням і розширенням згаданих наборів директив. OpenMP надає розробнику наступні переваги:

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

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

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

Ш Одним з достоїнств OpenMP його розробники вважають підтримку так званих «orphan» (відірваних) директив, тобто директиви синхронізації і розподілу роботи можуть не входити безпосередньо в лексичний контекст паралельної області.

На даний момент технологія OpenMP підтримується більшістю компіляторів мови С / С + +. Дещо гірше справа йде з інструментами тестування паралельних OpenMP програм. Інструменти аналізу, перевірки та оптимізації паралельних програм хоча й існують давно, до недавнього часу були мало задіяні при розробці прикладного програмного забезпечення. Тому вони часто є менш зручними, ніж інші інструментальні засоби розробки. Найбільш повно процес розробки паралельних OpenMP програм підтриманий у пакеті Intel Parallel Studio. Є інструмент попереднього аналізу коду, для виявлення ділянок коду, які потенційно можна ефективно розпаралелить. Є добре оптимізуючий компілятор з підтримкою OpenMP. Є профіліровщики та інструмент динамічного аналізу для виявлення паралельних помилок. Додатково можна виділити інструмент VivaMP, що входить до складу PVS-Studio. Це статичний аналізатор коду, спеціалізований на виявленні помилок у OpenMP програмах на етапі їх написання.

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

Рис.

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

OpenMP простий у використанні і включає лише два базових типів конструкцій: директиви pragma і функції виконуючого середовища OpenMP. Директиви pragma, як правило, вказують компілятору реалізувати паралельне виконання фрагментів коду. Всі ці директиви починаються з # pragma omp. Як і будь-які інші директиви pragma, вони ігноруються компілятором, що не підтримують конкретну технологію — в даному випадку OpenMP. Функції OpenMP служать в основному для зміни і отримання параметрів середовища. Крім того, OpenMP включає API-функції для підтримки деяких типів синхронізації. Щоб задіяти ці функції, бібліотеки OpenMP, період виконання (виконуючого середовища), в програму потрібно включити заголовки omp.h. Для реалізації паралельного виконання блоків програми потрібно просто додати в код директиви pragma і, якщо потрібно, скористатися функціями бібліотеки OpenMP періоду виконання. Директиви pragma мають наступний формат:

#pragma omp <�директива> [розділ [ [,] розділ]. .]

Найважливіша і поширена директива — parallel. Вона створює паралельний регіон для наступного за нею структурованого блоку, наприклад:

# pragma omp parallel [розділ [[,] розділ ]. .] структурований блок Ця директива повідомляє компілятору, що структурований блок коду повинен бути виконаний паралельно, в декількох потоках. Кожен потік буде виконувати один і той же потік команд, але не один і той же набір команд — все залежить від операторів, керуючих логікою програми, таких як if-else. В якості прикладу розглянемо класичну програму «Hello World»:

#pragma omp parallel

{

printf («Hello Worldn»);

}

У двопроцесорній системі, звичайно ж, розраховували б отримати наступне:

Hello World

Hello World

Тим не менш, результат міг би бути й таким:

HellHell oo WorWlodrld

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

Розглянемо приклад, який визначає середні значення двох сусідніх елементів масиву і записує результати в інший масив. У цьому прикладі використовується OpenMP-конструкція # pragma omp for, яка відноситься до директив поділу роботи (work-sharing directive). Такі директиви застосовуються не для паралельного виконання коду, а для логічного розподілу групи потоків, щоб реалізувати вказані конструкції керуючої логіки.

Директива # pragma omp for повідомляє, що при виконанні циклу for в паралельному регіоні ітерації циклу повинні бути розподілені між потоками групи:

#pragma omp parallel

{

#pragma omp for

for (int i = 1; i < size; ++i)

x[i] = (y[i-1] + y[i+1])/2;

}

Якщо б цей код виконувався на чотирьох процесорному комп’ютері, а у змінній size було б значення 100, то виконання ітерацій 1−25 могло б бути доручено першому процесору, 26−50 — другому, 51−75 — третьому, а 76−99 — четвертим. Це характерно для політики планування, так званої статичної. Слід зазначити, що наприкінці паралельного регіону виконується бар'єрна синхронізація (barrier synchronization). Інакше кажучи, досягнувши кінця регіону, всі потоки блокуються до тих пір, поки останній потік не завершить свою роботу. Якщо з тільки що наведеного прикладу виключити директиву # pragma omp for, кожен потік виконає повний цикл for, проробивши багато зайвої роботи:

#pragma omp parallel

{

for (int i = 1; i < size; ++i)

x[i] = (y[i-1] + y[i+1])/2;

}

Так як цикли є найпоширенішими конструкціями, де виконання коду можна розпаралелить, OpenMP підтримує скорочений спосіб запису комбінації директив # pragma omp parallel і # pragma omp for:

#pragma omp parallel for

for (int i = 1; i < size; ++i)

x[i] = (y[i-1] + y[i+1])/2;

В цьому циклі немає залежностей, тобто одна ітерація циклу не залежить від результатів виконання інших ітерацій. А ось у двох наступних циклах є два види залежності:

for (int i = 1; i <= n; ++i) // цикл 1

a[i] = a[i-1] + b[i];

for (int i = 0; i < n; ++i) // цикл 2

x[i] = x[i+1] + b[i];

Розпаралелить цикл 1 проблематично тому, що для виконання ітерації i потрібно знати результат ітерації i-1, тобто ітерація i залежить від ітерації i-1. Розпаралелить цикл 2 теж проблематично, але з іншої причини. У цьому циклі можемо вирахувати значення x [i] до x [i-1], однак, зробивши так, ми більше не зможете обчислити значення x [i-1].

Спостерігається залежність ітерації i-1 від ітерації i. При розпаралелюванні циклів потрібно переконатися в тому, що ітерації циклу не мають залежностей. Якщо цикл не містить залежностей, компілятор може виконувати цикл в будь-якому порядку, навіть паралельно. Дотримання цієї важливої вимоги компілятор не перевіряє. Якщо ми вкажемо компілятору розпаралелить цикл, у якому є залежності, компілятор підкориться, що призведе до помилки. Крім того, OpenMP накладає обмеження на цикли for, які можуть бути включені в блок # pragma omp for або # pragma omp parallel for block. Цикли for повинні відповідати формату:

for ([цілочисельний тип] i = інваріант циклу; i {<,>,=,<=,>=} інваріант циклу; i {+,-}= інваріант циклу)

Ці вимоги введені для того, щоб OpenMP міг при вході в цикл визначити число ітерацій.

Порівняємо тільки що наведений приклад, що включає директиву # pragma omp parallel for, з кодом, який довелося б написати для вирішення тієї ж задачі на основі Windows API. Як видно в приклад 1, для досягнення того ж результату потрібно набагато більше коду. Так, конструктор класу ThreadData визначає, якими мають бути значення start і stop при кожному виклику потоку. OpenMP обробляє всі ці деталі сам і надає програмісту додаткові засоби конфігурування паралельних регіонів і коду.

Приклад 1. Багатопоточність в Win32 class ThreadData { public:

/ / Конструктор ініціалізує поля start і stop ThreadData (int threadNum); int start; int stop; }; DWORD ThreadFn (void * passedInData) { ThreadData * threadData = (ThreadData *) passedInData; for (int i = threadData-> start; i stop; + + i) x [i] = (y [i-1] + y [i +1]) / 2; return 0; }

void ParallelFor () {

/ / Запуск груп потоків for (int i = 0; i

int main (int argc, char * argv []) { / / Створення груп потоків for (int i = 0; i

Розробляючи паралельні програми, потрібно розуміти, які дані є загальними (shared), а які приватними (private), від цього залежить не тільки продуктивність, але і коректна робота програми. У OpenMP це розходження очевидно, до того ж існує можливість налаштовувати вручну. Загальні змінні доступні всім потокам з групи, тому зміни таких змінних в одному потоці видимі іншим потокам у паралельному регіоні. Що стосується приватних змінних, то кожен потік з групи має в своєму розпорядженні їх окремі екземпляри, тому зміни таких змінних в одному потоці ніяк не позначаються на їх екземплярах, що належать іншим потокам. За замовчуванням всі змінні в паралельному регіоні - загальні, але з цього правила є три винятки. По-перше, приватними є індекси паралельних циклів for. Наприклад, це відноситься до змінної i в коді, показаному в прикладі 2. Змінна j за замовчуванням не є приватною, але явно зроблена такою через розділ firstprivate.

Приклад 2. Розділи директив OpenMP і вкладений цикл for float sum = 10.0f; MatrixClass myMatrix; int j = myMatrix. RowStart (); int i; # pragma omp parallel { # pragma omp for firstprivate (j) lastprivate (i) reduction (+: sum) for (i = 0; i

По-друге, приватними є локальні змінні блоків паралельних регіонів. В прикладі 2 така змінна doubleI, тому що вона оголошена в паралельному регіоні. Будь-які нестатичні і які не є членами класу MatrixClass змінні, оголошені в методі myMatrix: GetElement, будуть приватними. По-третє, приватними будуть будь-які змінні, зазначені в розділах private, firstprivate, lastprivate і reduction. У прикладі 2 змінні i, j та sum зроблені приватними для кожного потоку з групи, тобто кожен потік буде розпоряджатися своєю копією кожної з цих змінних.

Кожен з названих розділів приймає список змінних, але семантика цих розділів розрізняється. Розділ private говорить про те, що для кожного потоку повинна бути створена приватна копія кожної змінної зі списку. Приватні копії будуть ініцилізуватись значенням за замовчуванням (із застосуванням конструктора за замовчуванням, якщо це доречно). Наприклад, змінні типу int мають за замовчуванням значення 0. У розділу firstprivate така ж семантика, але перед виконанням паралельного регіону він вказує копіювати значення приватної змінної в кожен потік, використовуючи конструктор копій, якщо це доречно. Семантика розділу lastprivate теж збігається з семантикою розділу private, але при виконанні останньої ітерації циклу або розділу конструкції розпаралелювання значення змінних, зазначених у розділі lastprivate, присвоюються змінним основного потоку. Якщо це доречно, для копіювання об'єктів застосовується оператор присвоювання копій (copy assignment operator). Схожа семантика і в розділу reduction, але він приймає змінну і оператор. Підтримувані цим розділом оператори перераховані в табл. 1, а у змінної повинен бути скалярний тип (наприклад, float, int або long, але не std: vector, int [] і т. д.). Змінна розділу reduction ініціалізується в кожному потоці значенням, зазначеним у таблиці. В кінці блоку коду оператор розділу reduction застосовується до кожної приватної копії змінної, а також до початкового значення змінної.

Таблиця

В прикладі 2 змінна sum неявно ініціалізується в кожному потоці значенням 0.0f (в таблиці вказано канонічне значення 0, але в даному випадку воно приймає форму 0.0f, так як sum має тип float). Після виконання блоку # pragma omp for над усіма приватними значеннями і вихідним значенням sum (яке в нашому випадку дорівнює 10.0f) виконується операція +. Результат присвоюється вихідний загальній змінній sum.

Як правило, OpenMP використовується для розпаралелювання циклів, але OpenMP підтримує паралелізм і на рівні функцій. Цей механізм називається секціями OpenMP (OpenMP sections). Він досить простий і часто буває корисний. Розглянемо один з найбільш важливих алгоритмів у програмуванні - швидке сортування (quicksort). Як приклад реалізуємо рекурсивний метод швидкого сортування списку цілих чисел. Заради простоти не створюємо універсальну шаблонну версію методу, але суть справи від цього анітрохи не змінюється. Код методу, реалізованого з використанням секцій OpenMP, показаний в приклад 3 (код методу Partition опущений, щоб не захаращувати загальну картину).

Приклад 3. Швидке сортування з використанням паралельних секцій void QuickSort (int numList [], int nLower, int nUpper) { if (nLower

У даному прикладі перша директива # pragma створює паралельний регіон секцій. Кожна секція визначається директивою # pragma omp section. Кожній секції в паралельному регіоні ставиться у відповідність один потік з групи потоків, і всі секції виконуються одночасно. У кожній секції рекурсивно викликається метод QuickSort. Як і у випадку конструкції # pragma omp parallel for, потрібно переконатися в незалежності секцій один від одного, щоб вони могли виконуватися паралельно. Якщо в секціях змінюються загальні ресурси без синхронізації доступу до них, результат може виявитися непередбачуваним. В цьому прикладі використовується скорочення # pragma omp parallel sections, аналогічне конструкції # pragma omp parallel for. За аналогією з # pragma omp for директиву # pragma omp sections можна використовувати в паралельному регіоні окремо. Паралельні секції викликаються рекурсивно. Рекурсивні виклики підтримуються і паралельними регіонами, і паралельними секціями. Якщо створення вкладених секцій дозволено, в міру рекурсивних викликів QuickSort будуть створюватися все нові й нові потоки. Можливо, це не те, що потрібно програмісту, тому що такий підхід може призвести до створення великого числа потоків. Щоб обмежити число потоків, в програмі можна заборонити вкладення. Тоді наш додаток буде рекурсивно викликати метод QuickSort, використовуючи тільки два потоки. При компіляції цього додатка без параметра / openmp буде згенерована коректна послідовна версія. Одна з переваг OpenMP в тому, що ця технологія сумісна з компіляторами, що не підтримують OpenMP.

При одночасному виконанні декількох потоків часто виникає необхідність їх синхронізації. OpenMP підтримує кілька типів синхронізації, котрі допомагають у багатьох ситуаціях. Один з типів — неявна бар'єрна синхронізація, яка виконується в кінці кожного паралельного регіону для всіх зіставлених з ним потоків. Механізм бар'єрної синхронізації такий, що, поки всі потоки не досягнуть кінця паралельного регіону, жоден потік не зможе перейти його кордон. Неявна бар'єрна синхронізація виконується також у кінці кожного блоку # pragma omp for, # pragma omp single і # pragma omp sections. Щоб відключити неявну бар'єрну синхронізацію в будь-якому з цих трьох блоків поділу роботи, вкажіть розділ nowait:

#pragma omp parallel

{

#pragma omp for nowait

for (int i = 1; i < size; ++i)

x[i] = (y[i-1] + y[i+1])/2;

}

Крім вже описаних директив OpenMP підтримує ряд корисних підпрограм. Вони діляться на три великих категорії: функції виконуючого середовища, блокування / синхронізації і роботи з таймерами. Всі ці функції мають імена, що починаються з omp_, і визначені в заголовному файлі omp.h.

Підпрограми першої категорії дозволяють запитувати і ставити різні параметри операційного середовища OpenMP. Функції, імена яких починаються на omp_set_, можна викликати тільки поза паралельних регіонів. Всі інші функції можна використовувати як в середині паралельних регіонів, так і поза ними. Щоб дізнатися або задати число потоків у групі, використовують функції omp_get_num_threads і omp_set_num_threads. Перша повертає число потоків, що входять в поточну групу потоків. Якщо викликає потік виконується не в паралельному регіоні, ця функція повертає 1. Метод omp_set_num_thread задає число потоків для виконання наступного паралельного регіону, який зустрінеться поточному виконуваному потоку. Крім того, число потоків, використовуваних для виконання паралельних регіонів, залежить від двох інших параметрів середовища OpenMP: підтримки динамічного створення потоків і вкладення регіонів.Підтримка динамічного створення потоків визначається значенням булевого значення, яке за замовчуванням дорівнює false.

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

Вкладення паралельних регіонів також визначається булевим властивістю, яке за замовчуванням встановлено в false. Вкладення паралельних регіонів відбувається, коли поток, вже виконує паралельний регіон, зустрічається інший паралельний регіон. Якщо вкладення дозволено, створюється нова група потоків, при цьому дотримуються правила, описані раніше. А якщо вкладення не дозволено, формується група, що містить один потік. Для установки і читання властивостей, що визначають можливість динамічного створення потоків і вкладення паралельних регіонів, служать функції omp_set_dynamic, omp_get_dynamic, omp_set_nested і omp_get_nested. Крім того, кожен потік може запросити інформацію про своє середовище. Щоб дізнатися номер потоку в групі потоків, потрібно викликати omp_get_thread_num. Необхідно пам’ятати, що вона повертає не Windows-ідентифікатор потоку, а число в діапазоні від 0 до omp_get_num_threads — 1. Функція omp_in_parallel дозволяє потоку дізнатися, чи виконує він в даний час паралельний регіон, а omp_get_num_procs повертає число процесорів в комп’ютері. У прикладі 4 ми реалізували чотири окремі паралельних регіону і два вкладених.

Приклад 4. Використання підпрограм виконуючого середовища OpenMP # include # include int main () { omp_set_dynamic (1); omp_set_num_threads (10); # pragma omp parallel / / паралельний регіон 1 { # pragma omp single printf («Num threads in dynamic region is =% d n», omp_get_num_threads ()); } printf («n»); omp_set_dynamic (0); omp_set_num_threads (10); # pragma omp parallel / / паралельний регіон 2 { # pragma omp single printf («Num threads in non-dynamic region is =% d n», omp_get_num_threads ()); } printf («n»); omp_set_dynamic (1); omp_set_num_threads (10); # pragma omp parallel / / паралельний регіон 3 { # pragma omp parallel { # pragma omp single printf («Num threads in nesting disabled region is =% d n», omp_get_num_threads ()); } } printf («n»); omp_set_nested (1); # pragma omp parallel / / паралельний регіон 4 { # pragma omp parallel { # pragma omp single printf («Num threads in nested region is =% d n», omp_get_num_threads ()); } } }

Скомпілювавши цей код і виконавши його на звичайному двопроцесорної комп’ютері, отримуємо такий результат:

Num threads in dynamic region is = 2

Num threads in non-dynamic region is = 10

Num threads in nesting disabled region is = 1

Num threads in nesting disabled region is = 1

Num threads in nested region is = 2

Num threads in nested region is = 2

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

У третьому паралельному регіоні вкладення було відключено, тому для вкладеного паралельного регіону не було створено жодних нових потоків — і зовнішній, і вкладений паралельні регіони виконувалися двома потоками. У четвертому паралельному регіоні, де вкладення було включено, для вкладеного паралельного регіону була створена група з двох потоків (тобто в цілому цей регіон виконувався чотирма потоками). Процес подвоєння числа потоків для кожного вкладеного паралельного регіону може тривати, поки не вичерпається простір в стеку. На практиці можна створити кілька сотень потоків, хоча пов’язані з цим витрати легко переважать будь-які переваги.

OpenMP включає і функції, призначені для синхронізації коду. У OpenMP два типи блокувань: прості і вкладені (nestable); блокування обох типів можуть знаходитися в одному з трьох станів — неініціалізованому, заблокованому і розблокованому. Прості блокування (omp_lock_t) не можуть бути встановлені більше одного разу, навіть тим самим потоком. Вложені блокування (omp_nest_lock_t) ідентичні простим з тим винятком, що, коли потік намагається встановити вже приналежну йому вкладене блокування, він не блокується. Крім того, OpenMP веде облік посилань на вкладені блокування і стежить за тим, скільки разів вони були встановлені. OpenMP надає підпрограми, що виконують операції над цими блокуваннями. Кожна така функція має два варіанти: для простих і для вкладених блокувань. Можна виконати над блокуванням п’ять дій: ініціалізувати її, встановити (захопити), звільнити, перевірити і знищити. Всі ці операції дуже схожі на Win32-функції для роботи з критичними секціями, і це не випадковість: насправді технологія OpenMP реалізована як оболонка цих функцій. Відповідність між функціями OpenMP і Win32 ілюструє табл. 2.

Таблиця

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

В прикладі 5 показано код двох паралельно виконуваних циклів, на початку яких виконуючому середовищі невідома кількість їх ітерацій. У першому прикладі виконується перебір елементів STL-контейнера std: vector, а в другому — стандартного звязаного списку.

Приклад 5. Виконання заздалегідь невідомого числа ітерацій

# pragma omp parallel { / / Паралельна обробка вектора STL std: vector: iterator iter; for (iter = xVect. begin (); iter! = xVect. end (); + + iter) { # pragma omp single nowait { process1 (* iter); } } / / Паралельна обробка стандартного пов’язаного списку for (LList * listWalk = listHead; listWalk! = NULL; listWalk = listWalk-> next) { # pragma omp single nowait { process2 (listWalk); } } }

У прикладі з вектором STL кожен потік з групи потоків виконує цикл for і має власний примірник ітератора, але при кожній ітерації лише один потік входить в блок single (така семантика директиви single). Всі дії, що гарантують одноразове виконання блоку single при кожній ітерації, бере на себе виконуюче середовище OpenMP. Такий спосіб виконання циклу пов’язаний зі значними витратами, тому він корисний, тільки якщо у функції process1 виконується багато роботи. У прикладі зі зв’язаним списком реалізована та ж логіка. Варто відзначити, що в прикладі з вектором STL ми можемо до входу в цикл визначити число його ітерацій за значенням std: vector. size, що дозволяє привести цикл до канонічної форми для OpenMP:

# pragma omp parallel for for (int i = 0; i

Це суттєво зменшує витрати в період виконання, і саме такий підхід найкраще застосовувати для обробки масивів, векторів і будь-яких інших контейнерів, елементи яких можна перебрати в циклі for, відповідно канонічній формі для OpenMP.

За умовчанням в OpenMP для планування паралельного виконання циклів for застосовується алгоритм, так званий статичним плануванням (static scheduling). Це означає, що всі потоки з групи виконують однакове число ітерацій циклу. Якщо n — число ітерацій циклу, а T — число потоків у групі, кожний потік виконає n / T ітерацій (якщо n не ділиться на T без залишку, нічого страшного). Однак OpenMP підтримує й інші механізми планування, оптимальні в різних ситуаціях: динамічне планування (dynamic scheduling), планування в період виконання (runtime scheduling) і кероване планування (guided scheduling). Щоб задати один з цих механізмів планування, використовують розділ schedule в директиві # pragma omp for або # pragma omp parallel for. Формат цього розділу виглядає так:

schedule (алгоритм планирования[, число итераций])

Ось приклади цих директив: # pragma omp parallel for schedule (dynamic, 15) for (int i = 0; i <100; + + i) … # pragma omp parallel # pragma omp for schedule (guided)

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

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

Необхідно зазначити, що OpenMP — не панацея від всіх бід. Ця технологія орієнтована в першу чергу на розробників високопродуктивних обчислювальних систем і найбільш ефективна, якщо код включає багато циклів і працює з розділеними масивами даних. Створення як звичайних потоків, так і паралельних регіонів OpenMP має свою ціну. Щоб застосування OpenMP стало вигідним, виграш у швидкості, що забезпечується паралельним регіоном, повинен перевершувати витрати на створення групи потоків. У версії OpenMP, реалізованої в Visual C + +, група потоків створюється при вході в перший паралельний регіон. Після завершення регіону група потоків призупиняється, поки не знадобиться знову. За лаштунками OpenMP використовує пул потоків Windows. Рис. 2 ілюструє приріст швидкодії простої програми, який досягається завдяки OpenMP на двопроцесорному комп’ютері при різній кількості ітерацій. Максимальний приріст швидкодії становить приблизно 1,7 від вихідного, що типово для двопроцесорних систем.

Рис.

На даному графіку вісь «y» представляє відношення часу послідовного виконання коду до часу паралельного виконання того ж коду. Паралельна версія наздоганяє за швидкодією послідовну приблизно при 5000 ітерацій, але це поганий сценарій. Більшість паралельних циклів будуть виконуватися швидше послідовних навіть при значно меншій кількості ітерацій. Це залежить від обсягу роботи, виконуваної на кожній ітерації.

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

На завершення відзначимо кілька моментів, серед яких варто особливо підкреслити два. По-перше, технологія спочатку спроектована таким чином, щоб користувач міг працювати з єдиним текстом для паралельної і послідовної програм. Справді, звичайний компілятор на послідовній машині директиви OpenMP просто «не помічає. Єдиним джерелом проблем можуть стати змінні оточення і спеціальні функції, однак для них у специфікаціях стандарту передбачені спеціальні «заглушки «, що гарантують коректну роботу OpenMP-програми в послідовному випадку, потрібно тільки перекомпілювати програму і підключити іншу бібліотеку. Іншою перевагою OpenMP є можливість поступового, «інкрементного» ??розпаралелювання програми. Взявши за основу послідовний код, користувач крок за кроком додає нові директиви, що описують нові паралельні секції. Немає необхідності відразу писати паралельну програму, її створення ведеться послідовно, що спрощує і процес програмування, і налагодження.

OpenMP — проста, але потужна технологія розпаралелювання програм. Вона дозволяє реалізувати паралельне виконання як циклів, так і функціональних блоків коду. Вона легко інтегрується в існуючі програми і включається / вимикається одним параметром компілятора. OpenMP дозволяє більш повно використовувати обчислювальну потужність багатоядерних процесорів.

Поради коли використовувати технологію OpenMP:

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

Ш Програма повина бути кросплатформенною. OpenMP — багатоплатформовий і широко підтримуваний API. А так як він реалізований на основі директив pragma, програму можна скомпілювати навіть за допомогою компілятора, який не підтримує стандарт OpenMP.

Ш Виконання циклів потрібно розпаралелить. Весь свій потенціал OpenMP демонструє при організації паралельного виконання циклів. Якщо в програмі є тривалі цикли без залежностей, OpenMP — ідеальне рішення.

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

Бібліографічний список

1.http://openmp.org/

2.http://ru.wikipedia.org/wiki/OpenMP

3.http://bisqwit.iki.fi/story/howto/openmp/

4.http://msdn.microsoft.com/en-us/magazine/cc163717.aspx

5.http://www.viva64.com/ru/r/tag/parallel-programming/

6.http://parallel.ru/tech/tech_dev/openmp.html

7.http://www.viva64.com/ru/t/0037/

8.http://citforum.ru/hardware/arch/lectures/6.shtml

9.https://computing.llnl.gov/tutorials/openMP/

10.http://www.dtf.ru/articles/read.php?id=55 038

11.http://incursion.tk/?p=403