Система автоматизації розпаралелювання відображення на мультипроцесор

Анотація

Мета даної роботи - розробка і реалізація алгоритмів блоку "Експерт для мультипроцесора" у проекті "Експериментальна система автоматизації розпаралелювання". На підставі результатів аналізу послідовної програми і характеристик конкретного мультипроцесора "Експерт" генерує і оцінює різні варіанти розподілу обчислень і локалізацій даних. Після вибору найкращого варіанту він вставляє в послідовну програму директиви OpenMP, за допомогою яких вона перетворюється в паралельну програму для мультипроцесора. Крім того, експерт видає інформацію про прогнозованої ефективності розпаралелювання.

1. Введення

1.1 Розпаралелювання програм

1.2 Стандарт OpenMP

1.3 Розпаралелювання для OpenMP

1.4 Cуть і актуальність проблеми

2. Цілі дипломної роботи

2.1 Мета проекту "Система автоматизації розпаралелювання"

2.2 Цілі "Експерта для мультипроцесора"

2.3 Вхідні дані

2.4 Вихідні і зберігаються дані

3. Попередні рішення "систем автоматизації розпаралелювання"

4. Побудова розв'язку задачі

4.1 Формат вхідних даних

4.2 Основні аспекти роботи експерта

4.3 Оціночні функції

5. Покрокова реалізація "Експерта"

5.1 Крок 1. Попередній аналіз

5.2 Крок 2. Вибір варіанта розпаралелювання

5.3 Крок 3. Вибір варіанту локалізації

5.4 Крок 4. Внесення кінцевих коментарів до Бази Даних і підрахунок прискорення

5.5 Приклади роботи алгоритму

5.5.1 Програма "Якобі"

5.5.2 Програма "Sor"

5.5.3 Програма "Модифікований SOR"

5.5.4 Програма "Модифікований Якобі"

6. Висновок

Перелік прийнятих термінів

Література

Введення

Розпаралелювання програм

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

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

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

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

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

Тим не менш, будь-який кластер можна розглядати як єдину апаратно-програмну систему, яка має єдину комунікаційну систему, єдиний центр управління та планування завантаження. Обчислювальні мережі (GRID) об'єднують ресурси безлічі кластерів, багатопроцесорних і однопроцесорних ЕОМ, що належать різним організаціям і підкоряються різних дисциплін використання. Розробка паралельних програм для них ускладнюється через наступних проблем.

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

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

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

На Рис. 1 описані основні особливості симетричних мультипроцесорних систем (SMP). Для даних систем, як модель програмування для мультипроцесорів, виникла модель паралелізму з управління (у західній літературі використовується й інша назва - модель розподілу роботи, work - sharing model). На мультипроцесорах в якості моделі виконання використовується модель спільної пам'яті. У цій моделі паралельна програма являє собою систему ниток, що взаємодіють за допомогою загальних змінних і примітивів синхронізації. Нитка (по-англійськи "thread") - це легкий процес, що має з іншими нитками загальні ресурси, включаючи спільну оперативну пам'ять.

Архітектура	Система складається з декількох однорідних процесорів і масиву загальної пам'яті (звичайно з декількох незалежних блоків). Всі процесори мають доступ до будь-якій точці пам'яті з однаковою швидкістю. Процесори підключені до пам'яті або за допомогою загальної шини (базові 2-4 процесорні SMP-сервери), або за допомогою crossbar-комутатора (HP 9000). Апаратно підтримується когерентність кешів.
Приклади	HP 9000 V-class, N-class; SMP-cервера і робочі станції на базі процесорів Intel (IBM, HP, Compaq, Dell, ALR, Unisys, DG, Fujitsu та ін.)
Масштабованість	Наявність загальної пам'яті значно спрощує взаємодію процесорів між собою, однак накладає сильні обмеження на їх число - не більше 32 у реальних системах. Для побудови масштабованих систем на базі SMP використовуються кластерні або NUMA-архітектури.
Операційна система	Вся система працює під управлінням єдиної ОС (зазвичай UNIX-подібної, але для Intel-платформ підтримується Windows NT). ОС автоматично (у процесі роботи) розподіляє процеси / нитки по процесорам (scheduling), але іноді можлива і явна прив'язка.
Модель програмування	Програмування в моделі загальної пам'яті. (POSIX threads, OpenMP). Для SMP-систем існують порівняно ефективні засоби автоматичного розпаралелювання.

Рис. 1. Симетричні мультипроцесорні системи.

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

Перша спроба стандартизувати таку модель призвела до появи в 1990 році проекту мови PCF Fortran (проект стандарту X3H5). Однак, цей проект тоді не привернув широкої уваги та, фактично, залишився тільки на папері. Можливо, що причиною цього було зниження інтересу до мультипроцесорах і загальне захоплення мультікомпьютерамі і HPF.

Однак, через кілька років ситуація сильно змінилася. По-перше, успіхи у розвитку елементної бази зробили дуже перспективним і економічно вигідним створювати мультипроцесора. По-друге, широкий розвиток одержали мультікомпьютери з DSM (distributed shared memory - розподілена спільна пам'ять), що дозволяють програмам на різних вузлах взаємодіяти через загальні змінні також, як і на мультипроцесорах (Convex Exemplar, HP 9000 V-class, SGI Origin 2000). По-третє, не виправдалися надії на те, що HPF стане фактичним стандартом для розробки обчислювальних програм.

Найбільші виробники комп'ютерів і програмного забезпечення об'єднали свої зусилля і в жовтні 1997 року випустили опис мови OpenMP Fortran - розширення мови Фортран 77. Пізніше вийшли аналогічні розширення мов Сі і Фортран 90/95.

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

Успішне впровадження OpenMP на мультипроцесорах і DSM-мультікомпьютерах різко активізувало дослідження, спрямовані на пошуки шляхів поширення OpenMP на мультікомпьютери, кластери та мережі ЕОМ. Ці дослідження зосередилися, в основному, на двох напрямках:

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

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

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

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

Основний недолік цього підходу також очевидна - програмісту треба знати і вміти використовувати дві різні моделі паралелізму і різні інструментальні засоби [1].

Стандарт OpenMP

Інтерфейс OpenMP [4] задуманий як стандарт для програмування на масштабованих SMP-системах в моделі загальної пам'яті (shared memory model). У стандарт OpenMP входять специфікації набору директив компілятора, процедур і змінних середовища. Розробкою стандарту займається організація OpenMP ARB (ARchitecture Board), до якої увійшли представники найбільших компаній - розробників SMP-архітектур і програмного забезпечення. Специфікації для мов Fortran і C / C + + з'явилися відповідно в жовтні 1997 року і жовтні 1998 року.

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

Розробник не створює нову паралельну програму, а просто послідовно додає в текст послідовної програми OpenMP-директиви. На Рис. 2 показано зручність OpenMP: необхідно вставити всього 2 рядки в програму, яка обчислює число пі, щоб вона стала паралельна.

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

Однак стандарт OpenMP не обмежується тільки набором директив, а специфікує API [10], який, крім директив компілятору, включає набір функцій системи підтримки виконання OpenMP-програм, а також змінні оточення. Далі ми розглянемо основні особливості OpenMP стосовно мови Fortran [9]. Існують аналогічні засоби для мов Сі / C + +. У рамках OpenMP стандартна послідовна модель мови Fortran розширюється паралельними конструкціями SPMD (Single Program, Multiple Data), які найбільш близькі до традиційної "послідовної" ідеології.

У OpenMP використовується модель паралельного виконання fork / join. Програма починає виконуватися як один процес, який у ОpenMP називається головною ниткою (master thread). Цей процес виконується послідовно до тих пір, поки він не дійде до першої паралельної конструкції (у найпростішому випадку - області, яка є між директивами PARALLEL і END PARALLEL). У цей момент створюється "бригада" (team) ниток, а "бригадиром" для неї є головна нитка. Усередині бригади головна нитка має номер 0, а кількість ниток у бригаді задається змінною оточення чи може змінюватися динамічно перед початком виконання паралельної області шляхом виклику відповідної функції системи підтримки виконання OpenMP-програм. Однак всередині паралельної області кількість ниток фіксоване.

Шматок програми, укладений між директивами PARALLEL і END PARALLEL, виконується паралельно всіма нитками бригади (див. Рис. 3). Оператори програми, логічно укладені між цією парою директив, утворюють, в термінології OpenMP, лексичну (статичну) область дії відповідної паралельної конструкції. Оскільки зазначений блок програми може містити виклики підпрограм, які теж можуть виконуватися паралельно, вводиться поняття динамічної області дії, який включає і підпрограми, що викликаються з даного блоку [3].

Після завершення виконання паралельної конструкції нитки бригади синхронізуються, а виконання продовжує тільки головна нитка. Природно, у програмі може бути багато паралельних конструкцій; відповідно бригади ниток можуть утворюватися не один раз. OpenMP передбачає можливість вкладення паралельних конструкцій (пар PARALLEL / END PARALLEL). Багато "ключі" (clauses) в директивах OpenMP дозволяють вказати атрибути даних, що діють в період виконання відповідної паралельної конструкції.

За умовчанням, в паралельному регіоні приватними (приватними) є індекси паралельних циклів DO, всі інші змінні, за замовчуванням, загальні. Однак це правило умовчання можна змінити, вказавши ключ DEFAULT (PRIVATE) або зовсім скасувати, якщо задати DEFAULT (NONE). Лічильники фортрановскіх DO-циклів слід робити приватними (PRIVATE) для кожної нитки бригади. Такі приватні об'єкти (прості змінні, масиви і т.д.) з точки зору їх обробки еквівалентні тому, як якщо б для кожної нитки була б декларація нового об'єкта того ж типу. Всі посилання на вихідний об'єкт в лексичній області дії паралельної конструкції замінюються на посилання на цей новий приватний об'єкт.

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

Директива THREADPRIVATE (список змінних) оголошує приватними в нитках паралельного регіону змінні, описані в програмі. Директива вказується відразу після опису відповідних змінних і не впливає на роботу з ними поза паралельного регіону. З нею пов'язана директива COPYIN (список змінних) - для кожної нитки паралельного регіону створюються копії змінних, описаних в директиві threadprivate, копій присвоюються поточні значення оригіналів. Імена, зазначені в списках директиви threadprivate і параметра copyin, повинні збігатися. COPING застосовується з директивою parallel.

Існує можливість використання умовного оператора: IF (cкалярное_логическое_выражение).

Якщо цей ключ вказано, то відповідна паралельна область кодів буде виконуватися кількома нитками тільки за умови, що "скалярное_логическое_выражение" істинно. Наприклад, вказавши IF (N.GT.1000), можна змусити компілятор породити таку програму, що під час виконання перевіряється розмірність (N) і програма виконувалася б паралельно, тільки якщо ця розмірність досить велика - більше 1000. Це дозволяє уникати розпаралелювання при маленьких розмірностях, коли воно може виявитися невигідним через велику частку накладних витрат.

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

subroutine OMP _ SET _ NUM _ THREADS (N) - встановлює кількість ниток, рівне N.
integer function OMP _ GET _ NUM _ THREADS () - повертає кількість ниток у бригаді.
integer function OMP _ GET _ THREAD _ NUM ()-повертає номер "поточної" нитки (з якої стався виклик функції) у бригаді.

Крім вказівок на розподіл робіт між нитками, OpenMP має директиву SINGLE / END SINGLE, яка дозволяє виконувати укладений у неї блок Fortran-програми тільки однієї нитки.

Для розпаралелювання циклів існує директива DO (див. Рис. 4). У якості "ключів" можна вказати описатели PRIVATE (список), FIRSTPRIVATE (список), SHARED (список), ключ REDUCTION, а також ключі ORDERED і SCHEDULE.

Ключ SCHEDULE використовується для вказівки дисципліни планування виконання циклу нитками і має вигляд: SCHEDULE (тип [, M])

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

STATIC [, m] - блочно-циклічне розподіл ітерацій: перший блок з m ітерацій виконує перша нитка, другий блок - друга і т.д. до останньої нитки, потім розподіл знову починається з першої нитки, за замовчуванням значення m дорівнює 1;
DYNAMIC [, m] - динамічний розподіл ітерацій з фіксованим розміром блоку: спочатку всі нитки отримують порції з m ітерацій, а потім кожна нитка, закінчує свою роботу, отримує наступну порцію знову-таки з m ітерацій;

GUIDED [, m] - динамічний розподіл ітерацій блоками зменшуваного розміру; аналогічно розподілу DYNAMIC, але розмір виділених блоків весь час зменшується, що в ряді випадків дозволяє акуратніше збалансувати завантаження ниток;
RUNTIME - спосіб розподілу ітерацій циклу вибирається під час роботи програми в залежності від значення змінної OMP_SCHEDULE.

Якщо в OpenMP-директиві END DO задано NOWAIT, в Наприкінці циклу нитки НЕ синхронізовані. Ключ REDUCTION директиви! $ OMP PARALLEL DO позначає редукційну змінну (Див. Рис. 5).

У OpenMP є також можливість використовувати скорочення, що дозволяють об'єднувати інструкції PARALLEL / END PARALLEL і DO / ENDDO в пару PARALLEL DO / END PARALLEL DO.

Директива SECTIONS (див. Рис. 6) використовується для розподілу роботи між нитками в "Неітераційне" випадку. Ключі, як і раніше, можуть вказувати на тип змінних (PRIVATE, FIRSTPRIVATE і т.д.), а також містити ключ REDUCTION. OpenMP-конструкція SECTIONS дозволяє декільком ниткам виконувати паралельно звичайний лінійний ділянку програми на Фортрані, розбитий на "секції" - блоки операторів мови. Ці секції можуть містити в собі, зокрема, виклики фортрановскіх підпрограм.

Багаті можливості надають кошти OpenMP і для синхронізації. Відповідні директиви дозволяють, зокрема, встановити бар'єр (! $ OMP BARRIER) або забезпечити синхронізацію (! $ OMP ATOMIC), яка забезпечує від одночасного запису кількома нитками в одне і те ж поле оперативної пам'яті. Це дозволяє запобігти ситуації перегонів. Інша корисна директива, про яку варто згадати - це! $ OMP FLUSH. Вона змушує у відповідній точці програми отримати "узгоджене" між нитками стан оперативної пам'яті (при цьому змінні з регістрів будуть записані в пам'ять, скинуться буфери запису і т.д.). Пара директив MASTER: END MASTER виділяє ділянку коду, який буде виконаний тільки ниткою-майстром. Решта нитки пропускають дану ділянку і продовжують роботу з виконання оператора, розташованого слідом за директивою END MASTER. За допомогою директиви CRITICAL оформляється критична секція програми. У кожний момент часу в критичній секції може знаходитися не більше однієї нитки (див. Рис. 7). Якщо критична секція вже виконується будь-якої ниткою P0, то всі інші нитки, які виконали директиву для секції з такою назвою, будуть заблоковані, поки нитка P0 не закінчить виконання даної критичної секції. Як тільки P0 виконає директиву END CRITICAL, одна з заблокованих на вході ниток увійде в секцію. Якщо на вході в критичну секцію стояло кілька ниток, то випадковим чином вибирається одна з них, а інші заблоковані нитки продовжують очікування. Всі неіменовані критичні секції умовно асоціюються з одним і тим же ім'ям.

