Синхронізація в OpenMP

Синхронізація в OpenMP

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

Самим простим способом захистити дані від можливих проблем, пов'язаних з одночасним доступом, є директива atomic. Ця директива застосовується до оператору-виразу одного з наступних типів: x op = expr;

x ++;

++ x;

x ––;

–– x;

де x — змінна, expr — вираз, що не посилається на x, op — бінарна операція. Дана директива забезпечує атомарність відповідної операції: в момент виконання цієї операції одним із потоків інші потоки не мають доступу до змінної х. Іншим базовим механізмом синхронізації є механізм критичних секцій. Критична секція в коді програми виділяється за допомогою директиви critical, яка має наступний синтаксис:

#pragma omp critical [name]

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

В деяких випадках потрібно обмежити набір потоків, що виконують деякий фрагмент коду. Це досягається за допомогою директиви master, що має наступний синтаксис:

#pragma omp master

Оператор, до якого застосовується дана директива, виконується тільки головним потоком.

Розпаралелювання циклів

Більша частина часу роботи застосунків приходиться на циклічні ділянки. Тому прискоренню роботи таких ділянок за допомогою розпаралелювання приділяється велика увага. — private(list)

— firstprivate(list)

— lastprivate(list)

— reduction(operator: list)

— schedule(kind[, chunk_size])

— collapse(n)

— ordered

— nowait

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

#pragma omp for [клауза[[,] клауза] ...]

for (init-expr; test-expr; incr-expr) структурний блок {…} де опція (клауза) одна з:

При цьому: init-expr — або var = lb (ліва межа), або integer-type var = lb;

test-expr — var rel b, де var — змінна знакового цілого типу, rel — одна з наступних операцій порівняння: ‘<’, ‘<=’, ‘>’, ‘>=’. incr-expr — один з наступних виразів:

++var var++ –– var var–– var += incr var –=incr var = var + incr var = incr + varvar = var — incr 

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

Директива for повинна виконуватись всередині паралельної ділянки. Передбачена також директива parallel for, яка надає можливість поєднання функціональностя директив parallel та for в одній директиві. В результаті виконання цієї директиви створюється паралельна ділянка виконання та ітерації циклу розподіляються між потоками, що виконуються в цій ділянці.

Як приклад застосування директиви for розглянемо частину програми обчислення поелементної суми двох векторів. Спочатку розглянемо послідовну функцію обчислення суми двох векторів:

void vsum(int n, double* a, doubl* b, doubl* c){ int i; for (i = 0; i < n; i++) c[i] = a[i] + b[i]; } 

Функція приймає наступні параметри: n — розмірність вектора; a, b — вектори, що додаються; c — результат.

Ітерації циклу не мають інформаційних залежностей, так як на кожній наступній ітерації обробляються нові елементи масивів a, b, c. Тому до нього можна застосувати директиву for:

void vsum(int n, double* a, doubl* b, doubl* c){ int i; #pragma omp for for (i = 0; i < n; i++) c[i] = a[i] + b[i]; } 

Стратегія розподілу ітерацій циклу по потокам

Ітерації циклу, до якого застосована директива for, можуть по-різному розподілятись по потокам. Для розподілу ітерацій циклу по потокам можна використовувати клаузу schedule директиви for. Дана опція передбачає два аргументи. Перший визначає спосіб розподілу ітерацій. Другий необов'язковий аргумент задає число ітерацій в порції, яка слугує одиницею розподілу навантаження. Синтаксис цієї клаузи — schedule(алгоритм планування[,число_ітерацій]), де алгоритм планування один з:

— schedule(static[, число_ітерацій]) — статичне планування;

— schedule(dynamic[, число_ітерацій]) — динамічне планування;

— schedule(guided[, число_ітерацій]) — кероване планування;

— schedule(runtime) — планування в період виконання. Спосіб розподілу витків циклу між нитями буде задано під час виконання програми;

— schedule(auto) — автоматичне планування (OpenMP 3.0). Спосіб розподілу витків циклу між нитями визначається реалізацією компілятору. На етапі компіляції програми або під час її виконання визначається оптимальний спосіб розподілу. schedule(static[, число_ітерацій]):

#pragma omp parallel for schedule(static, 10) for(int i = 1; i <= 100; i++) 

Результат виконання програми на 4-х ядерному процесорі буде наступним: — Потік 0 отримує право на виконання ітерацій 1-10, 41-50, 81-90.

— Потік 1 отримує право на виконання ітерацій 11-20, 51-60, 91-100.

— Потік 2 отримує право на виконання ітерацій 21-30, 61-70.

— Потік 3 отримує право на виконання ітерацій 31-40, 71-80.

schedule(dynamic[, число_ітерацій]):

#pragma omp parallel for schedule(dynamic, 15)

Результат виконання програми на 4-х ядерному процесорі може бути наступним:

— Потік 0 отримує право на виконання ітерацій 1-15.

— Потік 1 отримує право на виконання ітерацій 16-30.

— Потік 2 отримує право на виконання ітерацій 31-45.

— Потік 3 отримує право на виконання ітерацій 46-60.

— Потік 3 завершує виконання ітерацій.

— Потік 3 отримує право на виконання ітерацій 61-75.

— Потік 2 завершує виконання ітерацій.

— Потік 2 отримує право на виконання ітерацій 76-90.

— Потік 0 завершує виконання ітерацій.

— Потік 0 отримує право на виконання ітерацій 91-100.

schedule(guided[, число_ітерацій]):

#pragma omp parallel for schedule(guided, 10) for(int i = 1; i <= 100; i++) 

число_виконуваних_потоком_ітерацій = max(число_нерозподілених_ітерацій/omp_get_num_threads(), число_ітерацій).

Нехай програма запущена на 4-х ядерному процесорі:

— Потік 0 отримує право на виконання ітерацій 1-25.

— Потік 1 отримує право на виконання ітерацій 26-44.

— Потік 2 отримує право на виконання ітерацій 45-59.

— Потік 3 отримує право на виконання ітерацій 60-69.

— Потік 3 завершує виконання ітерацій.

— Потік 3 отримує право на виконання ітерацій 70-79.

— Потік 2 завершує виконання ітерацій.

— Потік 2 отримує право на виконання ітерацій 80-89.

— Потік 3 завершує виконання ітерацій.

— Потік 3 отримує право на виконання ітерацій 90-99.

— Потік 1 завершує виконання ітерацій.

— Потік 1 отримує право на виконання 100-ї ітерації.

Примітки

1. Корнеев В. В. Параллельные вычислительные системы. М.: Нолидж, 1999
2. Воеводин В. В. Математические основы параллельных вычислений.- М.: Изд-во МГУ, 1991.
3. С. Немнюгин, О.Стесик Параллельное программирование для многопроцессорных обчислювальних систем. — СПб: БХВ-Петербург, 2002.

Література

1. Корнеев В. В. Параллельные вычислительные системы[1]. М.: Нолидж, 1999
2. Воеводин В. В. Математические основы параллельных вычислений[2].- М.: Изд-во МГУ, 1991.
3. С. Немнюгин, О.Стесик Параллельное программирование для многопроцессорных обчислювальних систем[3]. — СПб: БХВ-Петербург, 2002.