Файл: Мельник А. Архітектура комп\'ютера.doc

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 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),

  • багатошинна комунікаційна мережа з частковим з'єднанням блоків пам'яті (multi­ple bus with partial bus-memory connection),

багатошинна комунікаційна мережа з базованим на класах з'єднанням блоків
пам'яті (
multiple bus with class-based memory connection).