Директива ORDERED змушує коди Fortran, укладені всередині пари ORDERED / END ORDERED, виконуватимуться в "природному" порядку (в тій, в якій ітерації циклу виконуються при нормальному послідовному виконанні). Ця пара директив може бути присутнім тільки в динамічній області дії директиви DO (або PARALLEL DO), в якій зазначений ключ ORDERED. Такі директиви можуть використовуватися для організації друку в нормальній - скажімо, за зростанням лічильника циклу-послідовності [2].

Розпаралелювання для OpenMP

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

З цього випливає, що:

важко розраховувати на створення системи повністю автоматизує це перетворення, тобто розпаралелювання представляється як ітераційний процес взаємодії користувача з системою;
система не повинна обмежувати вибір, а по можливості, повинна і підказувати варіанти розпаралелювання;
система повинна допускати втручання користувача, тобто прийняття рішень самим користувачем;

C уть і актуальність проблеми

Переваги OpenMP:

Розробник не створює нову паралельну програму, а просто послідовно додає в текст послідовної програми OpenMP-директиви.
OpenMP - досить гнучкий механізм, що надає розробнику більші можливості контролю над поведінкою паралельного застосування.
Передбачається, що OpenMP-програма на однопроцесорній платформі може бути використана в якості послідовної програми, тобто немає необхідності підтримувати послідовну і рівнобіжну версії. Директиви OpenMP просто ігноруються послідовним компілятором.
Одним з достоїнств OpenMP його розробники вважають підтримку так званих "orphan" (відірваних) директив, тобто директиви синхронізації і розподілу роботи можуть не входити безпосередньо в лексичний контекст паралельної області.
OpenMP - стандарт, який розроблений представницьким форумом (HP, IBM, Intel, SGI, Sun, Fujitsu, NEC) для програмування мультипроцесорів і DSM-систем
Підтримується в компіляторах мов Fotran, C, C + + для всіх основних типів процесорів.

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

Цілі дипломної роботи

Цілі проекту "Система автоматизації розпаралелювання"

Дана дипломна робота є лише частиною проекту автоматизації розпаралелювання програм, тому спочатку зупинимося на проекті.

Рис. 8. Проект: Система автоматизації розпаралелювання.

На Рис. 8 схематично показані складові проекту: "Аналіз програми", "Експерт для мультипроцесора" (OpenMP) і "Експерт для кластера" (DVM).

Користувач створює послідовну програму на мові Fortran. У результаті роботи системи, користувач отримує інформацію для аналізу:

дерево циклів; для кожного циклу - його параметри та атрибути (результати аналізу);
опису даних;
опис використання масивів в циклах і знайдені залежності;
список запропонованих (у тому числі розглянутих, але відкинутих) варіантів розподілу (завдання "Експерта");
створені і модифікуються користувачем набори конфігурацій цільової машини і розмірів завдань;
для кожного запропонованого варіанту розпаралелювання (всіх конфігурацій і розмірів) і кожного циклу і всієї програми, як кореня дерева циклів, - оцінки часу виконання і якості розпаралелювання для даного варіанта (завдання "Експерта");

Програма, вступаючи в систему автоматизації розпаралелювання, проходить аналіз, на підставі якого формується База Даних, в яку входять: дерево циклів; опису масивів, опис використання масивів у циклах; додаткові коментарі.

З інформацією з бази даних "Експерти" шукають найоптимальніші способи розпаралелювання і додають інформацію про них до бази даних. Код програми на виході системи не змінюється, а всього лише додаються коментарі, де рекомендується вставити директиви OpenMP або DVM (можливо декілька кращих варіантів), наскільки будуть ефективні ці вставки, а також інформація з аналізу.

Цілі "Експерта для мультипроцесора"

Мета даного диплому - розробка програми, що реалізує "Експерт для мультипроцесора" в проекті. На підставі даних, отриманих на стадії аналізу, і характеристик конкретного мультипроцесора "Експерт" повинен занести до бази даних інформацію про коментарі (директивах OpenMP), які повинні бути вставлені в програму, яка вийде на виході системи, а також інформацію щодо прогнозованої ефективності розпаралелювання. Таким чином, "Експерт" генерує, оцінює і вибирає найкращі варіанти розподілу обчислень і локалізації даних. Експерт не змінює код програми, а лише вносить до бази даних інформацію про "найкращих рекомендаціях з розпаралелюванню". Ця інформація згодом і буде видана користувачеві.

Вхідні дані

Опис циклу містить:

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

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

Список масивів (і простих змінних).

Для кожного масиву:

ідентифікатор;
розмір по кожному вимірюванню;
список звернень до масиву.

Варіант завдання:

розмірності масивів по кожному вимірюванню (вже як константи);
число ітерацій;
або значення зовнішніх змінних, від яких залежать ці величини.

Варіант масиву процесорів:

число вимірювань і розмір по кожному виміру (грати процесорів).

Звернення до масивів (і змінним) у циклі - відношення "до <масиву> звертаються до <циклі>". Для кожної пари <масив, цикл>:

ні (не створює) залежно ні між итерациями, ні всередині;
залежність всередині однієї ітерації;
REDUCTION (залежність між итерациями створюють оператори спеціального виду, типу a = a + x _i);
Private, Lastprivate, Firstprivate - приватні змінні
виникає через нього залежність між итерациями загального вигляду.

Список усіх звернень, тобто наборів індексних виразів, бажано без повторень. Про кожне треба вказати:

читання або / і присвоювання;
індексні вирази;

Вихідні і зберігаються дані

Вихідні дані представляють собою:

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

Попередні рішення "систем автоматизації розпаралелювання"

Тут буде зроблено короткий огляд систем, в яких розробники і робочі групи досягли значних зрушень у вирішенні задачі.

Interactive Parallelizing Assistance Tool for OpenMP [7]

Aachen University, Німеччина. 2003

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

Interprocedural Parallelizing Compiler WPP and Analysis Information Visualization tool Aivi [8]

Hitachi, Ltd. Японія. 2000

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

The ParaWise Expert Assistant [6]

University of Greenwich, Великобританія. Серпні 2004.

Являє собою один з інструментів системи ParaWise / CAPO [5]. На підставі інструментів системи, які проводять аналіз програми, "Експерт-асистент" підказує: чи можливо розпаралелювання, і представляє деякі варіанти розпаралелювання (вставки OpenMP директив).

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

Побудова розв'язку задачі

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

Формат вхідних даних

Робота з Базою Даних для експерта відбувається за допомогою інтерфейсу. Основна частина Бази Даних-дерево циклів. Структура дерева важлива для опису алгоритмів роботи експерта. Вершини дерева можуть бути наступних типів:

Процедура. У даній версії "Системи автоматичного розпаралелювання" процедурою вважається тільки тіло програми.
Цикл. Цикл містить інформацію про всі змінних, використаних в ньому, залежностях, знайдених у ньому аналізатором, часу виконання одного витка, кількість ітерацій для даного варіанта завдання.
Лінійний фрагмент.
Умовний оператор.

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

Основні аспекти роботи експерта

При складанні алгоритмів експерта були враховані наступні можливості OpenMP:

можливість роботи з циклами (директива DO).
можливість обробки редукційних змінних (директива REDUCTION).
можливість виконувати частину коду всередині циклу в "природному" порядку (директива ORDERED).
можливість приватизувати змінні (директива PRIVATE).
можливість утворювати конвеєр допомогою OpenMP директив (ця можливість буде розглянута нижче).
можливість скасування синхронізацій між паралельними циклами (директива NOWAIT).

При роботі експерта всі цикли в програмі розбиваються на Потенційно Паралельні Цикли (далі ППЦ) і Цикли, Неподдающиеся Розпаралелювання (далі ЦНР). ППЦ - цикл, який можна распараллеліть засобами OpenMP, не обов'язково ефективно. ЦНР - цикли, які не піддаються розпаралелюванню через залежностей за даними між витками циклу. Такі цикли бувають наступних видів:

містять введення / висновок.
містять вихід з циклу.

Основна мета "Експерта" - знаходження для послідовної програми набору директив OpenMP такого, що прискорення паралельної програми при заданому варіанті роботи програми буде максимально. Назвемо такий набір директив найкращими коментарями до програми. Всі коментарі розіб'ємо на два види: коментарі по локалізації змінних (PRIVATE, REDUCTION і т.д.) і всі інші коментарі. Назвемо Варіантом паралелізму програми (далі Варіант паралелізму) - варіант директив OpenMP, що описують паралельні області та паралельні цикли (без директив локалізації змінних). Тоді Варіант локалізації змінних (Варіант локалізації) - варіант директив локалізації змінних. Для кожного варіанта паралелізму може існувати кілька варіантів локалізації. Перевіркою Альтернативної перекладу назвемо знаходження мінімуму оціночної функції для набору локалізацій для даного варіанту паралелізму з фіксуванням коментарів, відповідних мінімальної оціночної функцією. Схема розпаралелювання - фіксація одного варіанта паралелізму і одного варіанта локалізації.

Робота Експерта для мультипроцесора розділена на 4 стадії:

Поділ всіх циклів програми на ППЦ та ЦНР, позначення видів ППЦ та попереднє фіксування набору варіантів локалізації змінних.
Перебір всіляких варіантів розпаралелювання програми, попереднє фіксування найкращого варіанту паралелізму.
Перебір варіантів локалізацій програми, фіксування найкращою схеми розпаралелювання, підрахунок прискорення.
Розстановка директив OpenMP, відповідних найкращою схемою розпаралелювання, в програму.

У процесі роботи "Експерта" створюються внутрішні представлення даних, що забезпечують рішення задачі, представлені в Таблиці 1

Назва вистави	На якому кроці створюється	Що містить	Навіщо потрібно
Перше внутрішнє	1 крок	1. Інформація про всіх операторів програми 2. Інформація про локалізацію програми "за замовчуванням"	Базове уявлення, на підставі якого здійснюється подальший аналіз
Друге внутрішнє	2-3 крок	Схема розпаралелювання, яка вважається найкращою	Для формування коментарів (містить інформацію по розпаралелюванню)
Список паралельних регіонів	2 крок	Всі паралельні регіони програми	Для формування коментарів (містить інформацію щодо локалізації)
Програмний список локалізацій змінних	3 крок	Список змінних, для кожної з яких ведеться список локалізацій у паралельних регіонах програми	Для проставляння коментаря threadprivate

Таблиця 1. Внутрішні вистави "Експерта".

Перше внутрішнє уявлення містить інформацію про локалізацію змінних.

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

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

1-е значення 1-ї пари (вид приватної)	2-е значення 1-ї пари - позначка приватній
private (по замовчуванням) firstprivate lastprivate reduction	Ind - індекс Set - Необхідно вказати в коментарях Redtype () - тип редукції (тільки для редукційних) Pos (за замовчуванням) - можливо оголосити приватній, але не обов'язково No - неможливо оголосити приватній
1-е значення 2-ї пари (загальна)	2-е значення 2-ї пари (позначка загальної)
Shared (за замовчуванням)	Def (за умовчанням) - загальна за замовчуванням Set - необхідно вказати в директивах No - неможливо оголосити загальної

Таблиця 2. Позначки щодо локалізації змінних.

Як позначки відповідають директивам OpenMP:

Якщо 2-е значення 1-ї пари = Set, змінну необхідно оголосити PRIVATE.

Якщо 2-е значення 2-ї пари = Set, змінну необхідно оголосити SHARED.

Якщо 1-е значення 1-ї пари = reduction, необхідна директива REDUCTION (2-е значення 1-ї пари: ім'я змінної).

Якщо 1-е значення 1-ї пари = lastprivate, необхідна директива LASTPRIVATE (ім'я змінної).

Якщо 1-е значення 1-ї пари = firstprivate, необхідна директива FIRSTPRIVATE (ім'я змінної).

Оціночні функції

Оціночна функція вартості паралельного регіону обчислюється за наступною формулою:

Вартість паралельного виконання = (вартість послідовного виконання / число ниток + вартість ordered) * кількість ітерацій + вартість створення і видалення паралельної області вартість послідовного виконання

Це вартість однієї ітерації циклу (надана аналізатором) без урахування вартості виразів, оточених директивами Ordered / End Ordered число ниток - кількість "корисних" процесорів. Для циклу це значення дорівнює мінімуму із загальної кількості процесорів і кількості ітерацій циклу.

вартість ordered = вартість послідовного виконання виразів, оточених директивами Ordered / End Ordered.

вартість створення і видалення паралельної області = const + вартість створення m приватних змінних + вартість синхронізації. Константа залежить від архітектури системи і береться з бази даних або визначається користувачем. Це час, необхідний для створення (ініціалізації) і видалення паралельного регіону.

вартість створення m приватних змінних = m, де m це кількість приватних змінних в даному паралельному регіоні. Так як відомо, що одиниця вартості послідовного виконання програми еквівалентна одиничної запису в пам'ять, то для створення m локальних змінних візьмемо час рівне m "умовних одиниць". Це пов'язано з тим, що для кожної нитки необхідно ініціалізувати m змінних.

вартість синхронізації = кількість приватних змінних. Синхронізація відбувається при закритті паралельного циклу. При цьому необхідно синхронізувати всі локальні копії змінних. Вартість бар'єрної синхронізації, яка залежить від обладнання, враховується у вартості видалення паралельної області.

Оціночна функція вартості обчислюється за наступною формулою:

Вартість конвеєра = вартість дій всередині конвеєра * кількість дій конвеєра + ініціалізація конвеєра + синхронізація конвеєра.

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

кількість дій конвеєра, кількість дій, коли в роботу задіяна хоча б 1 нитку.

ініціалізація конвеєра = const, залежить від архітектури системи і береться з бази даних або визначається користувачем.

синхронізація конвеєра = кількість директив FLUSH, BARRIER і ENDDO * кількість локальних змінних * кількість дій конвеєра.

Оціночна функція регіону дорівнює сумі всіх оціночних функцій членів регіону.

Покрокова реалізація "Експерта"

Крок 1. Попередній аналіз

Дані на вході: База Даних з результатами статичного аналізу.

Дані на виході: 1-е внутрішнє представлення.

Як проходить перетворення вхідних даних у вихідні:

Цикли поділяємо на ППЦ та ЦНР, паралельно розраховуючи локалізацію за умовчанням. Лінійні фрагменти і умовні оператори просто переносимо. Прохід по дереву здійснюється "зверху-вниз".

Алгоритм перетворення вхідних даних у вихідні:

Проходимо по дереву циклів з Бази Даних, в залежності від вершини робимо відповідні дії.

Якщо вершина - цикл, не піддається розпаралелюванню переносимо їх у перше внутрішнє подання з позначкою ЦНР.

Якщо вершина - ППЦ, проводимо таку послідовність дій:

У поточну версію коментарів до вершини в першому внутрішньому поданні записати ППЦ.
Помітити рівень вкладеності (виходячи з того, що "тіло" програми має рівень 0).
Для всіх змінних, що використовуються в даному циклі в тимчасовому поданні зробити позначки:

Для індексу: private, ind, shared, no
Для інших: private, pos, shared, def

Якщо є редукція в циклі: для всіх редукційних змінних зробити позначки: reduction, "операція редукції", shared, no
Якщо в циклі присутня скалярна залежність за даними: для всіх змінних зі скалярною залежністю зробити позначки: private (lastprivate), set, shared, no
Якщо цикл містить залежність за даними в масиві: проставити для даного циклу позначку ordered і для оператора, відповідного перший використання масиву, що має залежність, в тілі циклу позначку "перше використання ordered", для оператора, відповідного останньому використання масиву, що має залежність, в тілі циклу поставити позначку "останнє використання ordered". Масиви, що викликали залежність занести в список "масивів з залежностями".

Якщо вершина - лінійний фрагмент або розгалуження - просто переносимо вершину з Бази Даних у 1-е внутрішнє представлення.

Крок 2. Вибір варіанта розпаралелювання

Дані на вході: База Даних з результатами статичного аналізу, 1-е внутрішнє представлення.

Дані на виході: незакінчена 2-е внутрішнє представлення.

Як проходить перетворення вхідних даних у вихідні:

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

На цьому кроці оминаємо дерево з перших внутрішнього подання і вибираємо найкращу схему розпаралелювання для вкладених ППЦ і об'єднуємо в паралельні регіони "сусідні" ППЦ. Для паралельних регіонів перебираємо всі можливі варіанти коментарів з фіксуванням найкращого з них у 2-му внутрішньому поданні.

Алгоритм перетворення вхідних даних у вихідні:

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

Основні дії кроку 2:

Знаходимо ППЦ найбільшого рівня (тобто самий "нижчий" за вкладеності) і робимо рівень знайденого циклу поточним.
Для всіх циклів поточного рівня порівнюємо 3 оціночних функції:

оціночна функція для послідовного варіанта,
оцінна функція при розпаралелювання даного циклу,
оцінна функція при розпаралелювання вкладених циклів, при тому, що даний цикл залишається послідовним (цей варіант оцінюється тільки, якщо існують вкладені ППЦ).
1. Якщо мінімальна функція a), то цикл позначається як неефективний для розпаралелювання. Якщо мінімальна функція b), то цикл позначається як ефективний для розпаралелювання та додається в паралельний регіон. Вкладені цикли, визнані ефективними для розпаралелювання стають неефективними для розпаралелювання. Якщо мінімальна функція с), то ніяких дій не відбувається.
2. Цикли, для яких розпаралелювання ефективно (мінімальна функція b) додаються у паралельний регіон. Якщо на поточному рівні вже є паралельний регіон, причому останній пройдений цикл сусідить з поточним, то проводиться перевірка на відсутність конфліктів локалізацій, якщо поточний цикл буде додано до паралельний регіон. У разі відсутності конфліктів, поточний цикл додається в регіон. Якщо знайдені конфлікти локалізації, або попередній цикл на рівні не є сусідами з поточним, або поточний цикл перший на рівні, то для циклу створюється новий паралельний регіон. Якщо в паралельний регіон додається цикл, то відбувається перевірка на установку Nowait.
3. Далі, цикл позначається, як пройдений. Якщо на рівні не залишилося не пройдених циклів, поточний рівень стає на одиницю менше, і тривають дії 2). Якщо ж поточний рівень прийняв значення 0, то після того, як не залишиться не пройдених ППЦ формується друга внутрішнє уявлення, що відбиває всі цикли, ефективні для розпаралелювання.

Як відбувається встановлення NOWAIT для поспіль стоять паралельних циклів:

Умова перевіряється для поспіль циклів при додаванні нового циклу в паралельний регіон.

Якщо в останнього циклу в паралельному регіоні є позначка NowaitIn (означає, що перед попереднім циклом вже встановлена директива NOWAIT), то перевірити умова Nowait для пар (новий цикл, останній цикл в паралельному регіоні). Якщо умова істинна перевіряти умова для пар всіх (новий цикл, цикл з позначкою NowaitOut), причому починаючи з передостаннього і в зворотному порядку, до першої невдалої перевірки або до першого циклу без позначки NowaitOut. Якщо не було невдалих перевірок, поставити у нового циклу позначку NowaitIn, а в останнього в паралельному регіоні NowaitOut (означає, що після циклу встановлена директива NOWAIT).
Якщо ж в останнього циклу в паралельному регіоні немає позначки позначка NowaitIn, то перевірити умова Nowait для пар (новий цикл, останній цикл в паралельному регіоні). Якщо умова істинна, поставити у нового циклу позначку NowaitIn, а в останнього в паралельному регіоні NowaitOut.

Перевірка умови Nowait між двома циклами:

Якщо безліч змінних / масивів для 2 поспіль циклів не перетинається (за винятком індексів - вони можуть бути однаковими), то перевірка вдала.
Інакше, порівняти індекси масивів. Для кожного звернення до непріватізованному масиву у лівій частині одного циклу і для кожного звернення до цього ж масиву у іншому циклі порівняти індекси. Якщо доведемо для вимірювання, по якому йде розпаралелювання, що індекси в усіх зверненнях різні і кількість ітерацій в циклах рівні, то перевірка вдала. Інакше перевірка невдала.

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

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

Для розпаралелювання циклів із залежністю використовується алгоритм, який був застосований в тестах NASA. Цей алгоритм накладає ряд обмежень, які перевіряються експертом. Варіант конвеєрної роботи тестується тільки, якщо цикл з конвеєрною залежністю є вкладеним внутрішнім. У залежності не беруть участь "кутові" елементи. На Рис. 9 ліворуч зображено залежність без участі "кутових" елементів. Тобто значення масиву залежить від значення елементів при зміні лише 1 виміру. У правій частині Рис. 9 описаний варіант залежності, при якому установка конвеєра неможлива через "кутових" елементів.

Рис. 9. Можливість установки конвеєра.

Для такого циклу оцінна функція при розпаралелювання циклу вважається, як мінімум оціночної функції:

для роботи циклу з директивами ORDERED,
конвеєрним розпаралелюванням.

У разі якщо на основному кроці цикл був помічений, як ефективний для розпаралелювання, то якщо мінімальна функція a), то цикл позначається ORDERED, інакше PIPELINE.

Крок 3. Вибір варіанту локалізації

Дані на вході: База Даних з результатами статичного аналізу, 1-е внутрішнє уявлення, незакінчена 2-е внутрішнє представлення.

Дані на виході: 2-е внутрішнє представлення.

Як проходить перетворення вхідних даних у вихідні:

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

Алгоритм перетворення вхідних даних у вихідні:

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

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

Якщо в Програмному списку локалізації змінних, будь-якої мінлива у всіх паралельних регіонах стає приватним, то в програмному списку локалізацій змінних даний масив позначається як threadprivate. Для наступних паралельних регіонів, що використовують даний масив, він оголошується в списку copyin. Установка даних директив дає прискорення за рахунок відсутності ініціалізації private змінних.

Для всіх масивів, для яких не проставлені коментарі threadprivate, розраховуємо альтернативну локалізації для всієї програми, вважаючи змінну приватній, але віднімаючи вартість ініціалізації і синхронізації для масиву. Якщо оціночна функція альтернативної локалізації краще оціночної функції для 2-го внутрішнього подання, альтернативна локалізація заноситься в 2-е внутрішнє уявлення, мінлива у всіх паралельних регіонах стає: private, def, shared, no і позначається як threadprivate.

Крок 4. Внесення кінцевих коментарів до Бази Даних і підрахунок прискорення

Дані на вході: База Даних, незакінчена 2-е внутрішнє представлення.

Дані на виході: База Даних з коментарями.

Як проходить перетворення вхідних даних у вихідні:

З 2-го внутрішнього подання коментарі переносяться до Бази Даних, дотримуючись синтаксис OpenMP. Оцінюється загальне прискорення.

Алгоритм перетворення вхідних даних у вихідні:

Проходимо всі вершини в Базі Даних. Кожну вершину намагаємося знайти у 2-му внутрішньому представленні, у разі успіху проставляємо відповідні коментарі наступним чином:

Якщо є масиви з позначкою threadprivate, то в вершину з описом змінних заноситься! $ OMP THREADPRIVATE (список змінних).
Якщо цикл перший в паралельному регіоні і цикл вигідний для розпаралелювання! $ OMP PARALLEL <список необхідних до позначення PRIVATE і SHARED змінних> <COPYIN (список змінних)>

<Список необхідних до позначення PRIVATE і SHARED змінних> - перерахування директив (клауз) виду PRIVATE (ім'я змінної) або SHARED (ім'я змінної). В одному списку може бути декілька, і PRIVATE, і SHARED.

<COPYIN (список змінних)> - вказується, якщо в циклі використовуються змінні з позначкою threadprivate, причому всі вони повинні бути перераховані через кому в списку змінних.

Якщо цикл останній в паралельному регіоні -! $ OMP END PARALLEL, як директива після циклу.
Якщо цикл вигідний для розпаралелювання -! $ OMP DO <ORDERED> <список REDUCTION, LASTPRIVATE, FIRSTPRIVATE>

<ORDERED> - директива ORDERED. Вказується, якщо при розпаралелювання циклу використовується ORDERED.

