трспо. Лекція Колективні операції обміну повідомленнями в mpi
 Скачать 3.37 Mb.
|
|
А та одного стовпця матриці В. Загальна кількість одержуваних при такому підході підзадач виявляється рівним n² (по числу елементів матриці С). Розглянувши запропонований підхід, можна відзначити, що досягнутий рівень паралелізму є в деякій мірі надлишковим. При проведенні практичних розрахунків кількість сформованих підзадач, як правило, буде перевищувати число наявних обчислювальних елементів (процесорів та/або ядер) і, тим самим, неминучим є етап укрупнення базових завдань. В цьому плані може виявитися корисним агрегація обчислень вже на кроці виділення базових підзадач. Можливе рішення може полягати в об'єднанні в рамках однієї підзадачі всіх обчислень, пов'язаних не з одним, а з декількома елементами результуючої матриці С. Для подальшого розгляду в рамках даного розділу визначимо базову задачу як процедуру обчислення всіх елементів одного з рядків матриці С. Такий підхід призводить до зниження загальної кількості підзадач до величини n. Для виконання всіх необхідних обчислень базовій підзадачі повинні бути доступні один з рядків матриці A і всі стовпці матриці B. Просте рішення цієї проблеми – дублювання матриці B у всіх підзадачах. Слід зазначити, що такий підхід не призводить до реального дублювання даних, оскільки розроблюваний алгоритм орієнтований на застосування для обчислювальних систем із загальною пам'яттю, до якої є доступ з усіх використовуваних обчислювальних елементів. 3.2. Виділення інформаційних залежностей Для обчислення одного рядка матриці необхідно, щоб у кожній подзадаче містилася рядок матриці А і був забезпечений доступ до всіх стовпців матриці B. Спосіб організації паралельних обчислень представлено на рис. 5.7. Рисунок 5.7. Організація обчислень під час виконання паралельного алгоритму множення матриць, заснованого на поділі матриць за рядками 3.3. Масштабування і розподіл підзадач Виділені базові підзадачі характеризуються однаковою обчислювальною трудомісткістю і рівним обсягом переданих даних. У разі, коли розмір n матриць виявляється більше, ніж число p обчислювальних елементів (процесорів та/або ядер), базові підзадачі можна укрупнити, об'єднавши в рамках однієї підзадачі кілька сусідніх рядків матриці. В цьому випадку вихідна матриця A і матриця-результат С розбиваються на ряд горизонтальних смуг. Розмір смуг при цьому слід вибрати рівним k=n/p (в припущенні, що n кратно p), що дозволить як і раніше забезпечити рівномірність розподілу обчислювального навантаження по обчислювальних елементах. 3.4. Аналіз ефективності Даний паралельний алгоритм володіє хорошою «локальністю обчислень». Це означає, що дані, які обробляє один з потоків паралельної програми, не змінюються іншим потоком. Немає взаємодії між потоками, немає необхідності в синхронізації. Значить, для того, щоб визначити час виконання паралельного алгоритму, необхідно знати, скільки обчислювальних операцій виконує кожен потік паралельної програми (обчислення виконуються потоками паралельно) і скільки даних необхідно прочитати з оперативної пам'яті в кеш процесора (доступ до пам'яті здійснюється строго послідовно). Для обчислення одного елемента результуючої матриці необхідно виконати скалярне множення рядка матриці А на стовпець матриці В. Виконання скалярного множення включає (2n–1) обчислювальних операцій. Кожен потік обчислює елементи горизонтальної смуги результуючої матриці, число елементів у смузі становить n²/p. Таким чином, час, який витрачається на обчислення, може бути визначено по формулі: (5) Для обчислення одного елемента результуючої матриці необхідно прочитати в кеш n+8n+8 елементів даних. Кожен потік обчислює n/p елементів матриці С, однак для визначення повного обсягу переписуваних в кеш даних слід враховувати, що читання даних з оперативної пам'яті може виконуватися тільки послідовно. Як результат, скорочення обсягу переписуваних в кеш даних досягається тільки для матриці B (прочитаний одноразово в кеш стовпець матриці B може використовуватися всіма потоками без повторного читання з пам'яті). Читання рядків матриці A і елементів матриці C в граничному випадку має бути виконано повністю і послідовно. У результаті час роботи з оперативною пам'яттю при виконанні описаного паралельного алгоритму множення матриць може бути визначений у відповідності з наступним співвідношенням: (6) де, як і раніше, β є пропускна здатність каналу доступу до оперативної пам'яті, а α – латентність оперативної пам'яті. Отже, час виконання паралельного алгоритму становить: (7) Як і раніше, слід врахувати, що частина необхідних даних може бути переміщена в кеш завчасно за допомогою тих або інших механізмів передбачення. Крім того, звернення до даних не обов'язково призводить до кеш-промаху і, відповідно, до читання даних з оперативної пам'яті (необхідні дані можуть перебувати і в кеш пам'яті) Дані фактори можна, як і в попередніх випадках, врахувати за допомогою введення в модель показника частоти кеш промахів: (8) 4. Вихідна проблема – стохастичне вирівнювання Розглянемо алгоритм стохастичного вирівнювання (або розподілу помилки), який використовується у багатьох графічних програмах і програмах обробки зображень. Спочатку метод стохастичного вирівнювання був запропонований Флойдом і Стинбергом як спосіб відтворення цифрових зображень на пристроях, які мають обмежений діапазон кольорів. Надрукувати 8-розрядне монохромне зображення на чорно-білому принтері непросто. Принтер, будучи пристроєм, що має всього два рівня кольору, не може сам надрукувати 8-разрядне зображення. Він повинен імітувати відтінки сірого за допомогою якоїсь апроксимації. Приклад зображення до і після процесу стохастичного вирівнювання показаний на рис. 5.8. Початкове зображення, що складається з 8-разрядних сірих пікселів, показано зліва, а результат після обробки за алгоритмом стохастичного вирівнювання – праворуч. Отримане зображення складається з пікселів тільки двох кольорів: чорного і білого. Рисунок 5.8. Приклад зображення до і після процесу стохастичного вирівнювання Базовий різновид алгоритму стохастичного вирівнювання виконується як простий трьох етапний процес. 1. Визначається вихідне значення по вхідному значенню поточного пікселя. На цьому кроці часто використовується квантування або у разі двійкових даних – межі. Для 8-розрядного сірого зображення, яке відтворюється на 1-розрядному вихідному пристрої, всі вхідні значення з діапазону [0,127] повинні відображатися як 0, а всі вхідні значення з діапазону [128,255] — 1. 2. Після того як вихідне значення визначено, код обчислює помилку між тим, що повинно бути зображено на вихідному пристрої, і тим, що фактично відтворюється. В якості прикладу припустимо, що поточне вхідне значення пікселя дорівнює 168. Оскільки воно більше граничного значення (128), то ми отримуємо вихідне значення 1. Це значення записується у вихідний масив. Для обчислення помилки програма повинна спочатку нормалізувати вихідне значення, щоб воно було в тому ж діапазоні, що і вхідне. Тобто в цілях обчислення помилки відтворення вихідний піксел повинен мати нормалізоване значення 0 (якщо вихідний піксель має значення 0) або 255 (якщо вихідний піксель має значення 1). У даному випадку помилка відтворення є різницею між значенням, яке потрібно було вивести (168), і вихідним значенням (255), що становить -87. 3. Нарешті, значення помилки розподіляється з ваговими коефіцієнтами по сусіднім пікселям, як показано на мал. 5.9. Рисунок 5.9. Розподіл помилки по сусіднім пікселям У даному прикладі для розподілу помилки на сусідні пікселі використовуються вагові коефіцієнти Флойда-Стинберга. Обчислюється 7/16 від помилки і додається до пікселя праворуч від поточного (оброблюваного). 5/16 помилки додається до пікселя в наступному ряду, прямо під поточним. Інші помилки поширюються аналогічно. Хоча годяться і інші вагові схеми, всі алгоритми стохастичного вирівнювання слідують цьому загальному методу. Цей трьохетапний процес застосовується до всіх пікселів зображення. 4.1. Аналіз алгоритму стохастичного вирівнювання На перший погляд можна подумати, що алгоритм стохастичного вирівнювання є за своєю суттю послідовним процесом. Традиційний підхід полягає в поширенні помилок у міру обчислення на сусідні пікселі. В результаті для обчислення значення наступного пікселя необхідно знати значення попереднього. Така залежність означає, що код може обробляти в даний момент часу тільки один піксель. Однак нескладно підійти до вирішення цієї проблеми так, щоб воно найбільше підходило для багатопоточної обробки. 4.2. Паралельне стохастичне вирівнювання Для перетворення звичайного алгоритму стохастичного вирівнювання до виду, який більше підходить для паралельного рішення, розглянемо різні форми декомпозиції, описані раніше в цій главі. Яка з них підійде до даного випадку? В якості підказки погляньте на рис. 5.10, який ілюструє поширення помилок з дещо іншої точки зору. В даному випадку ми розглядаємо поширення помилки з точки зору приймаючого пікселя. Рисунок 5.10. Обчислення помилки в алгоритмі стохастичного вирівнювання з точки зору приймаючого пікселя З урахуванням того, що піксель не може бути оброблений раніше своїх попередників в алгоритмі, проблема зводиться до того, що у нас є виробник, або в даному випадку кілька виробників, які виробляють дані (значення помилок), які споживач (поточний піксель) використовує для обчислення наступного пікселя. Інформаційний потік помилок, спрямований на поточний піксель, є критичним. Тому проблему, як здається, можна розбити шляхом декомпозиції за інформаційними потоками. Тепер, коли ми визначили підхід, наступним кроком є визначення найкращого еталона, який може бути застосований для вирішення даної конкретної проблеми. Кожен незалежний програмний потік повинен обробляти рівний об'єм роботи (балансування навантаження). Як слід розподілити роботу? Можна (на основі описаного в попередньому розділі алгоритму) виділити один програмний потік для обробки парних пікселів в даному ряді, а інший – для обробки непарних пікселів того ж ряду. Однак такий підхід неефективний – кожен потік буде блокуватися в очікуванні завершення іншого, в результаті загальна продуктивність може бути нижче, ніж у випадку послідовного вирішення. Для ефективного розподілу роботи між програмними потоками нам потрібен спосіб зменшення (а в ідеалі – усунення) залежності між пікселями. Для того, щоб можна було обробити піксель, він повинен мати три значення помилок (ці значення позначені на рисунку як еА, еВ та еС) з попереднього ряду і одне значення з сусіднього зліва пікселя в поточному рядку. Таким чином, поточний піксель можна обробити після обробки цих пікселів. Такий порядок диктує реалізацію, при якій кожен потік обробляє окремий ряд даних. Після того як закінчиться обробка перших декількох пікселів ряду, може почати свою роботу програмний потік, який відповідає за обробку наступного ряду. Ця послідовність наведена на рис. 5.11. Рисунок 5.11. Паралельне стохастичне вирівнювання шляхом багатопотокової обробки декількох рядків Зверніть увагу, що на початку кожного ряду відбувається невелика затримка внаслідок того, що до обробки поточного ряду необхідно підрахувати дані щодо помилок попереднього ряду. Такі типи затримок у реалізаціях виробник-споживач практично неминучі, однак їх вплив можна мінімізувати. Для цього необхідно домогтися гарного розподілу навантаження, щоб кожен програмний потік виконувався як можна більш ефективно. У цьому випадку затримка складе два пікселя перед тим, як можна буде починати виконання наступного потоку. На сторінці розміром 8,5 х 11 дюймів при 1200 точках на дюйм в одному ряду виходить 10 200 пікселів. Затримка в два пікселя в даному випадку несуттєва. 4.3 Інші альтернативи У попередньому прикладі був запропоновано метод стохастичного вирівнювання, коли кожен програмний потік обробляв окремий ряд даних. Однак можна було б розглянути варіант декомпозиції цієї роботи на ще більш дрібні складові. При розподілі завдань між потоками інстинктивно підшукуються незалежні задачі. Найпростіший спосіб добитися паралельності – обробляти окремо кожну сторінку. Взагалі кажучи, кожна сторінка є незалежним набором даних, тобто не має залежностей від інших сторінок. Чому ж було запропоноване рішення на основі обробки рядів замість того, щоб обробляти окремі сторінки? Цьому є три основні причини: • Зображення може займати кілька сторінок. Обробка по сторінкам накладає обмеження в одне зображення на сторінку, що може не підходити для цього додатка. • Збільшена витрата пам'яті. Сторінка розміром 8,5 х 11 дюймів при 1200 точках на дюйм займає 131 Мбайт оперативної пам'яті. Доведеться зберігати проміжні результати, а це буде менш ефективно в сенсі використання пам'яті. • Зазвичай додаток друкує не більше однієї сторінки. Розподіл завдань па рівні сторінок не дало б приросту продуктивності в порівнянні з послідовним кодом. Можливий комбінований підхід, коли сторінки розбиваються на області і кожна область обробляється окремим програмним потоком, як показано на рис. 5.12. Зверніть увагу, що потоки повинні обробляти кожен свою сторінку. Це збільшує стартову затримку перед початком виконання потоків. На рис. 5.12, потік 2 перед тим, як почати обробляти дані, має стартову затримку в 1/2 сторінки, в той час як стартова затримка для потоку 3 становить вже 2/3 сторінки. Незважаючи на деякі поліпшення, комбінований підхід має ті ж (описані раніше) обмеження, що і підхід з розбиттям по сторінкам. Для того щоб обійти ці обмеження, слід реалізувати стохастичне вирівнювання на основі рядків. Рисунок 5.12. Паралельне стохастичне вирівнювання для випадку декількох сторінок і декількох програмних потоків Лекція 4 OpenMP План лекції: 1. OpenMP і інші технології паралельного програмування 2. Потоки в OpenMP 3. Модель даних 4. Управління потоками 5. Ефективність використання OpenMP 1. OpenMP і інші технології паралельного програмування 1.1. OpenMP – загальні відомості OpenMP (Open Multi-Processing) – це набір директив компілятора, бібліотечних процедур і змінних оточення, які призначені для програмування багатопотокових додатків на багатопроцесорних системах з спільною пам'яттю (SMP-системах). Перший стандарт OpenMP був розроблений в 1997 році як API, орієнтований на написання багатопоточних додатків, що легко переносяться. Спочатку він був заснований на мові Fortran, але пізніше включив в себе і мови Сі і Сі ++. Інтерфейс OpenMP став однією з найбільш популярних технологій паралельного програмування. OpenMP успішно використовується як при програмуванні суперкомп'ютерних систем з великою кількістю процесорів, так і в настільних системах корисувачей або, наприклад, в Xbox 360. Розробку специфікації OpenMP ведуть кілька великих виробників обчислювальної техніки і програмного забезпечення, чия робота регулюється некомерційною організацією "OpenMP Architecture Review Board" (ARB). У OpenMP використовується модель паралельного виконання "розгалуження-злиття". Програма OpenMP починається як єдиний потік виконання, званий початковим потоком. Коли потік зустрічає паралельну конструкцію, він створює нову групу потоків, що складається з себе і деякого числа додаткових потоків, і стає головним у новій групі. Всі члени нової групи (включаючи головний) виконують код всередині паралельної конструкції. В кінці паралельної конструкції є неявний бар'єр. Після паралельної конструкції, виконання призначеного для користувача коду продовжує тільки головний потік. В паралельний регіон можуть бути вкладені інші паралельні регіони, в яких кожен потік початкового регіону стає основним для своєї групи потоків. Вкладені регіони можуть в свою чергу включати регіони більш глибокого рівня вкладеності. Число потоків в групі, що виконуються паралельно, можна контролювати декількома способами. Один з них – використання змінної оточення OMP_NUM_THREADS. Інший спосіб – виклик процедури omp_set_num_threads (). Ще один спосіб – використання виразу num_threads в поєднанні з директивою parallel. 1.2. OpenMP і інші технології паралельного програмування На даний момент вважається, що найбільш гнучким, переносним і загальноприйнятим інтерфейсом паралельного програмування є MPI (інтерфейс передачі повідомлень). Однак модель передачі повідомлень: • недостатньо ефективна на SMP-системах; • відносно складна в освоєнні, так як вимагає мислення в "необчислювальних" термінах. POSIX-інтерфейс для організації ниток (Pthreads) підтримується широко (практично на всіх UNIX-системах), проте з багатьох причин не підходить для практичного паралельного програмування: • немає підтримки Fortran; • занадто низький рівень програмування; • немає підтримки паралелізму за даними; • механізм ниток спочатку розроблявся не для цілей організації обчислювального паралелізму. OpenMP можна розглядати як високорівневу надбудову над Pthreads (або аналогічними бібліотеками ниток). Перерахуємо переваги, які OpenMP дає розробнику. За рахунок ідеї "інкрементального розпаралелювання" OpenMP ідеально підходить для розробників, що бажають швидко распараллелить свої обчислювальні програми з великими паралельними циклами. Розробник не створює нову паралельну програму, а просто послідовно додає в текст послідовної програми OpenMP-директиви. При цьому OpenMP – досить гнучкий механізм, що надає розробнику великі можливості контролю над поведінкою паралельного додатка. Передбачається, що OpenMP-програма на однопроцессорной платформі може бути використана в якості послідовної програми, тобто немає необхідності підтримувати послідовну і паралельну версії. Директиви OpenMP просто ігноруються послідовним компілятором, а для виклику процедур OpenMP можуть бути підставлені заглушки (stubs), текст яких наведено в специфікаціях. Однією з переваг OpenMP його розробники вважають підтримку так званих "orphan" (відірваних) директив, тобто директиви синхронізації і розподілу роботи можуть не входити безпосередньо в лексичний контекст паралельної області. |