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

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

Міністерство освіти і науки України

Черкаський державний технологічний університет

Кафедра спеціалізованих комп'ютерних систем

Курсова робота

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

Виконав:

студент 3 курсу

групи СКСС-1477

Кононенко Є.Д.

Перевірив:

Корпань Я.В.

Черкаси 2015 р.

Зміст

Вступ

1. Характеристики топології мережі передачі даних

2. Загальна характеристика механізмів передачі даних

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

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

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

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

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

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

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

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

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

4. Методи логічного представлення топології комунікаційного середовища

4.1 Подання кільцевої топології у вигляді гіперкуба

4.2 Відображення топології решітки на гіперкуб

5. Оцінка трудомісткості операцій передачі даних для кластерних систем

Висновок

Література

Вступ

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

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

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



1. Характеристики топології мережі передачі даних

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

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

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

· Ширина бінарного поділу - показник, що визначається як мінімальна кількість дуг, які треба видалити для розділення мережі передачі даних на дві незв'язні області однакового розміру;

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

Для порівняння в табл1 наводяться значення перерахованих показників для різних топологій мережі передачі даних.

Таблиця 1. Характеристики топологій мережі передачі даних (p - кількість процесорів)

Топологія	Діаметр	Ширина бісекції	Зв'язність	Вартість
Повний граф	1	p2 / 4	p - 1	p (p - 1) / 2
Зірка	2	1	1	p - 1
Повне двійкове дерево	2 log ((p + 1) / 2)	1	1	p - 1
Лінійка	p - 1	1	1	p - 1
Кільце	[p / 2]	2	2	p
Решітка (N = 2)	2( - 1)		2	2 (p - )
Решітка-тор (N = 2)	2[ / 2]	2	4	2p
Гіперкуб	log p	p / 2	log p	(p log p) / 2



2. Загальна характеристика механізмів передачі даних

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

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

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

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

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

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



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

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

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

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

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

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

tпд = tн + (mtк + tс)l.



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

tпд = tн + mtк + tсl

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



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

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

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

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

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



Таблиця 2. Час передачі даних між двома процесорами

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

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

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

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

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



= ().

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

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

tпд = (tн + mtк) log p.

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

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

.

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

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

.

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



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

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

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

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

.

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

.

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

.

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

.

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

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

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

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

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

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



.

Іншим типовим прикладом використовуваності операції множинної розсилки є задача знаходження приватних сум послідовності значень Si (у зарубіжній літературі ця задача відома під назвою prefix sum problem)

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

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

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

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

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

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

.

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

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

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

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

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

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

.

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

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

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

.



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

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

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

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

топологія мережа алгоритм маршрутизація

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

Рис. 1. Схема відображення гіперкуба на кільце (в колах наведено номери процесорів гіперкуба)

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



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

log p - г(q),

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

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

.



4. Методи логічного представлення топології комунікаційного середовища

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

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

· ущільнення дуг (congestion), яке виражається як максимальна кількість дуг логічної топології, що відображаються в одну лінію передачі фізичної топології;

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

· збільшення вершин (expansion), що обчислюється як відношення кількості вершин у фізичній і логічній топологіях.

4.1 Подання кільцевої топології у вигляді гіперкуба

Встановлення відповідності між кільцевою топологією і гіперкубом може бути виконано за допомогою двійкового рефлексивного коду Грея G (i, N) (binary reflected Gray code), що визначається відповідно до виразів:



G(0, 1) = 0, G(1, 1) = 1

де i задає номер значення в коді Грея, а N є довжина цього коду.

Для ілюстрації підходу в таб.3 показується відображення кільцевої топології на гіперкуб для мережі з p=8 процесорів.

Таблиця. 3. Відображення кільцевої топології на гіперкуб за допомогою коду Грея

Код Грея для N= 1	Код Грея для N= 2	Код Грея для N= 3	Номера процессоров
			гіперкуб	кільце
0	0 0	0 0 0	0	0
1	0 1	0 0 1	1	1
	1 1	0 1 1	3	2
	1 0	0 1 0	2	3
		1 1 0	6	4
		1 1 1	7	5
		1 0 1	5	6
		1 0 0	4	7

Важливою властивістю коду Грея є той факт, що сусідні значення G(i, N) і G(i+1, N) мають тільки одну відмінну бітову позицію. Як результат, сусідні вершини в кільцевій топології відображаються на сусідні процесори в гіперкубі.

4.2 Відображення топології решітки на гіперкуб

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



N = r + s

можна прийняти правило, що елементу решітки з координатами (i, j), відповідатиме процесор гіперкуба з номером: G(i, r) || G(j, s), де операція || означає конкатенацію кодів Грея.



5. Оцінка трудомісткості операцій передачі даних для кластерних систем

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

Інше часто вживане рішення при створенні кластерів полягає у використанні методу передачі пакетів (реалізованого, як правило, на основі протоколу TCP / IP) в якості основного способу виконання комунікаційних операцій.

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

,

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

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

де є кількість пакетів, на яке розбивається передане повідомлення, величина визначає максимальний розмір пакету, який може бути доставлений в мережі (за замовчуванням для операційної системи MS Windows в мережі Fast Ethernet = 1500 байт ), а є обсяг службових даних в кожному пакеті що пересилається (для протоколу TCP / IP, ОС Windows 2000 та мережі Fast Ethernet = 78 байт). В наведених співвідношеннях константа характеризує апаратну складову латентності і залежить від параметрів використовуваного мережевого устаткування, значення задає час підготовки одного байта даних для передачі по мережі.

Як результат, величина латентності

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



Крім латентності, у запропонованих виразах для оцінки трудомісткості комунікаційної операції уточнено і правило обчислення часу передачі даних

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

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

,

де R є пропускною здатністю мережі передачі даних.



Висновок

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

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

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



Література

1. http://www.software.unn.ac.ru/ccam/files/HTML_Version/part3.html

2. http://www.intuit.ru/studies/courses/1156/190/lecture/4946?page=6

3. Гергель В.П., Стронгин Р.Г "Основы параллельных вычислений для многопроцессорных вычислительных систем", Н. Новгород: Изд-во ННГУ, 2001

4. Таненбаум Э, "Архитектура компьютера", СПб.: Питер, 2002

5. http://www.hpcc.unn.ru/mskurs/RUS/PPT/ppr03

6. http://www.intuit.ru/studies/courses/1156/190/literature#literature.3

Размещено на Allbest.ru