<Список REDUCTION, LASTPRIVATE, FIRSTPRIVATE> - перерахування директив (клауз) виду REDUCTION (ім'я змінної), або LASTPRIVATE (ім'я змінної), або FIRSTPRIVATE (ім'я змінної). В одному списку може бути декілька, і REDUCTION, LASTPRIVATE, FIRSTPRIVATE.

Якщо цикл вигідний для розпаралелювання -! $ OMP END DO, як директива після циклу.
Якщо у циклу позначка Ordered, перед першою вершиною з позначкою "перше використання ORDERED" вноситься! $ OMP ORDERED.
Якщо у циклу позначка Ordered, в кінець останньої вершини з позначкою "останнє використання ORDERED" вноситься,! $ OMP END ORDERED.
Якщо у циклу позначка pipeline - Вставляються наступні директиви:

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

! $ INTEGER OMP_GET_NUM_THREADS, OMP_GET_THREAD_NUM

! $ INTEGER IAM, NUMT, ISYNC ("кількість процесорів")

При ініціалізації паралельного регіону, в який входить цикл з конвеєром:

! $ OMP PARALLEL PRIVATE (IAM, NUMT, ILIMIT)

Перед do зовнішнього циклу - ініціалізація ниток і синхронізаційними масиву ISYNC:

! $ Iam = omp_get_thread_num ()

! $ Numt = omp_get_num_threads ()

! $ ILIMIT = MIN (NUMT -1, Число витків зовнішнього циклу)

! $ ISYNC (IAM) = 0

! $ OMP BARRIER

До циклу з конвеєрною залежністю - ініціалізація конвеєра, допуск до циклу для ниток тільки після того, як попередня нитка зробила одну ітерацію зовнішнього циклу і розпаралелювання витків внутрішнього циклу між нитками:

! $ IF (IAM. GT. 0. AND. IAM. LE. ILIMIT) THEN

! $ DO WHILE (ISYNC (IAM-1). EQ. 0)

! $ OMP FLUSH (ISYNC)

! $ ENDDO

! $ ISYNC (IAM-1) = 0

! $ OMP FLUSH (ISYNC)

! $ ENDIF

! $ OMP DO

Перед enddo зовнішнього циклу - дочекатися, поки наступна нитка запуститься, і продовжувати виконання циклу:

! $ OMP ENDDO NOWAIT

! $ IF (IAM. LT. ILIMIT) THEN

! $ DO WHILE (ISYNC (IAM). EQ. 1)

! $ OMP FLUSH (ISYNC)

! $ ENDDO

! $ ISYNC (IAM) = 1

! $ OMP FLUSH (ISYNC)

! $ ENDIF

Після enddo зовнішнього циклу - синхронізація:

! $ OMP BARRIER

Таким чином, всі нитки входять в паралельний регіон. Відпрацьовує 1-а нитка із своєю частиною витків внутрішнього циклу. Набирає роботу 2-а нитка, працюють обидві нитки, причому 1-а з 2-м значенням ітератора, а 2-я з першим і т.д. Приклад функціонування конвеєра показаний на Рис. 10.

Рис. 10. Обчислення циклу з конвеєрною залежністю для 2-х мірного випадку. Квадрати - області елементів масиву; цифра - № нитки, яка обчислить цю область; цифра в дужках - крок роботи конвеєра, на якому обчислити область.

Приклади роботи алгоритму

Програма "Якобі"

Лістинг послідовної програми

PROGRAM JAC

PARAMETER (L = 8, ITMAX = 20)

REAL A (L, L), EPS, MAXEPS, B (L, L)

PRINT *,'********** TEST_JACOBI **********'

MAXEPS = 0.5E - 7

DO 1 J = 1, L (1)

DO 1 I = 1, L (2)

A (I, J) = 0. IF (I.EQ.1. OR. J.EQ.1. OR. I.EQ.L. OR. J.EQ.L) THEN

B (I, J) = 0.

ELSE

B (I, J) = (1. + I + J) ENDIF

1 CONTINUE

DO 2 IT = 1, ITMAX (3)

EPS = 0.

DO 21 J = 2, L-1 (4)

DO 21 I = 2, L-1 (5)

EPS = MAX (EPS, ABS (B (I, J) - A (I, J)))

A (I, J) = B (I, J)

21 CONTINUE

DO 22 J = 2, L-1 (6)

DO 22 I = 2, L-1 (7)

B (I, J) = (A (I-1, J) + A (I, J-1) + A (I +1, J) + A (I, J +1)) / 4

22 CONTINUE

PRINT 200, IT, EPS

200 FORMAT ('IT =', I4, 'EPS =', E14.7)

IF (EPS. LT. MAXEPS) GO TO 3

2 CONTINUE

3 OPEN (3, FILE = 'JAC.DAT', FORM = 'FORMATTED', STATUS = 'UNKNOWN')

WRITE (3, *) B CLOSE (3) END

Перше внутрішнє представлення для циклів

Після першого кроку в першому внутрішньому поданні поміченим в лістингу послідовної програми циклам будуть відповідати наступні вершини:

(1) Тип: ППЦ, рівень = 0, число ітерацій = 8

Використання змінних:

Ім'я: i. Позначки: PRIVATE, SET, SHARED, NO

Ім'я: j. Позначки: PRIVATE, IND, SHARED, NO

Ім'я: a. Позначки: PRIVATE, POS, SHARED, DEF

Ім'я: b. Позначки: PRIVATE, POS, SHARED, DEF

(2) Тип: ППЦ, рівень = 1, число ітерацій = 8

Використання змінних:

Ім'я: i. Позначки: PRIVATE, IND, SHARED, NO

Ім'я: j. Позначки: PRIVATE, POS, SHARED, DEF

Ім'я: a. Позначки: PRIVATE, POS, SHARED, DEF

Ім'я: b. Позначки: PRIVATE, POS, SHARED, DEF

(3) Тип: ЦНР, рівень = 0, число ітерацій = 20

Використання змінних:

Ім'я: eps. Позначки: PRIVATE, SET, SHARED, NO

Ім'я: j. Позначки: PRIVATE, SET, SHARED, NO

Ім'я: i. Позначки: PRIVATE, SET, SHARED, NO

Ім'я: b. Позначки: PRIVATE, NO, SHARED, SET ORDERED!

Ім'я: a. Позначки: PRIVATE, NO, SHARED, SET ORDERED!

(4) Тип: ППЦ, рівень = 1, число ітерацій = 6

Використання змінних:

Ім'я: i. Позначки: PRIVATE, SET, SHARED, NO

Ім'я: eps. Позначки: REDUCTION, MAX, SHARED, NO

Ім'я: b. Позначки: PRIVATE, POS, SHARED, DEF

Ім'я: j. Позначки: PRIVATE, IND, SHARED, NO

Ім'я: a. Позначки: PRIVATE, POS, SHARED, DEF

(5) Тип: ППЦ, рівень = 2, число ітерацій = 6

Використання змінних:

Ім'я: eps. Позначки: REDUCTION, MAX, SHARED, NO

Ім'я: b. Позначки: PRIVATE, POS, SHARED, DEF

Ім'я: i. Позначки: PRIVATE, IND, SHARED, NO

Ім'я: j. Позначки: PRIVATE, POS, SHARED, DEF

Ім'я: a. Позначки: PRIVATE, POS, SHARED, DEF

(6) Тип: ППЦ, рівень = 1, число ітерацій = 6

Використання змінних:

Ім'я: i. Позначки: PRIVATE, SET, SHARED, NO

Ім'я: a. Позначки: PRIVATE, POS, SHARED, DEF

Ім'я: j. Позначки: PRIVATE, IND, SHARED, NO

Ім'я: b. Позначки: PRIVATE, POS, SHARED, DEF

(7) Тип: ППЦ, рівень = 2, число ітерацій = 6

Використання змінних:

Ім'я: a. Позначки: PRIVATE, POS, SHARED, DEF

Ім'я: i. Позначки: PRIVATE, IND, SHARED, NO

Ім'я: j. Позначки: PRIVATE, POS, SHARED, DEF

Ім'я: b. Позначки: PRIVATE, POS, SHARED, DEF

3) Другий крок

На цьому кроці буде влаштований перебір різних варіантів розпаралелювання. Розглянемо їх, групуючи по регіонах. Всі варіанти будемо розглядати при числі процесорів = 4. 1-й регіон: цикли (1) і (2). Тут буде розглянуто 3 варіанти, час виконання 1 витка внутрішнього циклу = 6, L = 8.

! $ OMP PARALLEL PRIVATE (I)

! $ OMP DO

DO 1 J = 1, L

DO 1 I = 1, L

A (I, J) = 0.

IF (I.EQ.1. OR. J.EQ.1. OR. I.EQ.L. OR. J.EQ.L) THEN

B (I, J) = 0.

ELSE

B (I, J) = (1. + I + J)

ENDIF

ENDDO

! $ OMP END DO

! $ OMP END PARALLEL

DO 1 J = 1, L

! $ OMP PARALLEL

! $ OMP DO

DO 1 I = 1, L

A (I, J) = 0.

IF (I.EQ.1. OR. J.EQ.1. OR. I.EQ.L. OR. J.EQ.L) THEN

B (I, J) = 0.

ELSE

B (I, J) = (1. + I + J)

ENDIF

ENDDO

! $ OMP END DO

ENDDO

! $ OMP END PARALLEL

Вартість = 6 * 8 * 8 / 4 + 14 = 110

Кількість приватних = 2

Час ініціалізації = 5

Час синхронізації змінних і видалення регіону = 7

Разом: 1 4

Вартість = 8 * (6 * 8 / 4 + 12) = 192

Кількість приватних = 1

Час ініціалізації = 5

Час синхронізації змінних і видалення регіону = 6

Разом: 12

Рис. 11. Порівняння варіантів розпаралелювання в 1-му регіоні програми "Якобі".

На Рис. 11 показані можливі розглянуті варіанти розпаралелювання: циклу по J в лівій частині і циклу по I в лівій частині. Пункт "Вартість" відображає підрахунок оціночної функції. Вона береться, як сума "паралельного" обчислення циклу і "додаткових" витрат, підрахованих в пункті "Разом". Так як вартість послідовна = 6 * 8 * 8 = 384, буде обраний варіант, показаний у лівій частині.

2-й регіон: цикли (4) і (5). Час виконання 1 витка внутрішнього циклу = 5.

! $ OMP PARALLEL PRIVATE (I)

! $ OMP DO REDUCTION (EPS, MAX)

DO 21 J = 2, L-1

DO 21 I = 2, L-1

EPS = MAX (EPS, ABS (B (I, J) - A (I, J)))

A (I, J) = B (I, J)

21 CONTINUE

! $ OMP END DO

! $ OMP END PARALLEL

DO 21 J = 2, L-1

! $ OMP PARALLEL

! $ OMP DO REDUCTION (EPS, MAX)

DO 21 I = 2, L-1

EPS = MAX (EPS, ABS (B (I, J) - A (I, J)))

A (I, J) = B (I, J)

! $ OMP END DO

! $ OMP END PARALLEL

21 CONTINUE

Вартість = 5 * 6 * 6 / 4 +16 = 61

Кількість приватних = 3

Час ініціалізації = 5

Час синхронізації змінних і видалення регіону = 8

Разом: 16

Вартість = 6 * (5 * 6 / 4 +14) = 129

Кількість приватних = 2

Час ініціалізації = 5

Час синхронізації змінних і видалення регіону = 7

Разом: 14

Рис. 12. Порівняння варіантів розпаралелювання в 2-му регіоні програми "Якобі".

На Рис. 12 показані можливі розглянуті варіанти розпаралелювання: циклу по J в лівій частині і циклу по I в лівій частині. Вартість послідовна = 6 * 6 * 5 = 180, отже, буде обраний варіант, описаний в лівій частині Рис. 12. Редукційна змінна вважається як приватна.

Третій регіон: цикли (6) і (7). Час виконання 1 витка внутрішнього циклу = 9.

! $ OMP PARALLEL PRIVATE (I)

! $ OMP DO

DO 22 J = 2, L-1

DO 22 I = 2, L-1

B (I, J) = (A (I-1, J) + A (I, J-1) + A (I +1, J) + A (I, J +1)) / 4

22 CONTINUE

! $ OMP END DO

! $ OMP END PARALLEL

DO 21 J = 2, L-1

! $ OMP PARALLEL

! $ OMP DO SHARED (J), REDUCTION (EPS, MAX)

DO 21 I = 2, L-1

EPS = MAX (EPS, ABS (B (I, J) - A (I, J)))

A (I, J) = B (I, J)

! $ OMP END DO

! $ OMP END PARALLEL

1 лютому CONTINUE

Вартість = 9 * 6 * 6 / 4 +14 = 95

Кількість приватних = 2

Час ініціалізації = 5

Час синхронізації змінних і видалення регіону = 7

Разом: 14

Вартість = 6 * (9 * 6 / 4 +12) = 153

Кількість приватних = 1

Час ініціалізації = 5

Час синхронізації змінних і видалення регіону = 7

Разом: 12

Рис. 13. Порівняння варіантів розпаралелювання в 3-му регіоні програми "Якобі".

На Рис. 13 показані можливі розглянуті варіанти розпаралелювання: циклу по J в лівій частині і циклу по I в лівій частині. Вартість послідовна = 9 * 6 * 6 = 324, отже, буде обраний 1-й варіант з Рис. 13.

2-й і 3-й паралельні регіони об'єднаються в один регіон, тому що немає суперечностей щодо локалізації змінних. Перевірка на NOWAIT не буде успішна: для звернення A (I, J) = B (I, J) є звернення B (I, J) = (A (I -1, J) + A (I, J -1) + A (I +1, J) + A (I, J +1)) / 4 (може виникнути ситуація, коли однієї нитки доведеться використовувати "старе" значення масиву A у другому циклі).

Крок 3 і Крок 4

На кроці 3 не знайдеться паралельних сусідніх паралельних регіонів для склеювання. Із усіляких альтернативних локалізацій жодна не буде прийнята, тому що в будь-який з них кількість приватних змінних (а отже і оціночна функція будуть рости). Для проставляння threadprivate не знайдеться жодного приватного масиву.

На кроці 4 отримаємо вихідну програму:

program jac

parameter (l = 8, itmax = 20)

real a (l, l), eps, maxeps, b (l, l)

! arrays A and B with block distribution

print *,'********** TEST_JACOBI **********'

maxeps = 5.000000e-008

! Nest of two parallel loops, iteration (i, j) will be executed on

! Processor, which is owner of element A (i, j)

! OMP PARALLEL PRIVATE (i)

! OMP DO

do j = 1, l

do i = 1, l

a (i, j) = 0.

if (i. eq. 1. or. j. eq. 1. or. i. eq. l. or. j. eq. l) then

b (i, j) = 0.

else

b (i, j) = 1. + I + j

endif

enddo

! OMP ENDDO

! OMP END PARALLEL

do it = 1, itmax

eps = 0

! Variable EPS is used for calculation of maximum value

! OMP PARALLEL PRIVATE (i)

! OMP DO REDUCTION (MAX: eps)

do j = 2, l - 1

do i = 2, l - 1

eps = max (eps, abs (b (i, j) - a (i, j)))

a (i, j) = b (i, j)

enddo

! Copying shadow elements of array A from

! Neighbouring processors before loop execution

! OMP ENDDO

! OMP DO

do j = 2, l - 1

do i = 2, l - 1

b (i, j) = (a (i - 1, j) + a (i, j - 1) + a (i + 1, j) + a (i, j +

& 1)) / 4

enddo

! OMP ENDDO

! OMP END PARALLEL

print 200, it, eps

200 FORMAT ('IT =', I4, 'EPS =', E14.7)

if (eps. lt. 5.000000e-008) goto 3

enddo

