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

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

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

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

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

tпд = (tн + mtk)[p/2]

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

tпд = 2(tн + mtk)|${\displaystyle {\sqrt {p}}}$/2|

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

tпд = (tн + mtk)log2p

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

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

tпд = ${\displaystyle \sum _{i\mathop {=} 1}^{log_{2}p}}$(tн + mtk + tcp/2i) = (tн + mtk)log2p + tc(p – 1)

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

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

tпд = (tн + mtk)log2p + 2tc(${\displaystyle {\sqrt {p}}}$ – 1)

(2.2.8)

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

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

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

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

tпд = (tн + mtk)(p – 1)

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

tпд = (tн + mtk)(${\displaystyle {\sqrt {p}}}$ – 1)

(2.2.10)

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

tпд = (tн + m${\displaystyle {\sqrt {p}}}$tk)(${\displaystyle {\sqrt {p}}}$ – 1)

(2.2.11)

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

tпд = 2tн(${\displaystyle {\sqrt {p}}}$ – 1) + mtk(p – 1)

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

tпд = ${\displaystyle \sum _{i\mathop {=} 1}^{log_{2}p}}$(tн + 2i–1mtk) = tнlog2p + mtk(p – 1)

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

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

tпд=(tн+tk)+log2p

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

Sk=${\displaystyle \sum _{i\mathop {=} 1}^{k}}$xi, 1≤k≤p

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

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

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

tпд = tylog2p + mtk(p – 1)

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

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

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

tпд = (tн + 1/2mptk)(p – 1)

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

 tпд = 2(tн + mptk)(${\displaystyle {\sqrt {p}}}$ – 1)

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

tпд = (tн + 1/2mptk)log2p

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

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

tпд = (tн + mtk)(p – 1) + 1/2tcplog2p

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

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

Загальна схема алгоритму циклічного зсуву для топології решітка-тор полягає в наступному. Нехай процесори пронумеровані за стрічками решітки від 0 до p-1. На першому етапі організується циклічний зсув з кроком q mod ${\displaystyle {\sqrt {p}}}$ по кожній стрічці зокрема (якщо при реалізації такого зсуву повідомлення передаються через праві границі стрічок, то після виконання кожної такої передачі необхідно здійснити компенсаційний зсув вверх на 1 для процесорів першого стовпця решітки). На другому етапі реалізується циклічний зсув вверх з кроком [q/ ${\displaystyle {\sqrt {p}}}$] для кожного стовпця решітки. Загальна тривалість всіх операцій розсилань визначається співвідношенням:

tпд = (tн + mtk)(2[${\displaystyle {\sqrt {p}}}$/2] + 1)

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

Уявимо величину зсуву  q у вигляді двоїстого коду. Кількість ненульових позицій коду визначає кількість етапів в схемі реалізації операції циклічного зсуву. На кожному етапі виконується операція зсуву з величиною кроку, яка задається найстаршою ненульовою позицією значення q (наприклад, за умови вихідної величини зсуву q=5=101₂ на першому етапі виконується зсув з кроком 4, на другому етапі крок зсуву дорівнює 1). Виконання кожного етапу (окрім зсуву з кроком 1) полягає в передачі даних по шляху, який включає дві лінії зв’язку. Як результат, верхня оцінка для тривалості виконання операції циклічного зсуву визначається співвідношенням

tпд = (tн + mtk)(2log2p – 1)

Використання пересилання пакетів може підвищити ефективність виконання операції циклічного зсуву для топології гіперкуб. Реалізація всіх необхідних комунікаційних дій в цьому випадку може бути забезпечена шляхом відправки кожним процесором всіх даних, що пересилаються,безпосередньо процесорам призначення. Застосування методу по координатної маршрутизації дасть змогу уникнути колізій при використанні ліній передачі даних (в кожний момент часу для кожного каналу буде існувати не більше одного готового для відправки повідомлення) Довжина найбільшого шляху за умови такого розсилання даних визначається як log₂p-y(q), де y(q) - найбільше ціле значення j таке, що 2^j - дільник величини зсуву q. Тоді тривалість операції циклічного зсуву можна охарактеризувати з використанням виразу

tпд = tн + mtk + tc + (log2p – y(q))

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