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

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

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

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

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

До числа найпоширеніших методів передачі даних відносяться два основних способи комунікації. Перший із них орієнтований на передачу повідомлень (метод передачі повідомлень, чи МПС) як неподільних (атомарних) блоків інформації ( або SFR). При такому підході процесор, який містить повідомлення для передачі, готує весь об’єм даних для передачі, визначає процесор, якому слід направити дані, і запускає операцію пересилки даних. Процесор, якому направлено повідомлення, в першу чергу здійснює прийом повністю всіх даних і тільки потім приступає до пересилки прийнятого повідомлення далі за маршрутом. Тривалість пересилання даних tпд для методу передачі повідомлення розміром m байтів за маршрутом довжиною l визначається виразом: tпд = tп + (mtk + tc)l За умови достатньо довгих повідомлень тривалістю передачі службових даних можна знехтувати і вираз для тривалості передачі даних можна записати в простішому вигляді: tпд = tн + mtkl Другий спосіб комунікації базується на представленні повідомлень, що пересилаються, у вигляді блоків інформації меншого розміру — пакетів, в результаті чого передача даних може бути зведена до передачі пакетів (метод передачі пакетів або МПП). ЗА умови такого методу комунікації ( або CTR) процесор, що приймає, може здійснювати пересилку даних за подальшим маршрутом безпосередньо відразу після прийому чергового пакету, не очікуючи завершення прийому даних всього повідомлення. Тривалість пересилання даних при використанні методу передачі пакетів визначається виразом: tпд = tу + mtk + tcl Порівнюючи отримані вирази отримані вирази, можна помітити, що в більшості випадків метод передачі пакетів приводить до більш швидкого пересилання даних; крім того, даний підхід знижує потребу в пам’яті для зберігання даних, що пересилаються, при організації прийому-передачі повідомлень, а для передачі пакетів можуть використовуватися одночасно різні комунікаційні канали. З іншого боку, реалізація пакетного методу потребує розробки більш складного апаратного та програмного забезпечення мережі, може збільшити накладні витрати (тривалість підготовки та тривалість передачі службових даних). Крім того, при передачі пакетів можливе виникнення конфліктних ситуацій (дедлоків). Аналіз трудомісткості основних операцій передачі даних При всьому розмаїтті виконуваних операцій передачі даних при паралельних способах розв’язку складних науково-технічних задач, певні процедури взаємодії процесів мережі можна віднести до числа основних комунікаційних дій, або найбільш широко розповсюджених на практиці паралельних обчислень, або тих, до яких можна багато інших процесів прийому-передачі повідомлень. Важливо відмітити, що в рамках подібного базового набору для більшості операцій комунікації існують процедури, обернені за дією вихідним операціям. Як результат, аналіз комунікаційних процедур доцільно виконувати попарно, оскільки в багатьох випадках алгоритми виконання прямої та зворотної операцій можуть бути отримані наслідки не з однакових посилань. Передача даних між двома процесорами мережі Складність цієї комунікаційної операції може бути наслідком підстановки довжини максимального шляху (діаметра мережі) в вирази для тривалості передачі даних при різних методах комунікації. +Тривалість передачі даних між двома процесорами Топологія Передача повідомленьПередача пакетівКільцеtн + mtk[p/2]tн + mtk + tc[p/2]Решітка-торtн + 2mtk[p/2]tн + mtk + 2tc[p/2]Гіперкубtн + 2mtklog2ptн + mtk + tclog2p

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

Найпростіший спосіб реалізації операції розсилання полягає в її виконанні як послідовності попарних взаємодій процесорів мережі. Проте за такого підходу більша частина пересилань є надлишковою і можливе застосування більш ефективних алгоритмів комунікації. Передача повідомлень Для кільцевої технології процесор — джерело розсилання може ініціювати передачу даних відразу двом своїм сусідам, які, у свою чергу, прийнявши повідомлення, організують пересилання далі по кільцю. Трудомісткість виконання операції розсилання в цьому випадку визначатиметься співвідношенням: tпд = (tн + mtk)[p/2]

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

Для гіперкубу розсилка може бути виконана в ході N-етапної процедури передачі даних. На першому етапі процесор-джерело повідомлення передає дані одному з своїх сусідів (наприклад, по першій розмірності) — у результаті після першого етапу є два процесори, які мають копію даних, що пересилаються (цей результат можна інтерпретувати також як розбиття вихідного гіперкуба на два таких однакових за розміром гіперкуби з розмірністю N – 1, що кожний із них має копію вихідного повідомлення). На другому етапі два процесори, задіяні на першому етапі, пересилають повідомлення своїм сусідам по другій розмірності тощо в результаті такого розсилання тривалість операції оцінюється з використанням виразу: tпд = (tн + mtk)log2p Порівнюючи отримані вирази для тривалості виконання операції розсилання, можна відмітити, що найкращі показники мають технології типу гіперкуб; більше того, можна показати, що такий результат є найкращим для вибраного способу комунікації з використанням повідомлень. Передача пакетів Для топології типу кільце алгоритм розсилання можна отримати шляхом логічного зображення кільцевої структури мережі у вигляді гіперкубу. В результаті на етапі розсилання процесор — джерело повідомлення передає дані процесору, який знаходиться на відстані p/2 від вихідного процесора. Далі, на другому етапі обидва процесори, які вже мають дані, що розсилаються, після першого етапу, передають повідомлення процесорам, які знаходяться на відстані p/4, і т. д. Трудомісткість виконання операції розсилання за такого методу передачі даних визначається співвідношенням:

tпд = (tн + mtk + tcp/2i) = (tн + mtk)log2p + tc(p – 1)

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

Для топології типу решітка-тор алгоритм розсилання можна отримати із способу передачі даних, застосованого для кільцевої структури мережі, у відповідності з тим же способом, що і у випадку використання методу передачі повідомлень. Отриманий в результаті такого узагальнення алгоритм розсилання характеризується таким співвідношенням для оцінки тривалості виконання: tпд = (tн + mtk)log2p + 2tc( – 1) (2.2.8)

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

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

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

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

На другому етапі розсилання даних виконується по процесорам мережі, які утворюють вертикалі решітки. Тривалість цього етапу: tпд = (tн + mtk)( – 1) (2.2.11)

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

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