REFERATUA.ORG.UA — База українських рефератів



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

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

Малюнок 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 процесорів:

s(i)= тоді s-1(i)=

Якщо номер процеса i представити у двійковому коді idid-1...i2i1, то функцію суміші можна подати в наступному вигляді:

s(idid-1...i2i1)=id-1id-2...i1id і s-1(idid-1...i2i1)=i1id...i3i2.

Визначивши функцію суміші, запишемо правило за яким з'єднуються процеси в сумішно-обмінній моделі. В ній кожен процес Pi має три сусіди: Pj, де j відрізняється від i останнім бітом у двійковому розкладі, P s(i) та P s-1(i).

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

Малюнок 7а. Логічна схема сумішного з'єднання.

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

Малюнок 7б. Модель комп'ютера сумішно-обмінного з'єднання розміру 8.

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

Малюнок 8. Модель комп'ютера сумішно-зсувного з'єднання розміру 8

Схема з'єднання метеликом [5] (butterfly network). Малюнок 9а. Метелик з N входами подається графом з Топології мереж.Граф як основа побудови  комп’ютерної мережі рівнів, кожен з яких містить N вершин. j-та вершина на i-ому рівні позначається j1j2...jlogN,i, де j1j2...jlogN - бінарне подання числа j і вона з'єднується з вершинами j1j2...jlogN,i+1 та j1j2...jiТопології мереж.Граф як основа побудови  комп’ютерної мережіji+2...jlogN,i+1 на рівні i+1. На нульовому рівні розташовані вхідні вершини, на рівні logN — вершини виходу. Шлях, який проходять дані з будь-якого входу на будь-який вихід визначається однозначно за номером виходу і його довжина дорівнює Топології мереж.Граф як основа побудови  комп’ютерної мережі. З будь-якої вершини виходять дві дуги: нагору(0) та вниз(1). Наприклад, якщо виходом буде вершина 101, то з якого б входу ми не пішли, підемо вниз, вгору, вниз і обов'язково потрапимо у вихід 101. На малюнку 9б зображена схема метелика з випадковим з'єднанням вершин першого рівня. Його зв'язки повністю співпадають зі зв'язками стандартного метелика окрім першого рівня. З кожної вершини першого рівня виходить дві дуги в будь-які вершини другого рівня, одна з останніх повинна знаходитися в верхній половині, друга - в нижній.

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

Малюнок 9а. Схема з'єднання Малюнок 9б. Метелик з випадковим

метеликом для 32 процесів. з'єднанням першого рівня.

Схема метелика належить до великого класа розчеплених багатостанових мереж (splitter multistage interconnection networks). Перемикачі на кожному рівні розчепленої мережі можна розбити на блоки. Всі перемикачі рівня 0 належать одному блоку. На рівні 1 існує два блоки - один складається з верхніх N/2 прцесів, другий - з нижніх N/2 процесів. Взагалі, на рівні Топології мереж.Граф як основа побудови  комп’ютерної мережі кількість блоків дорівнює 2i, розмір кожного з яких дорівнює N/2i. Кожний блок Топології мереж.Граф як основа побудови  комп’ютерної мережі на рівні i з'єднується з двома блоками на рівні i+1 - Bhigh та Blow, відповідно верхній та нижній блоки. Розгалуження блоку на два і називається розчепленням. Розчеплена мережа має складність d, якщо будь-яка вершина, яка не є вхідною, має 2d вхідних ребер, а з будь-якої вершини, яка не є виходом, виходить d верхніх та d нижніх ребер. Схеми метелика,які наведено на малюнках 9а та 9б, є розчепленими мережами складності 1. В розчеплених мережах існує лише один шлях між вхідною та вихідною вершиною.

Мережа вулиць Манхетена [31] (Manhattan Street Network) (Малюнок 10) є двовимірна прямокутна мережа безпосереднього з'єднання, яка складається з N=m*n процесів, кожен з яких має ідентифікаційний номер (a,b), де 0ЈaЈm-1, 0ЈbЈn-1. Вершина (a,b) сполучається зв'язками з вершинами (x,b) та (a,y) наступним чином: (x,b) = {(a+/-1) mod m, b}, +/- коли b парне/непарне та (a,y)={a, (b+/-1) mod n}, +/- коли a парне/непарне. Напрямок з'єднань цієї мережі співпадає з напрямком руху по вулицям Манхетена. Діаметр мережі дорівнює N1/2+1, середня довжина шляхів між двома вершинами — (N3/2/2+N-4)/(N-1) [31].

HR4-мережа [34], або торовидна мережа, виглядає як і мережа вулиць Манхетена за


 
Загрузка...