трспо. Лекція Колективні операції обміну повідомленнями в mpi
 Скачать 3.37 Mb.
|
|
3.2. Паралельна обробка в конструкціях, відмінних від циклів Як правило, OpenMP використовується для розпаралелювання циклів, але OpenMP підтримує паралелізм і на рівні функцій. Цей механізм називається секціями OpenMP (OpenMP sections). Він досить простий і часто буває корисний. Розглянемо один з найважливіших алгоритмів в програмуванні – швидке сортування (quicksort). Як приклад реалізований рекурсивний метод швидкого сортування списку цілих чисел. Заради простоти приведена спрощена версія методу, але суть справи від цього анітрохи не змінюється. Код методу, реалізованого з використанням секцій OpenMP, показаний в лістингу 3 (код методу Partition опущений, щоб не захаращувати загальну картину). Лістинг 3. Швидке сортування з використанням паралельних секцій void QuickSort (int numList [], int nLower, int nUpper) { if (nLower // Розбиття інтервалу сортування int nSplit = Partition (numList, nLower, nUpper); #pragma omp parallel sections { #pragma omp section QuickSort (numList, nLower, nSplit - 1); #pragma omp section QuickSort (numList, nSplit, nUpper); } } } В даному прикладі перша директива #pragma створює паралельний регіон секцій. Кожна секція визначається директивою #pragma omp section. Кожній секції в паралельному регіоні ставиться у відповідність один потік з групи потоків, і все секції виконуються одночасно. У кожній секції рекурсивно викликається метод QuickSort. Як і в випадку конструкції #pragma omp parallel for, ви самі повинні переконатися в незалежності секцій однієї від іншої, щоб вони могли виконуватися паралельно. Якщо в секціях змінюються спільні ресурси без синхронізації доступу до них, результат може виявитися непередбачуваним. У цьому прикладі використовується скорочення #pragma omp parallel sections, аналогічне конструкції #pragma omp parallel for. За аналогією з #pragma omp for директиву #pragma omp sections можна використовувати в паралельному регіоні окремо. Перш за все зауважте, що в лістингу 3 паралельні секції викликаються рекурсивно. Рекурсивні виклики підтримуються і паралельними регіонами, і (як в нашому прикладі) паралельними секціями. Якщо створення вкладених секцій дозволено, у міру рекурсивних викликів QuickSort будуть створюватися всі нові і нові потоки. Можливо, це не те, що потрібно програмісту, так як такий підхід може призвести до створення великого числа потоків. Щоб обмежити число потоків, в програмі можна заборонити вкладення. Тоді наш додаток буде рекурсивно викликати метод QuickSort, використовуючи тільки два потоки. При компіляції цієї програми без параметра / openmp буде згенеровано коректна послідовна версія. Одна з переваг OpenMP в тому, що ця технологія сумісна з компіляторами, що не підтримують OpenMP. 4. Управління потоками 4.1. Директиви pragma для синхронізації При одночасному виконанні декількох потоків часто виникає необхідність їх синхронізації. OpenMP підтримує кілька типів синхронізації, які допомагають у багатьох ситуаціях. Один з типів – неявна бар'єрна синхронізація, яка виконується в кінці кожного паралельного регіону для всіх зіставлених з ним потоків. Механізм бар'єрної синхронізації такий, що, поки все потоки не досягнуть кінця паралельного регіону, жоден потік не зможе перейти його кордон. Неявна бар'єрна синхронізація виконується також в кінці кожного блоку #pragma omp for, #pragma omp single і #pragma omp sections. Щоб відключити неявну бар'єрну синхронізацію в будь-якому з цих трьох блоків розподілу роботи, вкажіть розділ nowait: #pragma omp parallel { #pragma omp for nowait for (int i = 1; i Цей розділ директиви розпаралелювання говорить про те, що синхронізувати потоки в кінці циклу for не треба, хоча в кінці паралельного регіону вони все ж будуть синхронізовані. Другий тип – явна бар'єрна синхронізація. У деяких ситуаціях її доцільно виконувати поряд з неявній. Для цього включіть в код директиву #pragma omp barrier. Як бар'єрів можна використовувати критичні секції. У Win32 API для входу в критичну секцію і виходу з неї служать функції EnterCriticalSection і LeaveCriticalSection. У OpenMP для цього застосовується директива #pragma omp critical [ім'я]. Вона має таку ж семантику, що і критична секція Win32, і спирається на EnterCriticalSection. Ви можете використовувати іменовану критичну секцію, і тоді доступ до блоку коду є взаємовиключним тільки для інших критичних секцій з тим же ім'ям (це справедливо для всього процесу). Якщо ім'я не вказано, директива ставиться у відповідність якомусь імені, обирається системою. Доступ до всіх неіменованого критичним секціях є взаємовиключним. У паралельних регіонах часто зустрічаються блоки коду, доступ до яких бажано надавати тільки одному потоку, – наприклад, блоки коду, що відповідають за запис даних в файл. У багатьох таких ситуаціях не має значення, який потік виконає код, важливо лише, щоб цей потік був єдиним. Для цього в OpenMP служить директива #pragma omp single. Іноді можливостей директиви single недостатньо. У ряді випадків потрібне, щоб блок коду був виконаний основним потоком, – наприклад, якщо цей потік відповідає за обробку GUI і вам потрібно, щоб якесь завдання виконав саме він. Тоді застосовується директива #pragma omp master. На відміну від директиви single при вході в блок master і виході з нього немає ніякого неявного бар'єру. Щоб завершити всі незавершені операції над пам'яттю перед початком наступної операції, використовуйте директиву #pragma omp flush, яка еквівалентна внутрішньої функції компілятора _ReadWriteBarrier. OpenMP-директиви pragma повинні оброблятися всіма потоками з групи в одному порядку (або взагалі не оброблятися ніякими потоками). Таким чином, наступний приклад коду некоректний, а передбачити результати його виконання не можна (можливі варіанти - збій або зависання системи): #pragma omp parallel { if (omp_get_thread_num ()> 3) { #pragma omp single // код, доступний не всім потокам x ++; } } 4.2. Підпрограми середовища OpenMP що виконується Крім вже описаних директив 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 { 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 ()); } } } Скомпілювавши цей код в Visual Studio і виконавши його на звичайному двопроцесорним комп'ютері, ми отримали такий результат: 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 потоків, тому що динамічне створення потоків для цього регіону було відключено. Результати виконання третього і четвертого паралельних регіонів ілюструють слідства включення і відключення можливості вкладення регіонів. У третьому паралельному регіоні вкладення було відключено, тому для вкладеного паралельного регіону не було створено ніяких нових потоків - і зовнішній, і вкладений паралельні регіони виконувалися двома потоками. У четвертому паралельному регіоні, де вкладення було включено, для вкладеного паралельного регіону була створена група з двох потоків (т. ч. в цілому цей регіон виконувався чотирма потоками). Процес подвоєння числа потоків для кожного вкладеного паралельного регіону може тривати, поки ви не вичерпаєте простір в стеці. На практиці можна створити кілька сотень потоків, хоча пов'язані з цим витрати легко переважать будь-які переваги. Як ви, мабуть, помітили, для третього і четвертого паралельних регіонів динамічне створення потоків було включено. Подивимося, що буде, якщо виконати той же код, відключивши динамічне створення потоків: omp_set_dynamic (0); omp_set_nested (1); omp_set_num_threads (10); #pragma omp parallel { #pragma omp parallel { #pragma omp single printf ( "Num threads in nested region is =% d \ n", omp_get_num_threads ()); } } А відбувається те, чого і слід було очікувати. Для першого паралельного регіону створюється група з 10 потоків, потім при вході у вкладений паралельний регіон для кожного з цих 10 потоків створюється група також з 10 потоків. В цілому вкладений паралельний регіон виконують 100 потоків: Num threads in nested region is = 10 Num threads in nested region is = 10 Num threads in nested region is = 10 Num threads in nested region is = 10 Num threads in nested region is = 10 Num threads in nested region is = 10 Num threads in nested region is = 10 Num threads in nested region is = 10 Num threads in nested region is = 10 Num threads in nested region is = 10 4.3 Методи синхронізації / блокування OpenMP включає і функції, призначені для синхронізації коду. У OpenMP два типи блокувань: прості і вкладені (nestable); блокування обох типів можуть перебувати в одному з трьох станів – неініціалізованих, заблокованому і розблокованому. Прості блокування (omp_lock_t – тип даних, який містить стан блокування, доступність блокування або приналежність потоку до блокування) не можуть бути встановлені більш ніж один раз, навіть тим же потоком. Вкладені блокування (omp_nest_lock_t) ідентичні простим з тим винятком, що, коли потік намагається встановити вкладене блокування, що вже належить йому, він не блокується. Крім того, OpenMP веде облік посилань на вкладені блокування і стежить за тим, скільки разів вони були встановлені. OpenMP надає підпрограми, які виконують операції над цими блокуваннями. Кожна така функція має два варіанти: для простих і для вкладених блокувань. Ви можете виконати над блокуванням п'ять дій: форматувати її, встановити (захопити), звільнити, перевірити і знищити. Всі ці операції дуже схожі на Win32-функції для роботи з критичними секціями, і це не випадковість: насправді технологія OpenMP реалізована як оболонка цих функцій. Відповідність між функціями OpenMP і Win32 ілюструє табл. 2. Табл. 2. Функції для роботи з блокуваннями в OpenMP і Win32 Просте блокування OpenMP Вкладене блокування OpenMP Win32-функція omp_lock_t omp_nest_lock_t CRITICAL_SECTION omp_init_lock omp_init_nest_lock InitializeCriticalSection omp_destroy_lock omp_destroy_nest_lock DeleteCriticalSection omp_set_lock omp_set_nest_lock EnterCriticalSection omp_unset_lock omp_unset_nest_lock LeaveCriticalSection omp_test_lock omp_test_nest_lock TryEnterCriticalSection Для синхронізації коду можна використовувати і підпрограми виконуючого середовища, і директиви синхронізації. Перевага директив в тому, що вони прекрасно структуровані. Це робить їх більш зрозумілими і полегшує пошук місць входу в синхронізовані регіони і виходу з них. Перевага підпрограм виконуючого середовища – гнучкість. Наприклад, ви можете передати блокування в іншу функцію і встановити / звільнити її в цій функції. При використанні директив це неможливо. Як правило, якщо вам не потрібна гнучкість, що забезпечується лише подпрограммами виконуючого середовища, краще використовувати директиви синхронізації. 4.3.1 Паралельна обробка структур даних У лістингу 5 показаний код двох паралельно виконуваних циклів, на початку яких виконує середовищі невідомо число їх ітерацій. У першому прикладі виконується перебір елементів STL-контейнера std :: vector, а в другому – стандартного пов'язаного списку. Лістинг 5. Виконання заздалегідь невідомого числа ітерацій #pragma omp parallel { // Паралельна обробка вектора STL std :: vector { #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. 4.4. Більш складні алгоритми планування За замовчуванням в 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. Після того як потік завершить виконання заданих ітерацій, він переходить до наступного набору ітерацій. Так триває, поки не будуть пройдені всі ітерації. Останній набір ітерацій може бути менше, ніж спочатку заданий. При керованому плануванні число ітерацій, виконуваних кожним потоком, визначається за такою формулою: число_вивиконуємих_потоком_ітерацій = max (число_нерозподілених / omp_get_num_threads (), число ітерацій) Завершивши виконання призначених ітерацій, потік запитує виконання іншого набору ітерацій, число яких визначається по щойно наведеною формулою. Таким чином, число ітерацій, що призначаються кожному потоку, з часом зменшується. Останній набір ітерацій може бути менше, ніж значення, обчислене за формулою. Якщо вказати директиву #pragma omp for schedule (dynamic, 15), цикл for з 100 ітерацій може бути виконаний чотирма потоками в такий спосіб: Потік 0 отримує право на виконання ітерацій 1-15 Потік 1 отримує право на виконання ітерацій 16-30 Потік 2 отримує право на виконання ітерацій 31-45 Потік 3 отримує право на виконання ітерацій 46-60 Потік 2 завершує виконання ітерацій Потік 2 отримує право на виконання ітерацій 61-75 Потік 3 завершує виконання ітерацій Потік 3 отримує право на виконання ітерацій 76-90 Потік 0 завершує виконання ітерацій Потік 0 отримує право на виконання ітерацій 91-100 А ось яким може виявитися результат виконання того ж циклу чотирма потоками, якщо буде вказана директива #pragma omp for schedule (guided, 15): Потік 0 отримує право на виконання ітерацій 1-25 Потік 1 отримує право на виконання ітерацій 26-44 Потік 2 отримує право на виконання ітерацій 45-59 Потік 3 отримує право на виконання ітерацій 60-64 Потік 2 завершує виконання ітерацій Потік 2 отримує право на виконання ітерацій 65-79 Потік 3 завершує виконання ітерацій Потік 3 отримує право на виконання ітерацій 80-94 Потік 2 завершує виконання ітерацій Потік 2 отримує право на виконання ітерацій 95-100 Динамічне і кероване планування добре підходять, якщо при кожній ітерації виконуються різні обсяги роботи або якщо одні процесори більш продуктивні, ніж інші. При статичному плануванні немає ніякого способу, що дозволяє збалансувати навантаження на різні потоки. При динамічному і керованому плануванні навантаження розподіляється автоматично – така сама суть цих підходів. Як правило, при керованому плануванні код виконується швидше, ніж при динамічному, внаслідок менших витрат на планування. Останній підхід – планування в період виконання – це скоріше навіть не алгоритм планування, а спосіб динамічного вибору одного з трьох описаних алгоритмів. Якщо в розділі schedule вказано параметр runtime, виконуючого середовища OpenMP використовує алгоритм планування, заданий для конкретного циклу for за допомогою змінної OMP_SCHEDULE. Вона має формат «тип [, число ітерацій]», наприклад: set OMP_SCHEDULE = dynamic, 8 Планування в період виконання дає певну гнучкість у виборі типу планування, при цьому за замовчуванням застосовується статичне планування. |