3 open (unit = 3, file = 'JAC.DAT', form = 'FORMATTED', status = 'UNKNO

& WN ')

write (unit = 3, fmt = *) b

close (unit = 3)

end

Для даної програми буде видана наступна оцінка продуктивності:

Загальний час послідовного виконання: 10547 у.о.

Загальний час паралельного виконання (4 нитки): 3231 у.о

Сумарне прискорення: у 3,26 рази

Програма "Sor"

Лістинг послідовної програми

PROGRAM SOR

PARAMETER (N = 10)

REAL A (N, N), EPS, MAXEPS, W

INTEGER ITMAX

PRINT *,'********** TEST_SOR **********'

ITMAX = 20

MAXEPS = 0.5E - 5

W = 0.5

DO 1 J = 1, N

DO 1 I = 1, N

IF (I. EQ.J) THEN

A (I, J) = N + 2

ELSE

A (I, J) = -1.0

ENDIF

1CONTINUE

DO 2 IT = 1, ITMAX

EPS = 0.

DO 21 J = 2, N-1

DO 21 I = 2, N-1

S = A (I, J)

A (I, J) = (W / 4) * (A (I-1, J) + A (I +1, J) + A (I, J-1) +

* A (I, J +1)) + (1-W) * A (I, J)

EPS = MAX (EPS, ABS (S - A (I, J)))

21CONTINUE PRINT 200, IT, EPS

200 FORMAT ('IT =', I4, 'EPS =', E14.7)

IF (EPS. LT. MAXEPS) GO TO 4

2CONTINUE

4 OPEN (3, FILE = 'SOR.DAT', FORM = 'FORMATTED', STATUS = 'UNKNOWN')

WRITE (3, *) A CLOSE (3) END

Перше внутрішнє представлення для циклів

(1) Тип: ППЦ, рівень = 0, число ітерацій = 8

Використання змінних:

Ім'я: i. Позначки: PRIVATE, SET, SHARED, NO

Ім'я: j. Позначки: PRIVATE, IND, SHARED, NO

Ім'я: a. Позначки: PRIVATE, POS, SHARED, DEF

(2) Тип: ППЦ, рівень = 1, число ітерацій = 8

Використання змінних:

Ім'я: i. Позначки: PRIVATE, IND, SHARED, NO

Ім'я: j. Позначки: PRIVATE, POS, SHARED, DEF

Ім'я: a. Позначки: PRIVATE, POS, SHARED, DEF

(3) Тип: ЦНР, рівень = 0, число ітерацій = 20

Використання змінних:

Ім'я: eps. Позначки: PRIVATE, SET, SHARED, NO

Ім'я: j. Позначки: PRIVATE, SET, SHARED, NO

Ім'я: i. Позначки: PRIVATE, SET, SHARED, NO

Ім'я: a. Позначки: PRIVATE, NO, SHARED, SET ORDERED! PIPELINE!

Ім'я: s. Позначки: PRIVATE, SET, SHARED, NO

(4) Тип: ППЦ, рівень = 1, число ітерацій = 6

Використання змінних:

Ім'я: i. Позначки: PRIVATE, SET, SHARED, NO

Ім'я: eps. Позначки: REDUCTION, MAX, SHARED, NO

Ім'я: j. Позначки: PRIVATE, IND, SHARED, NO

Ім'я: a. Позначки: PRIVATE, NO, SHARED, SET, rw = 2 ORDERED! PIPELINE!

Ім'я: s. Позначки: PRIVATE, SET, SHARED, NO

(5) Тип: ППЦ, рівень = 2, число ітерацій = 6

Використання змінних:

Ім'я: i. Позначки: PRIVATE, IND, SHARED, NO

Ім'я: j. Позначки: PRIVATE, POS, SHARED, DEF

Ім'я: eps. Позначки: REDUCTION, MAX, SHARED, NO

Ім'я: a. Позначки: PRIVATE, NO, SHARED, SET, rw = 2 ORDERED! PIPELINE!

Ім'я: s. Позначки: PRIVATE, SET, SHARED, NO

Другий крок

На цьому кроці буде влаштований перебір різних варіантів розпаралелювання. Розглянемо їх, групуючи по регіонах. Всі варіанти будемо розглядати при числі процесорів = 4.

1-й регіон: цикли (1) і (2). Тут буде розглянуто 3 варіанти, час послідовного виконання 1 витка = 1.

! $ OMP PARALLEL PRIVATE (I)

! $ OMP DO

DO 1 J = 1, N

DO 1 I = 1, N

IF (I. EQ.J) THEN

A (I, J) = N + 2

ELSE

A (I, J) = -1.0

ENDIF

1CONTINUE

! $ OMP END DO

! $ OMP END PARALLEL

DO 1 J = 1, N

! $ OMP PARALLEL

! $ OMP DO

DO 1 I = 1, N

IF (I. EQ.J) THEN

A (I, J) = N + 2

ELSE

A (I, J) = -1.0

ENDIF

! $ OMP END DO

! $ OMP END PARALLEL

1 CONTINUE

Вартість = 1 * 10 * 10 / 4 + 14 = 39

Кількість приватних = 2

Час ініціалізації = 5

Час синхронізації змінних і видалення регіону = 7

Разом: 14

Вартість = 10 * (1 * 10 / 4 + 12) = 145

Кількість приватних = 1

Час ініціалізації = 5

Час синхронізації змінних і видалення регіону = 6

Разом: 12

Рис. 14. Порівняння варіантів розпаралелювання в 1-му регіоні програми "SOR".

На Рис. 14 показані можливі розглянуті варіанти розпаралелювання: циклу по J в лівій частині і циклу по I в лівій частині. Вартість послідовна = 10 * 10 = 100, отже, буде обраний варіант, показаний у лівій частині Рис. 14.

2-й регіон: цикли (4) і (5). Тут буде розглянуто 4 варіанти, час послідовного виконання 1 витка = 22.

! $ OMP PARALLEL PRIVATE (S) PRIVATE (I)

! $ OMP DO REDUCTION (EPS, MAX)

DO 21 J = 2, N-1

DO 21 I = 2, N-1

! $ OMP ORDERED

S = A (I, J)

A (I, J) = (W / 4) * (A (I-1, J) + A (I +1, J) + A (I, J-1) +

* A (I, J +1)) + (1-W) * A (I, J)

EPS = MAX (EPS, ABS (S - A (I, J)))

! $ OMP END ORDERED

21CONTINUE

! $ OMP END DO

! $ OMP END PARALLEL

DO 21 J = 2, N-1

! $ OMP PARALLEL PRIVATE (S)

! $ OMP DO REDUCTION (EPS, MAX)

DO 21 I = 2, N-1

! $ OMP ORDERED

S = A (I, J)

A (I, J) = (W / 4) * (A (I-1, J) + A (I +1, J) + A (I, J-1) +

* A (I, J +1)) + (1-W) * A (I, J)

EPS = MAX (EPS, ABS (S - A (I, J)))! $ OMP END ORDERED

! $ OMP END DO

! $ OMP END PARALLEL

1 лютому CONTINUE

Вартість = 22 * 8 * 8 + 18 = 1 426

Кількість приватних = 4

Час ініціалізації = 5

Час синхронізації змінних і видалення регіону = 9

Разом: 18

Вартість = 8 * (22 * 8 + 16) = 1536

Кількість приватних = 3

Час ініціалізації = 5

Час синхронізації змінних і видалення регіону = 8

Разом: 16

Рис. 15. Порівняння варіантів розпаралелювання в 2-му регіоні програми "SOR" з директивою ORDERED.

! $ OMP PARALLEL

! $ Iam = omp_get_thread_num ()

! $ Numt = omp_get_num_threads ()

! $ ISYNC (IAM) = 0

! $ ILIMIT = MIN (NUMT-1, N-1-2)

! $ OMP BARRIER

DO 21 J = 2, N-1

! $ OMP DO PRIVATE (S), REDUCTION (EPS, MAX)

! $ IF (IAM. GT. 0. AND. IAM. LE. ILIMIT) THEN

! $ DO WHILE (ISYNC (IAM-1). EQ. 0)

! $ OMP FLUSH (ISYNC)

! $ ENDDO

! $ ISYNC (IAM-1) = 0

! $ OMP FLUSH (ISYNC)

! $ ENDIF

DO 21 I = 2, N-1

S = A (I, J)

A (I, J) = (W / 4) * (A (I-1, J) + A (I +1, J) + A (I, J-1) +

* A (I, J +1)) + (1-W) * A (I, J)

EPS = MAX (EPS, ABS (S - A (I, J)))

! $ OMP ENDDO NOWAIT

! $ IF (IAM. LT. ILIMIT) THEN

! $ DO WHILE (ISYNC (IAM). EQ. 1)

! $ OMP FLUSH (ISYNC)

! $ ENDDO

! $ ISYNC (IAM) = 1

! $ OMP FLUSH (ISYNC)

! $ ENDIF

! $ OMP END DO

! $ OMP BARRIER

! $ OMP END PARALLEL

21 CONTINUE

Вартість = 22 * 32 +3 +9 +22 = 738

Кількість дій конвеєра = 32

Кількість приватних = 3

Час ініціалізації конвеєра без урахування приватних = 5 + 4 = 9

Час синхронізації змінних і видалення регіону = 3 +5 +4 +3 +3 +4 = 22 (синхронізація приватних + ініціалізація регіону + бар'єр до першого циклу + по бар'єру під час ініціалізації кожної нитки + по бар'єру під час ініціалізації подальшої нитки + бар'єр у кінці регіону)

Рис. 16. Схема розпаралелювання в 2-му регіоні програми "SOR" при конвеєрному варіанті.

На Рис. 15 і Рис. 16 показані варіанти паралелізму, які будуть перебиратися "Експертом". Вартість послідовна = 22 * 8 * 8 = 1408, отже, буде обраний варіант c конвеєром.

Крок 3 та Крок 4

На кроці 3 не знайдеться паралельних сусідніх паралельних регіонів для склеювання. Із усіляких альтернативних локалізацій жодна не буде прийнята, тому що в будь-який з них кількість приватних змінних (а отже, і оцінна функція будуть рости). Для проставляння threadprivate не знайдеться жодного приватного масиву.

На кроці 4 отримаємо вихідну програму для варіанту завдання з 4 процесорами:

program sor

parameter (n = 10)

real a (n, n), eps, maxeps, w

integer itmax

! $ INTEGER OMP_GET_NUM_THREADS, OMP_GET_THREAD_NUM

! $ INTEGER IAM, NUMT, ISYNC (4)

print *,'********** TEST_SOR **********'

itmax = 20

maxeps = 5.000000e-006

w = 5.000000e-001

! $ OMP PARALLEL PRIVATE (i)

! $ OMP DO

do j = 1, n

do i = 1, n

if (i. eq. j) then

a (i, j) = n + 2

else

a (i, j) = (- (1.0))

endif

enddo

! $ OMP END DO

! $ OMP END PARALLEL

do it = 1,20

eps = 0

! $ OMP PARALLEL PRIVATE (IAM, NUMT, ILIMIT) PRIVATE (i) SHARED (a) PRIVATE (s) & & REDUCTION (MAX: eps)

! $ Iam = omp_get_thread_num ()

! $ Numt = omp_get_num_threads ()

! $ ISYNC (IAM) = 0

! $ ILIMIT = min (NUMT-1, n-1-2)

! $ OMP BARRIER

do j = 2, n - 1

! $ IF (IAM. GT. 0. AND. IAM. LE. ILIMIT) THEN

! $ DO WHILE (ISYNC (IAM-1). EQ. 0)

! $ OMP FLUSH (ISYNC)

! $ ENDDO

! $ ISYNC (IAM-1) = 0

! $ OMP FLUSH (ISYNC)

! $ ENDIF

! $ OMP DO

do i = 2, n - 1

s = a (i, j)

a (i, j) = 5.000000e-001 / 4 * (a (i - 1, j) + a (i + 1, j) + a

& (I, j - 1) + a (i, j + 1)) + (1 - 5.000000e-001) * a (i, j)

eps = max (eps, abs (s - a (i, j)))

enddo

! $ OMP ENDDO NOWAIT

! $ IF (IAM. LT. ILIMIT) THEN

! $ DO WHILE (ISYNC (IAM). EQ. 1)

! $ OMP FLUSH (ISYNC)

! $ ENDDO

! $ ISYNC (IAM) = 1

! $ OMP FLUSH (ISYNC)

! $ ENDIF

enddo

! $ OMP BARRIER

! $ OMP END PARALLEL

print 200, it, eps

200 FORMAT ('IT =', I4, 'EPS =', E14.7)

if (eps. lt. 5.000000e-006) goto 4

enddo

4 open (unit = 3, file = 'SOR.DAT', form = 'FORMATTED', status = 'UNKNO

& WN ')

write (unit = 3, fmt = *) a

close (unit = 3)

end

Для даної програми буде видана наступна оцінка продуктивності:

Загальний час послідовного виконання: 28343 у.о.

Загальний час паралельного виконання (4 нитки): 14880 у.о.

Сумарне прискорення: у 1, 9 рази

Програма "Модифікований SOR"

Даний приклад наведено для того, щоб показати роботу "Експерта" на залежностях за даними в масиві, для якого неможливе застосування конвеєра.

Лістинг послідовної програми

PROGRAM SOR

PARAMETER (N = 10)

REAL A (N, N), B (N, N), EPS, MAXEPS, W

INTEGER ITMAX

PRINT *,'********** TEST_SOR **********'

ITMAX = 20

MAXEPS = 0.5E - 5

W = 0.5

DO 1 J = 1, N

DO 1 I = 1, N

IF (I. EQ.J) THEN

A (I, J) = N + 2

ELSE

A (I, J) = -1.0

ENDIF

1CONTINUE

DO 2 IT = 1, ITMAX

EPS = 0.

DO 21 J = 2, N-1

DO 21 I = 2, N-1

S = A (I, J)

A (I, J) = (W / 4) * (A (I-1, J) + A (I +1, J) + A (I, J-1) +

* A (I, J +1)) + (1-W) * A (I +1, J +1)

B (I, J) = A (I, J)

EPS = MAX (EPS, ABS (S - B (I, J)))

21CONTINUE

PRINT 200, IT, EPS

200 FORMAT ('IT =', I4, 'EPS =', E14.7)

IF (EPS. LT. MAXEPS) GO TO 4

2CONTINUE

4 OPEN (3, FILE = 'SOR.DAT', FORM = 'FORMATTED', STATUS = 'UNKNOWN')

WRITE (3, *) A

CLOSE (3)

END

Робота "Експерта"

Для даної програми будуть проведені дії, аналогічні тим, що описані в пункті 5.5.2. Зупинимося лише на відмінностях у кроці 2 і вихідних даних.

2-й регіон: цикли (4) і (5). Тут буде розглянуто 3 варіанти, час послідовного виконання перших 3 директив = 19, 4-ї директиви = 4:

! $ OMP PARALLEL PRIVATE (S) PRIVATE (I)

! $ OMP DO REDUCTION (EPS, MAX)

DO 21 J = 2, N-1

DO 21 I = 2, N-1

! $ OMP ORDERED

S = A (I, J)

A (I, J) = (W / 4) * (A (I-1, J) + A (I +1, J) + A (I, J-1) +

* A (I, J +1)) + (1-W) * A (I +1, J +1)

B (I, J) = A (I, J)

! $ OMP END ORDERED

EPS = MAX (EPS, ABS (S - B (I, J)))

21CONTINUE

! $ OMP END DO

! $ OMP END PARALLEL

DO 21 J = 2, N-1

! $ OMP PARALLEL PRIVATE (S)

! $ OMP DO REDUCTION (EPS, MAX)

DO 21 I = 2, N-1

! $ OMP ORDERED

S = A (I, J)

A (I, J) = (W / 4) * (A (I-1, J) + A (I +1, J) + A (I, J-1) +

* A (I, J +1)) + (1-W) * A (I +1, J +1)

B (I, J) = A (I, J)

! $ OMP END ORDERED

EPS = MAX (EPS, ABS (S - B (I, J)))

! $ OMP END DO

! $ OMP END PARALLEL

1 лютому CONTINUE

Вартість = 19 * 8 * 8 + 4 * 8 * 8 / 4 + 18 = 1298

Кількість приватних = 4

Час ініціалізації = 5

Час синхронізації змінних і видалення регіону = 9

Разом: 18

Вартість = 8 * (19 * 8 + 4 * 8 / 4 + 16) = 1408

Кількість приватних = 3

Час ініціалізації = 5

Час синхронізації змінних і видалення регіону = 8

Разом: 16

Рис. 17. Порівняння варіантів розпаралелювання в 2-му регіоні програми "модифікований SOR".

На Рис. 17 показані можливі варіанти паралелізму для даного регіону. Як видно, випадок з конвеєром не буде розглянуто, через те, що елемент A (I, J) залежить від "бічного" елементи A (I +1, J +1). Вартість послідовна = 23 * 8 * 8 = 1472, отже, буде обраний 1-й варіант.

На виході отримаємо наступну програму:

program sor

parameter (n = 10)

real a (n, n), b (n, n), eps, maxeps, w

integer itmax

print *,'********** TEST_SOR **********'

itmax = 20

maxeps = 5.000000e-006

w = 5.000000e-001

! $ OMP PARALLEL PRIVATE (i)

! $ OMP DO

do j = 1, n

do i = 1, n

if (i. eq. j) then

a (i, j) = n + 2

else

a (i, j) = (- (1.0))

endif

enddo

! $ OMP END DO

! $ OMP END PARALLEL

do it = 1,20

eps = 0

! $ OMP PARALLEL PRIVATE (i) SHARED (a) PRIVATE (s)

! $ OMP DO ORDERED REDUCTION (MAX: eps)

do j = 2, n - 1

do i = 2, n - 1

! $ OMP ORDERED

s = a (i, j)

a (i, j) = 5.000000e-001 / 4 * (a (i - 1, j) + a (i + 1, j) + a

& (I, j - 1) + a (i, j + 1)) + (1 - 5.000000e-001) * a (i + 1, j + 1)

b (i, j) = a (i, j)

! $ OMP END ORDERED

eps = max (eps, abs (s - b (i, j)))

enddo

! $ OMP END DO

! $ OMP END PARALLEL

print 200, it, eps

200 FORMAT ('IT =', I4, 'EPS =', E14.7)

if (eps. lt. 5.000000e-006) goto 4

enddo

4 open (unit = 3, file = 'SOR.DAT', form = 'FORMATTED', status = 'UNKNO

& WN ')

write (unit = 3, fmt = *) a

close (unit = 3)

end

Загальний час послідовного виконання: 29623 у.о.

Загальний час паралельного виконання (4 нитки): 26143 у.о.

Сумарне прискорення: у 1, 13 рази

Програма "Модифікований Якобі"

Даний приклад наведено для того, щоб показати роботу "Експерта", при установці директиви NOWAIT. Вихідна програма "Якобі" була змінена, щоб перевірка установки NOWAIT була успішна. Робота "Експерта" на цьому прикладі повторює дії з пункту 5.5.1 за винятком того, що перевірка установки NOWAIT дасть позитивний результат.

Лістинг послідовної програми

PROGRAM JAC

PARAMETER (L = 8, ITMAX = 20)

REAL A (L, L), EPS, MAXEPS, B (L, L), C (L, L)

C arrays A and B with block distribution

PRINT *,'********** TEST_JACOBI **********'

MAXEPS = 0.5E - 7

Cnest of two parallel loops, iteration (i, j) will be executed on

Cprocessor, which is owner of element A (i, j)

DO 1 J = 1, L

DO 1 I = 1, L

A (I, J) = 0.

IF (I.EQ.1. OR. J.EQ.1. OR. I.EQ.L. OR. J.EQ.L) THEN

B (I, J) = 0.

ELSE

B (I, J) = (1. + I + J)

ENDIF

1 CONTINUE

DO 2 IT = 1, ITMAX

EPS = 0.

Cvariable EPS is used for calculation of maximum value

DO 21 J = 2, L-1

DO 21 I = 2, L-1

A (I, J) = B (I, J)

21 CONTINUE

CCopying shadow elements of array A from

Cneighbouring processors before loop execution

DO 22 J = 2, L-1

DO 22 I = 2, L-1

A (I, J) = (C (I-1, J) + C (I, J-1) + C (I +1, J) +

* C (I, J +1)) / 4

22 CONTINUE

PRINT 200, IT, EPS

200 FORMAT ('IT =', I4, 'EPS =', E14.7)

IF (EPS. LT. MAXEPS) GO TO 3

2 CONTINUE

3 OPEN (3, FILE = 'JAC.DAT', FORM = 'FORMATTED', STATUS = 'UNKNOWN')

WRITE (3, *) B

CLOSE (3)

END

Вихідна програма

program jac

parameter (l = 8, itmax = 20)

real a (l, l), eps, maxeps, b (l, l), c (l, l)

! arrays A and B with block distribution

print *,'********** TEST_JACOBI **********'

maxeps = 5.000000e-008

! Nest of two parallel loops, iteration (i, j) will be executed on

! Processor, which is owner of element A (i, j)

! $ OMP PARALLEL PRIVATE (i)

! $ OMP DO

do j = 1, l

do i = 1, l

a (i, j) = 0.

if (i. eq. 1. or. j. eq. 1. or. i. eq. l. or. j. eq. l) then

b (i, j) = 0.

else

b (i, j) = 1. + I + j

endif

enddo

! $ OMP END DO

! $ OMP END PARALLEL

do it = 1, itmax

eps = 0

! Variable EPS is used for calculation of maximum value

! $ OMP PARALLEL PRIVATE (i)

! $ OMP DO

do j = 2, l - 1

do i = 2, l - 1

a (i, j) = b (i, j)

enddo

! Copying shadow elements of array A from

! Neighbouring processors before loop execution

! $ OMP END DO NOWAIT

! $ OMP DO

do j = 2, l - 1

do i = 2, l - 1

a (i, j) = (c (i - 1, j) + c (i, j - 1) + c (i + 1, j) + c (i, j +

& 1)) / 4

enddo

! $ OMP END DO

! $ OMP END PARALLEL

print 200, it, 0

200 FORMAT ('IT =', I4, 'EPS =', E14.7)

if (0. lt. 5.000000e-008) goto 3

enddo

3 open (unit = 3, file = 'JAC.DAT', form = 'FORMATTED', status = 'UNKNO

& WN ')

write (unit = 3, fmt = *) b

close (unit = 3)

end

Загальний час послідовного виконання: 7667 у.о.

Загальний час паралельного виконання (4 нитки): 2471 у.о.

Сумарне прискорення: в 3, 1 рази

Висновок

У рамках дипломної роботи був реалізований "Експерт з розпаралелюванню на мультипроцесор", як компонент "Системи автоматизації розпаралелювання".

Робота системи була протестована на прикладах, описаних у пункті 5.5. В якості вихідного результату формується файл з вихідною програмою, а також файл, що описує покрокові дії "Експерта" з обгрунтуванням причини формування вихідного файлу, а також підраховує прискорення програми.

Проект реалізовано у програмі Visual Studio. NET на мові C + +. Загальний обсяг програмного коду, що реалізує "Експерт" - понад 1800 рядків.

Перелік прийнятих термінів

Потенційно Паралельний Цикл (ППЦ) - цикл, який можна распараллеліть засобами OpenMP, не обов'язково ефективно.

Цикл Неподдающиеся Розпаралелювання (ЦНР) - цикли з залежностями наступних видів:

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

Паралельний регіон - послідовність циклів, лінійних фрагментів, розгалужень, яка буде укладена в рамки! $ OMP PARALLEL -! $ OMP END PARALLEL.

Варіант паралелізму програми (Варіант паралелізму) - варіант директив OpenMP, що описують паралельні області та паралельні цикли (без директив локалізації змінних).

Варіант локалізації змінних (Варіант локалізації) - варіант директив локалізації змінних. Для кожного варіанта паралелізму може існувати кілька варіантів локалізації.

Схема розпаралелювання - фіксація одного варіанта паралелізму і одного варіанта локалізації.

1-е внутрішнє подання - дерево, за структурою схоже з деревом з Бази Даних, у якому позначені всі ППЦ і для кожного ППЦ позначені позначки для локалізації. Є результатом роботи 1-го кроку.

2-е внутрішнє подання - дерево, за структурою схоже з деревом з Бази Даних, в якому розставлені позначки, за якими в базу даних можна занести коментарі з розпаралелюванню (Розпаралелювання і Локалізацію). Є результатом роботи 3-го кроку.

Найкращі коментарі - коментарі такі, що оцінна функція для програми з такими коментарями буде мінімальна в порівнянні з програмою з будь-якими іншими коментарями. Перебування таких коментарів - головне завдання експерта.

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

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