Сітки з комутаторами

Сітки з комутаторами - це динамічні структури зв'язку.

Рис. 2.2. Шинний розподілювач

Кожний ПЕ має n-1 пункт комутації, бо діагональні пункти не потребують контакту. Загалом ця сітка має n*(n-1) пунктів комутації і дає можливість встановити будь-яку кліькість з'єднань між всіма ПЕ. Тобто без всяких колізій може відбуватись повністю паралельний обмін даними. Суттєвим недоліком цього комутатора є витрати на його побудову, становлять n*(n-1) пунктів з'єднань для n ПЕ. Практично така кількість пунктів може бути реалізована лише для невеликої кількості процесорів. Вже для 100 ПЕ потрібно 9900 перемикань.

Дельта - сітки

Щоб зменшити витрати порядку n², що виникли під час побудови розподілювачів перехресних шин, були розроблені дельта-сітки. В найпростішому випадку (рис.2.3)

Рис.2.3. Дельта-мережі комутації

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

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

Рис.2.4. Перемикач дельта-мережі

З таких простих базових елементів можна будувати більш об'смні сітки. На рис.2.5 наведено триступеневу дельта-сітку, яка •з'єднує 8 входів з 8 виходами. Кожний елемент сітки відподає базисному елементу, що показаний на рис.2.3.

Рис. 2.5. Дельта-сітка розміром 8х8

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

2.3 Структури, що забезпечують зв’язок типу "пункт-пункт"

Розглянемо статичні структури зв’язку "пункт-пункт". При цьому застосовують ся такі параметри:

n – кількість ПЕ в мережі;

V- кількість ліній зв’язку у кожного ПЕ;

А – макс. відстань між двома ПЕ.

Кільце

Кільцева структура (рис. 2.6) має тільки 2 лінії зв’язку на кожний ПЕ (позитивна риса) і потребує в найгіршому випадку n/2 кроки для обміну даними між двома ПЕ, що розміщуються в кільці на найб. відстані один від одного (негативна риса).

Рис. 2.6. Кільце

Повний граф

Протилежністю кільця є повний граф (рис.2.7).Йогооптимальна коннективність забезпечується n-1 лінією зв'язку на кожний ПЕ.

Рис. 2.7. Повний граф

Решітки і тори

Дуже часто застосовуються решітчасті структури зв'язку і їхні замкнуті варіанти - тори. На рис.2.8 показано чотиризв'язкові структури.

Квадратна решітка Квадратний тор

(4 лінії зв'язку в ПЕ) (4 лінії зв'язку в ПЕ)

Рис. 2.8. Квадратні решітки та тори

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

Гіперкуб

Гіперкуб нульової вимірності - це єдиний елемент (рис.2.9, ліворуч). Гіперкуб вимірності і+1 виникає з двох гіперкубів вимірності і, в яких елементи, що взаємодіють, з'єднані між собою. Наприклад, на рис.2.9 показано, що з двох квадратів (гіперкубів вимірності 2) можна побудувати куб (гіперкуб вимірності 3), з'єднавши кожний елемент "переднього" з кожним елементом "заднього" квадрата.

Рис.2.9. Гіперкуб з розмірностями від нуля до чотирьох

Кожний ПЕ потребує log₂n з'єднаннь з сусіднім ПЕ. Кількість зв'язків тут на відміну від попередніх решітчастих структур не є постійною. До того ж максимальна відстань між ПЕ змінюється на таку саму логарифмічну величину. Тому гіперкуб є універсальною мережею зв'язку з невеликою логарифмічною відстанню і не дуже великою логарифмічною кількістю ліній зв'язку у кожногоПЕ.

Отже, порівняння мереж можливо тільки на основі параметрів V (кількість ліній зв'язків кожного ПЕ) і А (максимальна відстань між двома ПЕ). Це порівняння або аналіз того, які переваги має певна мережа, може дати корисні результати тільки з урахуванням особливостей вирішуваної паралельної задачі.

Залежно від умов застосування одна структура зв'язку може бути ефективнішою за іншу структуру. Якщо алгоритм розв’язування задач потребує певної мережі, то як правило, фізична реалізація якраз цієї, можливо "гіршої" за параметрами V і А мережі, дасть кращі результати, ніж пристосування для цієї задачі іншої мережі, що має "хороші" параметри.

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

Поиск по сайту: