трспо. Лекція Колективні операції обміну повідомленнями в mpi
 Скачать 3.37 Mb.
|
|
Тип даних MPI Тип даних С MPI_CHAR signed char MPI_SHORT signed short int MPI_INT signed int MPI_LONG signed long int MPI_UNSIGNED CHAR unsigned char MPI_UNSIGNED SHORT unsigned short int MPI_UNSIGNED unsigned int MPI_UNSIGNED LONG unsigned long int MPI_FLOAT float MPI_DOUBLE double MPI_LONG_DOUBLE long double MPI_BYTE Немає відповідності MPI_PACKED Немає відповідності У MPI повинні дотримуватися правила сумісності типів. Відповідність типів має, як правило, місце у процедурах відправки і процедурах прийому повідомлень. З базових типів можуть бути сконструйовані більш складні типи даних. Коди завершення Коди завершення повертаються в якості значення функції або через останній аргумент процедури FORTRAN. Виняток становлять підпрограми MPI_wtime і MPI_wtick, в яких повернення коду помилки не передбачено. Використовуються стандартні значення MPI_SUCCESS – при успішному завершенні виклику і MPI_ERR_OTHER – зазвичай при спробі повторного виклику процедури MPI_ INIT. Системою підтримуються і інші помилки. Замість числових кодів в програмах зазвичай використовують спеціальні іменовані константи. Серед них: • MPI_ERR_BUFFER – неправильний вказівник на буфер; • MPI_ERR_COMM – неправильний комунікатор; • MPI_ERR_RANK – неправильний ранг; • MPI_ERR_OP – неправильна операція; • MPI__ERR_ARG – неправильний аргумент; • MPI_ERR_UNKNOWN – невідома помилка; • MPI_ERR_TRUNCATE – повідомлення обрізано при прийомі; • MPI_ERR_INTERN – внутрішня помилка. Зазвичай виникає, якщо системі не вистачає пам'яті. Як влаштована МРІ-програма На початку програми, відразу після заголовка, необхідно підключити відповідний заголовковий файл. В програмі на мові С це mpi.h: #include "mpi.h" У цьому файлі містяться описи констант і змінних бібліотеки MPI. Першим викликом бібліотечної процедури MPI в програмі повинен бути виклик підпрограми ініціалізації MPІ_ INIT, перед ним може розташовуватися тільки виклик MPI_Initialized, з допомогою якого визначають ініціалізована система MPI чи ні. Виклик процедури ініціалізації виконується тільки один раз. Процедура ініціалізації створює комунікатор зі стандартним ім'ям MPI_COMM_WORLD. Це ім'я вказується в усіх наступних викликах процедур MPI. Після виконання всіх обмінів повідомленнями в програмі повинен розташовуватися виклик процедури MPІ_FINALIZE(ierr). В результаті цього виклику видаляються структури даних MPI і виконуються інші необхідні дії. Програміст повинен подбати про те, щоб до моменту виклику процедури MPІ_ FINALIZE були завершені всі пересилання даних. Після виконання даного виклику інші виклики процедур MPI, включаючи MPI_ INIT, неприпустимі. Лістинг 6.1. Найпростіша MPI-програма на мові С #include "mpi.h" #include { int myid, numprocs; MPI_INIT (&argc, &argv) ; MPI_COMM_SIZE(MPI_COMM_WORLD, &numprocs); MPI_COMM_RANK(MPI_COMM_WORLD, &myid) ; fprintf (stdout, "Process %d of %d\n", myid, numprocs) MPI_FINALIZE() ; return 0; } Лекція 5. Етапи розробки паралельних алгоритмів План лекції: 1. Загальна схема розробки паралельного алгоритму 1.1. Декомпозиція 1.2. Проектування комунікацій 1.3. Укрупнення 1.4. Планування обчислень 2. Паралельні методи матричного множення 2.1. Постановка задачі 2.2. Аналіз ефективності 3. Базовий паралельний алгоритм множення матриць 3.1. Визначення завдань 3.2. Виділення інформаційних залежностей 3.3. Масштабування і розподіл підзадач 3.4. Аналіз ефективності 4. Вихідна проблема – стохастичне вирівнювання 4.1. Аналіз алгоритму стохастичного вирівнювання 4.2. Паралельне стохастичне вирівнювання 4.3. Інші альтернативи 1. Загальна схема розробки паралельного алгоритму Паралельний алгоритм - це алгоритм, який може бути реалізований по частинах на безлічі різних обчислювальних пристроїв з наступним об'єднанням отриманих результатів і отримання коректного результату. При розробці паралельних програм виділяють чотири етапи: • декомпозиція; • проектування комунікацій; • укрупнення; • планування обчислень. Рисунок 5.1. Загальна схема розробки паралельного алгоритму 1.1. Декомпозиція На цьому етапі завдання аналізується, проводиться оцінка можливості її розпаралелювання. У разі перспективності створення ефективної паралельної програми проводиться розподіл задачі більш дрібні частини – фрагменти структур даних і фрагменти алгоритму (фундаментальні підзадачі). Такий розподіл необхідний для підвищення максимального паралелізму задачи. Кількість фундаментальних задач повинна бути, принаймні, на порядок більше планованої кількості використовуваних процесорів, а самі підзадачі в перспективі повинні мати приблизно однаковий розмір. Перетинання виділених фрагментів алгоритму повинне бути зведене до мінімуму, щоб уникнути дублювання обчислень (наслідок – зниження ефективності паралельного алгоритму). Декомпозиція повинна бути такою, щоб при збільшенні розміру задачі зростала б кількість фундаментальних підзадач, а не розмір кожної підзадачі. Розмір фундаментальної підзадачі визначається ступенем деталізації розпаралеленого алгоритму, яка характеризується кількістю операцій в підзадачі. Якщо в алгоритмі можна виділити підзадачі, в яких виконується лише кілька операцій, то говорять про дрібнозернистий паралелізм. Якщо фрагменти алгоритму (фундаментальні підзадачі) визначаються на рівні процедур, в яких кількість арифметичних операцій становить близько 10³ , то має місце середньоблочний паралелізм. Грубозернистий паралелізм алгоритму характеризується можливістю виділення декількох великих задач на рівні окремих програм, які можуть виконуватися на комп'ютері з паралельною архітектурою незалежно, що вимагає, як правило, спеціальної організації обчислень. На цьому етапі розробки програми для паралельних обчислень не враховуються особливості архітектури багатопроцесорної обчислювальної системи. Розрізняють декомпозицію за даними і функціональну декомпозицію. У першому випадку спочатку фрагментуються дані, з якими зв'язуються операції алгоритму їх обробки, а в другому – спочатку декомпозується алгоритм обробки даних. Прикладами для декомпозиції за даними можуть служити одновимірна, двомірна чи тривимірна декомпозиція перетворюваних за певними правилами елементів масиву, що має три і більше індексів. Одночасне обчислення за послідовним алгоритмом суми, різниці, скалярного і векторного добутків двох заданих векторів розміром n – це приклад функціональної декомпозиції. 1.2. Проектування комунікацій На цьому етапі встановлюються комунікації (зв'язки) між фундаментальними підзадачами. Визначається комунікаційна модель передачі даних між підзадачами. Вибираються алгоритми і методи комунікацій. При цьому необхідно враховувати типи комунікацій. Так, наявність тільки локальних комунікацій, коли кожна підзадача пов'язана лише з невеликим числом інших підзадач, дає перевагу при побудові паралельної програми порівняно з глобальними комунікаціями (кожна підзадача пов'язана з великим числом інших підзадач). Також простіше будувати паралельну програму, якщо тип комунікацій структурований (комунікації утворюють регулярну структуру, наприклад з топологією «решітка»), статичний (комунікаційна структура не змінюється з часом), синхронний (відправник і одержувач повністю координують передачу даних між собою). Однак використання динамічних комунікацій (комунікаційна структура, що зв'язує підзадачі, змінюється з плином часу) і асинхронних комунікацій (відправник не контролює отримання даних, а одержувач – їх відправку) відкриває нові можливості в створенні ефективних паралельних програм. При розробці комунікаційної моделі передачі даних між фундаментальними підзадачами необхідно виконувати наступні вимоги: • у кожної підзадачі кількість комунікацій (зв'язків) з іншими фрагментами алгоритму має бути приблизно однакова; • об'єм даних, що одночасно передаються по комунікаціям, повинен бути однаковим; • перевагу у використанні мають локальні комунікації, за якими передача даних здійснюється одночасно; • по можливості передачу даних краще поєднувати з обчисленнями; • передача даних по комунікаціям не повинна призводити до неодночасного виконання фундаментальних завдань. На цьому етапі не враховується архітектура суперкомп'ютера. 1.3. Укрупнення Проводиться об'єднання підзадач в більш великі блоки для підвищення ефективності створюваного алгоритму – щоб, наприклад, знизити комунікаційні витрати або трудомісткість розробки паралельного алгоритму. Враховується архітектура багатопроцесорної системи, для якої розробляється паралельна програма. Кількість укрупнених блоків фундаментальних завдань має відповідати кількості використовуваних процесорів (ядер). Першими кандидатами для об'єднання в укрупнені блоки є фундаментальні підзадачі, які не можуть виконуватися одночасно і незалежно. При укрупненні іноді вдається знизити комунікаційні витрати за рахунок заміни передачі даних дублюванням обчислень у різних підзадачах або блоках підзадач. Укрупнення повинно виконуватися таким чином, щоб зберігалися висока масштабованість і продуктивність паралельної програми. Кажуть, що алгоритм або програма є масштабованими, якщо ефективність Ep(n,p) можна утримувати на постійному ненульовому значенні при одночасному збільшенні кількості використовуваних процесорів p і розміру задачі n. 1.4. Планування обчислень На цьому етапі здійснюється призначення укрупнених підзадач певним процесорам у відповідності з вимогами зниження комунікаційних витрат і забезпечення паралелізму. Особливе значення цей етап має при проведенні обчислень на гетерогенних багатопроцесорних системах, що характеризуються наявністю різних по продуктивності обчислювальних вузлів і компонентів міжпроцесорної мережі. Стратегія розміщення укрупнених блоків завдань на процесорних елементах будується з урахуванням основного критерію – мінімізації часу виконання паралельної програми. Найчастіше використовуються стратегії «господар/працівник», ієрархічні та децентралізовані схеми (рис. 5.2-5.5). У стратегії «господар/працівник» головний блок (master) відповідає за не перетинаючий розподіл основного обчислювального навантаження (укрупнених блоків підзадач) між процесорами – працівниками (slave), контролювання її виконання і збір розрахункових даних для підготовки основного результату розв'язання задачі (рис. 5.2). Рисунок 5.2. Стратегія «господар/працівник» розміщення укрупнених блоків по шести процесорним елементам В ієрархічній схемі «господар/працівник» обсяг обчислювальної роботи також розділений між процесорами-працівниками, проте кожен з них виступає в якості процесора-«господаря» по відношенню до процесорів- «працівників», розташованих на більш низькому ступені в цій ієрархічній схемі (рис. 5.3). Характер взаємодії між рівнями ієрархії подібний до взаємодії процесорів в стратегії «господар/працівник». Рисунок 5.3. Ієрархічна схема «господар/працівник» розміщення укрупнених блоків по процесорним елементам У децентралізованій схемі головний блок відсутній, обчислення в блоках виконуються, дотримуючись певної стратегії (мал. 5.4). Рисунок 5.4. Децентралізована схема розміщення укрупнених блоків по процесорним елементам У розглянутій вище схемі розробки паралельних алгоритмів і програм важливу роль в ідентифікації паралелізму алгоритму відіграє аналіз графа алгоритму, який може бути побудований після виконання етапів декомпозиції та проектування комунікацій. Граф алгоритму являє собою орієнтований граф, що складається з вершин, відповідних певним фрагментам (фундаментальним підзадачам) алгоритму, і спрямованих дуг, що відповідають за передачу даних між ними (рис. 5.5). По дугах (комунікаціях) результати, отримані при виконанні фрагментів алгоритму, передаються в якості аргументів для продовження алгоритму іншими фрагментами. Стрілка з вершини A до вершини B графа алгоритму означає, що задача A повинна бути виконана перед завданням B. У цьому випадку має місце залежність завдання B від результату виконання завдання A. Якщо завдання A і B не пов'язані між собою, то вони незалежні і можуть виконуватися одночасно (паралельно). На рис. 5.5 представлені графи деяких алгоритмів. Вершини представляють собою підзадачі або фрагменти алгоритмів. Буква всередині вершини визначає операцію алгоритму. Стрілки означають залежність між підзадачами. Рисунок 5.5. Паралелізм у графах алгоритмів Граф алгоритму 1 являє паралелізм за даними. Три підзадачі з різними аргументами можуть виконувати операцію B. Граф алгоритму 2 показує функціональний паралелізм. Підзадачі, які реалізують операції B, C, D, можуть виконуватися одночасно. Граф алгоритму 3 відповідає лінійним залежностям між операціями A, B, C, які виконуються одна за одною. 2. Паралельні методи матричного множення 2.1. Постановка задачі Множення матриці A розміру m×n і матриці B розміру n×l призводить до отримання матриці С розміру m×l , кожен елемент якої визначається у відповідності з виразом: Як випливає з цього , кожен елемент результуючої матриці є скалярний добуток відповідних рядка матриці A і стовпця матриці B: Цей алгоритм передбачає виконання m*n*l операцій множення і стільки ж операцій додавання елементів вихідних матриць. При множенні квадратних матриць розміру n×n кількість виконаних операцій має порядок O(n³). Відомі послідовні алгоритми множення матриць, що володіють меншою обчислювальною складністю, але ці алгоритми вимагають певних зусиль для їх освоєння і, як результат, у даній главі при розробці паралельних методів як основи буде використовуватися наведений вище послідовний алгоритм. Також будемо припускати, що всі матриці є квадратними і мають розмір n×n. Послідовний алгоритм множення матриць реалізується трьома вкладеними циклами: double MatrixA[Size][Size]; double MatrixB[Size][Size]; double MatrixC[Size][Size]; int i,j,k; for (i=0; i MatrixA[i][k]*MatrixB[k][j]; } } } Цей алгоритм є ітеративним і орієнтованим на послідовне обчислення рядків матриці С. Дійсно, під час виконання однієї ітерації зовнішнього циклу (циклу по змінній i) обчислюється один рядок результуючої матриці (рис. 5.6) Рисунок 5.6. Перша ітерація циклу На першій ітерації циклу по змінній i використовується перший рядок матриці A і всі стовпці матриці B для того, щоб обчислити елементи першого рядка результуючої матриці С. Оскільки кожен елемент результуючої матриці є скалярний добуток рядка і стовпця вихідних матриць, то для обчислення всіх елементів матриці розміром n×n необхідно виконати n ² (2n-1) скалярних операцій і витратити час: (1) 2.2. Аналіз ефективності Час виконання алгоритму складається з часу, що витрачається безпосередньо на обчислення, і часу, необхідного на читання даних з оперативної пам'яті в кеш процесора. Час обчислень може бути оцінено з використанням формули (1). Тепер необхідно оцінити обсяг даних, які необхідно прочитати з оперативної пам'яті в кеш обчислювального елемента у випадку, коли розмір матриць настільки великий, що вони одночасно не можуть бути поміщені в кеш. Для обчислення одного елемента результуючої матриці необхідно прочитати в кеш елементи одного рядка матриці А та одного стовпця матриці B. Для запису отриманого результату додатково потрібно читання відповідного елемента матриці С з оперативної пам'яті. Важливо відзначити, що наведені оцінки кількості даних, що читаються з пам'яті, справедливі, якщо всі ці дані відсутні у кеші. В реальності частина цих даних може вже присутня в кеші, і тоді обсяг переписуваних даних в кеш зменшується. Розташування даних в кожному конкретному випадку залежить від багатьох величин (розмір кешу, обсягу оброблюваних даних, стратегії заміщення рядків кеша тощо). Детальний аналіз всіх цих моментів є досить важким. Можливий вихід в такому випадку полягає в оцінці максимально можливого обсягу даних, що переміщуються з пам'яті в кеш (побудова оцінки зверху). У нашому випадку всього необхідно обчислити n² елементів результуючої матриці – тоді, припускаючи, що при обчисленні кожного чергового елемента потрібно прочитати в кеш всі необхідні дані, випливає, що загальний обсяг даних, необхідних для читання з оперативної пам'яті в кеш, не перевищує величини 2n³ +n². Таким чином, оцінка часу виконання послідовного алгоритму множення матриць може бути представлена наступним чином: (2) де β є пропускна здатність каналу доступу до оперативної пам'яті (константа 64 введена для обліку факту, що в випадку кеш-промаху з ОП читається кеш- рядок розміром 64 байти). Якщо окрім пропускної здатності врахувати латентність пам'яті, модель матиме наступний вигляд: (3) де α є латентність оперативної пам'яті. Обидві попередні моделі є моделями на найгірший випадок і дають сильно завищену оцінку часу виконання алгоритму, так як доступ до оперативної пам'яті відбувається не при кожному зверненні до елементу. Як і раніше, введемо в модель (3) величину γ, 0 ≤ γ ≤1, для завдання частоти виникнення кеш-промахів. Тоді оцінка часу виконання алгоритму матричного множення приймає вигляд: (4) 3. Базовий паралельний алгоритм множення матриць 3.1. Визначення задач З визначення операції матричного множення випливає, що обчислення всіх елементів матриці С може бути виконано незалежно один від одного. Як результат, можливий підхід для організації паралельних обчислень полягає у використанні в якості базової підзадачі процедури визначення одного елемента результуючої матриці С. Для проведення всіх необхідних обчислень кожна підзадача повинна виконувати обчислення над елементами одного рядка матриці |