ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 24.12.2021
Просмотров: 6757
Скачиваний: 22
449
чення. Надлишкова мережа не тільки більш пристосована до дефектів компонентів, але також забезпечує зміну напрямів пересилання повідомлень, і таким чином полегшує вирішення питань блокування в мережі.
12.9.3. Статичні топології комунікаційних мереж: багатопроцесорних систем
Статичні (фіксовані) комунікаційні мережі мають однонаправлені та двонаправлені фіксовані канали зв'язку між процесорами. Може бути виділено два види статичних мереж. Це мережі з повним з'єднанням (CCN - completely connected networks) та мережі з обмеженим з'єднанням (LCN - limited connection networks).
У мережі з повним з'єднанням (повнозв'язних мережах) кожен вузол з'єднаний зі всіма іншими вузлами у мережі. Мережа з повним з'єднанням гарантує швидку доставку повідомлення від будь-якого початкового вузла до будь-якого вузла призначення, оскільки йому доведеться перетнути лише один канал зв'язку. Так як кожен вузол з'єднаний з кожним іншим вузлом в мережі, організація обміну повідомленнями між вузлами стає простим завданням. Мережі з повним з'єднанням є, проте, дорогими, оскільки вимагають великої кількості каналів зв'язку для їх побудови. Ця незручність стає очевидною при великих кількостях вузлів N. Слід зазначити, що число каналів зв'язку в мережі з повним з'єднанням рівне N(N-l)/2, тобто асимптотична складність цієї мережі, виражена кількістю каналів зв'язку, є 0(N2). Часова затримка мережі з повним з'єднанням, виражена кількістю пересічених зв'язків, є постійною і рівною 1. Мережа з повним з'єднанням, приведена в якості прикладу на рис. 12.25, MaeN = 6 вузлів. Як результат, для їх з'єднання потрібно 15 каналів зв'язку.
Мережі з обмеженим з'єднанням не забезпечують безпосереднього зв'язку кожного вузла з кожним іншим вузлом мережі. Натомість, комунікації між деякими вузлами мають бути здійснені через інші вузли мережі. Довжина шляху між вузлами, виміряна кількістю каналів зв'язку, які доведеться перетнути, є довшою, порівняно з випадком мереж з повним з'єднанням. Крім того, при застосуванні мереж з обмеженим з'єднанням виникає ще дві інших проблеми. Це потреба пошуку ефективної топології комунікаційної мережі і потреба в механізмі маршрутизації повідомлень по мережі, поки вони не досягають своїх місць призначення.
Нижче ці дві проблеми обговорюється детальніше.
450
З розвитком архітектури комп'ютерів створено цілий ряд топологій комунікаційних мереж з обмеженим з'єднанням. Ці топології включають:
-
одновимірні (лінійні) топології;
-
двовимірні топології (кільце, зірка, дерево, решітка);
-
тривимірні топології (повнозв'язна топологія, кубічна топологія, гіперкубічні топології).
Прості приклади цих топологій комунікаційних мереж показані на рис. 12.26.
У лінійній топології вузли комунікаційної мережі утворюють одновимірний масив (рис. 12.26 а), в якому кожен вузол з'єднаний з своїми двома безпосередніми сусідніми вузлами. Два вузли в кінцях масиву з'єднані з своїм єдиним безпосереднім сусідом. Якщо вузлу і потрібно зв'язатися з вузлом), де j>i, то повідомленню від вузла і доводиться перетнути вузли і+1, і+2, ...,j-i. Так само, коли вузлу і потрібно зв'язатися з вузлом], де i>j, то повідомлення від вузла і має перетнути вузли і-1, і-2,..., i-j. У найгіршому випадку, коли вузлу 1 доводиться відправити повідомлення вузлу N, повідомленню доведеться перетнути в сумі N-1 вузлів, щоб досягти свого місця призначення. Тому, хоча лінійні масиви є простими і мають прості механізми маршрутизації, вони є повільними. Це особливо відчувається, коли число вузлів N велике. Мережна асимптотична складність лінійного масиву є O(N) і його часова асимптотична складність є O(N).
Якщо обидва вузли в кінцях лінійної мережі з'єднати, отримається мережа з структурою кільця (рис. 12.26 Ь). Вона може бути однонаправленою та двонаправленою, залежно від кількості каналів зв'язку та напрямку передачі в них даних. Прикладом систем, в яких використано топологію кільця, є мережа Token Ring та система SCI.
Решітчаста (сотова) топологія комунікаційної мережі (рис. 12.26 с) в загальному є n-вимірною матрицею, яка має К0хК1х...хКn-1 , вузлів, де п - число вимірів мережі, і Кі є основа виміру і. Існує велика кількість сотових мереж, які відрізняються з'єднаннями вузлів. Наприклад, на рис. 12.26 d показана сотово-кільцева мережа, в якій крайні вузли замкнуті в кільце. Рис. 12.27 показує приклад сотової мережі розміром 3x3x2. Вузол, позиція якого є (і, j, k), з'єднаний із своїми сусідами з позицією і+1, j+1, i k+1. Потрібно від-
451
значити, що для сотової мережі
з N вузлами найдовша відстань між двома
довільними вузлами пропорційна N1/2,
тобто її часова асимптотична
складність є 0(N1/2).
Багатопроцесорні
комп'ютерні системи з сотовою топологією
комунікаційної мережі є ефективними
для виконання наукових обчислень. Іншою
перевагою сотових мереж є те, що вони
масштабуються. Велика матриця може бути
отримана з малої без зміни порядку
вузла (кількості входів). Тому багато
комп'ютерних систем з розподіленою
пам'яттю базуються на таких мережах,
наприклад система МРР фірми Goodyear
Aerospace,
система Paragon
фірми Intel,
система J-Machine
Масачусетського технологічного
інституту.
Зіркоподібна топологія (рис. 12.26e) передбачає об'єднання багатьох вузлів через один центральний вузол і характеризується простотою організації керування.
В деревовидній мережі, в якій двійкове дерево, показане на рис. 12.26 f, є частковим випадком, якщо вузлу на рівні і (коренева вершина знаходиться на рівні 0) потрібно зв'язатися з вузлом на рівні], де i>j і вузол призначення належить піддереву того ж кореня, то йому доведеться направити повідомлення вгору через прохідні вузли рівнів і-1, і-2,..., j+1, поки воно не досягне вузла призначення. Якщо вузлу на рівні і потрібно зв'язатися з іншим вузлом на тому ж рівні і (або з вузлом на рівні j Ф і, де вузол призначення належить піддереву іншого кореня), йому доведеться направити повідомлення вгору дерева, поки повідомлення не досягає вершини на рівні 0. Після цього повідомлення доведеться направити вниз від вершини, поки воно не досягне місця призначення. Слід зазначити, що кількість вузлів в мережі двійкового дерева, що має k рівнів, рівна N(k) = 2k - 1.
Максимальна глибина мережі двійкового дерева рівна log2N, де N - число вузлів в мережі. Тому, апаратна асимптотична складність цієї мережі є 0(2k) і її часова асимптотична складність є 0(log2N).
Досить популярними є кубічні (рис. 12.26 g) та гіперкубічні топології, які дозволяють зменшити часову складність статичних топологій мереж.
Гіперкубічні мережі мають структуру n-мірного куба, n-мірний куб (гіперкуб порядку п) визначають як неорієнтований граф, що має 2n мічених вершин від 0 до 2n-1, в якому є дуга між заданою парою вершин лише в тому випадку, якщо двійкове представлення їх адрес відрізняється лише одним бітом. Як приклад, на рис. 12.28 показаний 4-мірний куб.
452
У багатопроцесорній системі, базованій на гіперкубічній мережі, процесори розміщуються у вершинах графа. Дуги графа представляють канали зв'язку між процесорами. Як видно з рисунку, кожен процесор в 4-мірному кубі з'єднаний з чотирма іншими процесорами. У n-мірному кубі кожний процесор має канали зв'язку з п іншими процесорами. Оскільки в гіперкубі є дуга між заданою парою вузлів лише якщо двійкове представлення їх адрес відрізняється одним бітом, ця властивість забезпечує простий механізм маршрутизації повідомлень. Маршрут повідомлення, що відправляється з вузла і та призначене для вузла j, може бути знайдений шляхом виконання над двійковим представленням адрес і тa j операції виключного АБО (XOR). Якщо результат виконання операції XOR приводить до 1 в заданій бітовій позиції, то повідомлення має бути посланим по каналу зв'язку, який охоплює відповідний вимір. Наприклад, якщо повідомлення послане від початкового (S) вузла 0101 до вузла призначення (D) 1011, то результатом операції XOR буде 1110. Це означатиме, що повідомлення буде послано лише уздовж вимірів 2, 3, і 4 (рахуючи справа наліво) для того, щоб прибути до місця призначення. Порядок, в якому повідомлення перетинає три виміри, не має важливого значення. Як тільки повідомлення перетинає три виміри в будь-якому порядку, воно досягне місця призначення. Три можливих непересічних маршрути, які може пройти повідомлення у наведеному прикладі, показані виділеними лініями на рис. 12.28. Непересічні маршрути не мають будь-яких спільних каналів зв'язку.
У n-мірному кубі кожен вузол має порядок п. Порядок вузла визначений як число каналів зв'язку, що входять в вузол. Верхня межа кількості непересічних каналів в п-мірному кубі рівна п. Гіперкуб представляється як логарифмічна архітектура. Це тому, що максимальне число каналів зв'язку, які повідомленню доведеться перетнути, щоб досягти місця призначення, в n-мірному кубі, що містить N=2n вузлів, рівне log2N.
Одна з бажаних особливостей гіперкубічних мереж - рекурсивна природа їх побудови. n-мірний куб може бути побудований на основі двох підкубів, кожен з яких має порядок n-1, шляхом з'єднання вузлів подібних адрес в обох підкубах. Так 4-мірний куб, показаний на рис. 12.28, побудований на основі двох підкубів, порядок кожного з яких рівний трьом. Потрібно відзначити, що побудова 4-мірного куба на основі двох 3-мірних кубів вимагає збільшення порядку кожного вузла.
Система iPSC фірми Intel є прикладом базованої на гіперкубічній комунікаційній мережі комерційної багатопроцесорної комп'ютерної системи.
453
12.9.4. Шинні динамічні комунікаційні мережі багатопроцесорних систем
В табл. 12.1 наведено характеристики деяких комерційних одношинних багатопроцесорних комп'ютерних систем.
Як ми вже вказували, динамічні комунікаційні мережі багатопроцесорних систем можуть бути одно- та багатошинними. На рис. 12.29 наведено приклад використання однотипної комунікаційної мережі, яка є найпростішим варіантом з можливих з'єднань. В загальному вигляді така система включає N процесорів Р, кожен з яких має свою локальну пам'ять, які з'єднані спільною шиною. Всі процесори через шину взаємодіють з спільною пам'яттю. Типовий розмір таких систем - від одного до 50 процесорів. Він визначається потрібною пропускною здатністю шини, яка приходиться на один процесор. Тому описана архітектура, при простоті розширення, обмежена пропускною здатністю шини, по якій одночасно може проводити обмін інформацією лише один процесор. Складність цієї мережі може бути оцінена наступним чином: апаратна асимптотична складність, виражена кількістю магістралей, є 0(1), часова асимптотична складність, яка вимірюється кількістю затримок, є O(N), де N - кількість процесорів.
Використання багатьох шин для з'єднання процесорів та блоків пам'яті є природнім розширенням одношинних систем. В цьому випадку можливі кілька варіантів схем з'єднань. Серед них можна відзначити наступні:
-
багатошинна комунікаційна мережа з повним з'єднанням блоків пам'яті (multiple bus with full bus-memory connection),
-
багатошинна комунікаційна мережа з одним з'єднанням блоків пам'яті (multiple bus with single bus memory connection),
-
багатошинна комунікаційна мережа з частковим з'єднанням блоків пам'яті (multiple bus with partial bus-memory connection),
• багатошинна комунікаційна
мережа з базованим на класах з'єднанням
блоків
пам'яті (multiple
bus with
class-based
memory
connection).