Програмування паралельних процесів

Размещено на http://www.allbest.ru/

Програмування паралельних процесів

1. Розробка алгоритмів паралельних обчислень

алгоритм паралельний обчислення

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

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

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

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

Загальну схему розробки паралельних алгоритмів представлено на рис. 8.1.

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

Рис. 1. Загальна схема розробки паралельних алгоритмів

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

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

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

2. Моделювання паралельних програм

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



Рис. 2. Модель паралельної програми у вигляді графа "процеси - канали"

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

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

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

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

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

Етапи розробки паралельних алгоритмів

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

Розділення обчислень на незалежні частини

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

Рис. 3. Розділення даних матриці: а) стрічкова схема, б) блочна схема

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

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

Для іншої частини задач обчислення можуть полягати в виконанні різних операцій над одним і тим же набором даних - в цьому випадку кажуть про наявність функціонального паралелізму (як приклад, можна навести задачі обробки послідовності запитів до інформаційних баз даних, обчислення з одночасним застосуванням різних алгоритмів розрахунку та ін.). Часто функціональна декомпозиція використовується для організації конвеєрної обробки даних (наприклад, для виконання певних перетворень даних обчислення можна звести до функціональної послідовності введення, обробки і збереження даних). Важливим при виділенні під задач є вибір потрібного рівня декомпозиції обчислень. Формування максимально можливої кількості під задач забезпечує використання гранично досяжного рівня паралелізму розв'язуваної задачі, проте ускладнює аналіз паралельних обчислень. Застосування в разі декомпозиції обчислень тільки достатньо "крупних" під задач приводить до ясної схеми паралельних обчислень, проте може ускладнити ефективне використання достатньо великої кількості процесорів. Можливе розумне поєднання цих двох підходів може полягати в застосуванні як конструктивних елементів декомпозиції тільки тих під задач, для яких методи паралельних обчислень відомі. Так при аналізі задачі матричного множення як під задачі можна використовувати методи скалярного добутку векторів чи алгоритм матрично-векторного множення. Подібний проміжний спосіб декомпозиції обчислень дає змогу забезпечити простоту представлення обчислювальних схем та ефективність паралельних розрахунків. Під задачі, що вибираються за умови такого підходу, далі іменуватимуться базовими, вони можуть бути елементарними (неподільними), якщо не припускають подальшого розділення, чи складовими - в іншому випадку.

Виділення інформаційних залежностей

За наявності обчислювальної схеми розв'язку задачі після виділення базових під задач визначення інформаційних залежностей між ними не викликає ускладнень. Етапи виділення під задач та інформаційних залежностей достатньо складно піддаються розділенню. Виділення під задач повинно відбуватися з врахуванням необхідних інформаційних зв'язків, після аналізу об'єму і частоти необхідних інформаційних об'ємів між під задачами може знадобитися повторення етапу розділення обчислень. В разі проведення аналізу інформаційних залежностей між під задачами слід розрізняти (переважні форми інформаційної взаємодії підкреслені):

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

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

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

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

Для оцінки правильності етапу виведення інформаційних залежностей можна скористатися таким контрольним списком питань:

- чи відповідає обчислювальна складність під задач інтенсивності їх інформаційних взаємодій?

- чи є однаковою інтенсивність інформаційних взаємодій для різних під задач?

- чи є схема інформаційної взаємодії локальною?

- чи не перешкоджає виявлена інформаційна залежність паралельному розв'язку під задач?

Масштабування набору під-задач

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

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

Список контрольних питань для оцінки правильності етапу масштабування такий:

- чи не погіршиться локальність обчислень після масштабування наявного набору під задач?

- чи мають під задачі після масштабування однакову обчислювальну та комунікаційну складність?

- чи відповідає кількість задач чисельності наявних процесорів?

- чи залежать параметричні правила масштабування від кількості процесорів?

Розподіл під-задач між процесорами

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

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

Для прикладу коротко охарактеризуємо спосіб динамічного управління розподілом обчислюваного навантаження, який називається схемою "менеджер-виконавець" (the manager-worker scheme), При використанні цього підходу припускається, що під задачі можуть виникати і завершуватися в ході обчислень, при цьому інформаційні взаємодії між під задачами або повністю відсутні, або мінімальні. У відповідності з цією схемою для управління розподілом навантаження в системі виділяється окремий процесор-менеджер, якому доступна інформація про всі наявні під задачі. інші процесори системи є виконавцями, які для отримання обчислювального навантаження звертаються до процесора-менеджера. Породжувані в ході обчислень нові під задачі передаються назад процесору-менеджеру і можуть бути отримані для розв'язку за умови наступних звертань процесорів-виконавців. Завершення обчислень відбувається в момент, коли процесори-виконавці завершили рішення всіх переданих їм під задач, а процесор-менеджер не має яких-небудь обчислювальних навантажень для виконання. Доцільними є наступні питання для перевірки етапу розподілу під задач:

- чи не призводить розподіл декількох задач на один процесор до зростання додаткових обчислювальних витрат?

- чи існує необхідність динамічного балансування обчислень?

- чи не є процесор-менеджер "вузьким" місцем при використанні схеми "менеджер-виконавець"?

Паралельне рішення гравітаційної задачі N тіл

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

,	(2.2.31)

де - тривалість пере обчислення параметрів однієї пари тіл.

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

Розділення обчислень на незалежні частини

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

Виділення інформаційних залежностей

Виконання обчислень, пов'язаних з кожною під задачею, стає можливим тільки у випадку, коли в під задачах є дані (положення та швидкості пересувань) про всі тіла фізичної системи. Як результат, перед початком кожної ітерації моделювання кожна під задача повинна отримати всю необхідну інформацію від всіх інших під задач системи. Така процедура передачі даних називається операцією збирання даних. В розглядуваному алгоритмі ця операція повинна бути виконана для кожної під задачі - такий варіант передачі даних називається операцією узагальненого збору даних. Визначення вимог до необхідних результатів інформаційного обміну не приводить до однозначного встановлення потрібного інформаційного обміну між під задачами - досягнення потрібних результатів може бути забезпечено за допомогою різних алгоритмів виконання операції узагальненого збору даних Найпростіший спосіб виконання необхідного інформаційного обміну полягає в реалізації послідовності кроків, на кожному з яких всі наявні під задачі розбиваються попарно і обмін даними здійснюється між під задачами утворених пар. За належної організації попарного розділення під задач (N-1) - кратне повторення описаних дій приведе до повної реалізації потрібної операції збору даних.

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

Масштабування і розподіл під-задач по процесорам

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

Аналіз ефективності паралельних обчислень

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

,	(8.1)

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

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

.	(8.2)

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

3. Аналіз масштабованості паралельних обчислень

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

Оцінимо накладні витрати (total overhead), які мають місце при виконанні паралельного алгоритму

.	(8.3)

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

.	(8.4)

Застосовуючи отримані співвідношення, ефективність використання процесорів можна виразити як

.	(8.5)

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

Нехай є бажаний рівень ефективності виконуваних обчислень. З виразу для ефективності можна отримати

або , .	(8.6)

Породжувану останнім співвідношенням залежність між складністю розв'язуваної задачі та чисельністю процесорів називають функцією ізлефективності (isoefficiency function).

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

.	(8.7)

і вираз для функції ізоефективності набуде вигляду

.	(8.8)

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

4. Оцінка комунікаційної трудомісткості паралельних алгоритмів

Алгоритми маршрутизації

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

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

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

До числа найпоширеніших оптимальних алгоритмів відноситься клас методів по координатної маршрутизації (dimension-ordered routing), в яких пошук шляхів передачі даних здійснюється по черзі для кожної розмірності топології мережі комунікації. Так для двомірної решітки такий підхід приводить до маршрутизації, коли передача даних спочатку виконується по одному напрямку (наприклад, по горизонталі до досягнення вертикалі, на якій розташований процесор призначення), а далі дані передаються впродовж другого напрямку (ця схема відома під назвою алгоритму ХУ - маршрутизації). Для гіперкуба по координатна схема маршрутизації може полягати, наприклад, в циклічній передачі даних процесору, який визначається першою відмінною бітовою позицією в номерах процесорів - того, на якому повідомлення розташовується в даний момент часу, та того, на який воно повинно бути передане.

Методи передачі даних

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

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

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

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

До числа найпоширеніших методів передачі даних відносяться два основних способи комунікації. Перший з них орієнтований на передачу повідомлень (метод передачі повідомлень, чи МПС) як неподільних (атомарних) блоків інформації (store and-forward routing або SFR). При такому підході процесор, який містить повідомлення для передачі, готує весь об'єм даних для передачі, визначає процесор, якому слід направити дані, і запускає операцію пересилки даних. Процесор, якому направлено повідомлення, в першу чергу здійснює прийом повністю всіх даних і тільки потім приступає до пересилки прийнятого повідомлення далі за маршрутом. Тривалість пересилання даних для методу передачі повідомлення розміром байтів за маршрутом довжиною визначається виразом

.	(8.9)

За умови достатньо довгих повідомлень тривалістю передачі службових даних можна знехтувати і вираз для тривалості передачі даних можна записати в простішому вигляді:

.	(8.10)

Другий спосіб комунікації базується на представленні повідомлень, що пересилаються, у вигляді блоків інформації меншого розміру - пакетів, в результаті чого передача даних може бути зведена до передачі пакетів (метод передачі пакетів або МПП). ЗА умови такого методу комунікації (cut-through routing або CTR) процесор, що приймає, може здійснювати пересилку даних за подальшим маршрутом безпосередньо відразу після прийому чергового пакету, не очікуючи завершення прийому даних всього повідомлення. Тривалість пересилання даних при використанні методу передачі пакетів визначається виразом:

.	(8.11)

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

Аналіз трудомісткості основних операцій передачі даних

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

Передача даних між двома процесорами мережі

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

Таблиця 8.1 Тривалість передачі даних між двома процесорами

Топологія	Передача повідомлень	Передача пакетів
Кільце
Решітка-тор
Гіперкуб

Передача даних від одного процесора всім іншим процесорам мережі. Операція передачі даних (одного і того ж сполучення) від одного процесора всім іншим процесорам мережі (one-to-all broadcast або single-node broadcast) є однією з найчастіше виконуваних комунікаційних дій. Двоїста до неї операція - прийом на одному процесорі повідомлень від всіх інших процесорів мережі (single-node accumulation). Подібні операції використовуються, зокрема, при реалізації матрично-векторного множення, розв'язку систем лінійних рівнянь методом Гауса, розв'язку задачі пошуку найкоротших шляхів та ін.

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

Передача повідомлень

Для кільцевої технології процесор - джерело розсилання може ініціювати передачу даних відразу двом своїм сусідам, які, в свою чергу, прийнявши повідомлення, організують пересилання далі по кільцю. Трудомісткість виконання операції розсилання в цьому випадку визначатиметься співвідношенням:

.	(8.12)

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

.	(8.13)

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

.	(8.14)

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

Передача пакетів

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

	(8.15)

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

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

.	(8.16)

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

Передача даних від всіх процесорів всім процесорам мережі

Операція передачі даних від всіх процесорів всім процесорам мережі (all-to-all broadcast або multinode broadcast) є природним узагальненням одиночної операції розсилки, двоїста до неї операція - прийом повідомлень на кожному процесорі від всіх процесорів мережі (multinode accumulation). Подібні операції широко використовуються, наприклад, при реалізації матричних обчислень.

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

Передача повідомлень

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

.	(8.17)

Для топології типу решітка-тор множинне розсилання повідомлень може бути виконана з використанням алгоритму, отриманого узагальненням способу передачі даних для кільцевої структури мережі. Схема узагальнення полягає в наступному. На першому етапі організується передача повідомлень роздільно по всім процесорам мережі, які розташовані на одних і тих же горизонталях решітки (в результаті на кожному процесорі однієї і тієї ж горизонталі формуються укрупнені повідомлення з розміром , які об'єднують всі повідомлення горизонталі). Тривалість виконання етапу:

.	(8.18)

На другому етапі розсилання даних виконується по процесорам мережі, які утворюють вертикалі решітки. Тривалість цього етапу:

.	(8.19)

Загальна тривалість операції розсилання визначається співвідношенням:

	(8.20)

Для гіперкуба алгоритм множинного розсилання повідомлень можна отримати узагальненням раніше описаного способу передачі даних для топології типу решітки на розмірність гіперкуба N. В результаті такого узагальнення схема комунікації полягає в наступному. На кожному етапі , виконання алгоритму функціонують всі процесори мережі, які обмінюються своїми даними із своїми сусідами i - ої розмірності і формують об'єднані повідомлення. Тривалість операції розсилання може бути отримана з використанням виразу:

.	(8.21)

Передача пакетів

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

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

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

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

.	(8.22)

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

	(8.23)

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

Узагальнена передача даних від одного процесора всім іншим процесорам мережі

Загальний випадок передачі даних від одного процесора всім іншим процесорам мережі полягає в тому, що всі повідомлення, що розсилаються, різні (one-to-all personalized communication чи single-node scatter) . Двоїста операція передачі даних для даного типу взаємодії процесорів - узагальнений прийом повідомлень (single-node gather) на одному процесорі від всіх інших процесорів мережі (відмінність цієї операції від раніше розглянутої процедури збірки даних на одному процесорі полягає в тому, що узагальнена операція збірки не передбачає якоїсь взаємодії повідомлень (наприклад, редукції) в процесі передачі даних). Трудомісткість операції узагальненого розсилання порівнювана із складністю виконання процедури множинної передачі даних. Процесор - ініціатор розсилання посилає кожному процесору мережі повідомлення з розміром , і, тим самим, нижня оцінка тривалості виконання операції характеризується величиною .

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

	(8.24)

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

Узагальнена передача даних від всіх процесорів всім процесорам мережі

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

Передача повідомлень

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

.	(8.25)

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

.	(8.26)

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

	(8.27)

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

Передача пакетів

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

.	(8.28)

Циклічний зсув

Окремий випадок узагальненого множинного розсилання є процедурою перестановки (permutation), який представляє собою операцію перерозподілу інформації між процесорами мережі, в якій кожний процесор передає повідомлення визначеному певним способом іншому процесору мережі. Конкретний варіант перестановки - циклічний q - зсув (circular q - shift), коли кожний процесор , передає дані процесору з номером . Подібна операція зсуву використовується, наприклад, при організації матричних обчислень.

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

Передача повідомлень

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

.	(8.29)

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