Топології мереж.Граф як основа побудови комп’ютерної мережі

Малюнок 1. Малюнок 2

Схема повного з'єднання. Схема з'єднання в коло

для 6 процесорів. для 6 процесорів.

Схема з'єднання в коло. Малюнок 2. Ця архітектура більш реалістична і будується просто. Кількість дроту дорівнює кількості процесорів. Діаметр дорівнює P/2, середня відстань між процесорами дорівнює приблизно P/4. Передача інформації відбувається по колу за чи проти ходу годинникової стрілки при спільній роботі всіх P процесорів. Для обміну даними між будь-якими двома процесами необхідно зробити не більш ніж P-1 такт.Двовимірна архітектура мережевого з'єднання [20]. Малюнок 3. Діаметр цієї схеми з'єднання дорівнює 2 * (P1/2 - 1) - відстань між протилежними кутовими процесорами мережі. Передача інформації між двома процесами відбувається за O(P1/2) тактів - передача по рядкам та стовпчикам. Більш загальною моделлю є d-вимірна архітектура, діаметр якої дорівнює d*(P1/d-1), передача даних відбувається за O(d*P1/d) тактів. Ця модель широко використовується для розв'язку дифференційних рівнянь (звичайних чи в часткових похідних) та рівнянь математичної фізики.

Малюнок 3. Двовимірна архітектура Малюнок 4. Зірка з 9 процесів.

мережевого з'єднання для 16 процесорів.

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

Малюнок 5. Бінарне дерево розміру 15.

Бінарне дерево. Малюнок 5. Деревоподібна архітектура має найменший діаметр серед всіх існуючих, який дорівнює для бінарного дерева 2lg((P+1)/2) - відстань між двома листами, шлях між якими проходить через корінь. Для k-арних дерев діаметр зменшується зі збільшенням k. Недоліком деревоподібних мереж є те, що обмін даними між процесами відбувається за лінійний час, а процес-корінь є вузьким горлом при передачі інформації.

Багатопроцесорний комп'ютер з паралельною обробкою інформації називається деревовидною машиною (tree machine) [33], якщо його процесори сполучені зв'язками так, що утворюється топологія повного бінарного дерева. Такий комп'ютер має 2d-1 процесорних елементів для деякого d, які розбиті на d рівнів, пронумерованих від 1 до d. Кожний процесор на рівні j, 1ЈjЈd, зв'язаний з єдиним процесором на рівні j-1 (батьком), та з двома процесорами на рівні j+1 (синами). Зв'язки між процесами розташовані таким чином, що безпосередньо обмінюватися інформацією можуть лише батько з сином. Єдиний процесор на першому рівні називається коренем в топології дерева, а процесори на рівні d — листами. Корінь не має батька, а листи не мають синів. На малюнку 15 зображена топологія деревовидної машини з d=4 рівнями, яка містить 24-1 = 15 процесорних елементів.

Схема з'єднання в куб. Малюнок 6. Якщо d - вимірність гіперкуба, то він містить P=2d процесів. Передача даних відбувається за тактів. Кожен процесор сполучається з d сусідами. Діаметр кубічної мережі дорівнює точно logdP. Кожен процесор можна ідентифікувати d-вимірним вектором бітів. Тоді відстань між процесами можна визначити, коректуючи біти їх номерів. Щоб дістатися до протилежних процесорів треба скоректувати бітів - з 00...0 до 11...1.

Малюнок 6. Схема з'єднання в куб розміру 8.

Схема сумішно-обмінного з'єднання (shuffle - exchange). Малюнки 7а.7б. Ця архітектура мережі є однією з найкращих для паралельної обробки інформації: її діаметр приблизно дорівнює 2*lgP, кількість тактів для обміну між двома процесами - 4*lgP-3. Використовується вона в телефонних комунікаціях. Ця схема вирішує проблеми великого діаметра моделі та повільного часу обміну між двома процесами. Кожен процес з'єднується з іншими за правилом, яке визначає функція суміші для P=2*id процесорів: