Загальні теоретичні відомості. Найбільш важливим аспектом паралельних ОС з локальною пам’яттю є те, як взаємодіють між собою окремі процесори
Найбільш важливим аспектом паралельних ОС з локальною пам’яттю є те, як взаємодіють між собою окремі процесори. Конфігурація системи міжпроцесорного зв’язку істотно впливає на порядок підключення ліній зв’язку, що з’єднують окремі процесори. Організація внутрішніх комунікацій ОС називається топологією. Залежно від того, чи залишається конфігурація взаємозв’язків незмінною (доки виконується відповідне завдання), розрізняють ОС зі статичною та динамічною топологіями. В статичних ОС структура взаємозв’язків фіксована. В ОС із динамічною топологією в процесі обчислень конфігурація взаємозв’язків за допомогою програмних засобів може бути оперативно змінена. До статичних топологій відносять такі, де між двома вузлами можливий лише один чи декілька фіксованих шляхів, тобто немає комутуючих пристроїв. З можливих критеріїв класифікації статичних ОС обирають їх розмірність. З цих позицій розрізняють: · одновимірні топології (лінійний масив); · двовимірні топології (кільце, зірка, дерево, решітка); · багатовимірні топології (повнозв’язана топологія); · гіперкубічну топологію. У простій лінійній топології вузли системи
Рис. 8.1. Лінійна топологія ОС У лінійній топології час передавання повідомлення залежить від відстані між вузлами, а відмова одного з них може призвести до неможливості передавання повідомлення. З цього приводу в лінійних ОС використовують відмовостійкі вузли, які при відмові ізолюють себе від мережі, дозволяючи повідомленню обминути несправний вузол.
Рис. 8.2. Кільцева топологія ОС Стандартна кільцева топологія (рис. 8.2) являє собою лінійний ланцюг, кінці якого з’єднані між собою. Недолік: додавання чи вилучення вузла потребує демонтажу мережі. Зіркоподібна організація вузлів (рис. 8.3) рідко використовується для об’єднання процесорів багатопроцесорної ОС, але добре працює, коли потік інформації йде від декількох вторинних вузлів, з’єднаних з одним первинним вузлом, наприклад при підключенні терміналів. Загальна пропускна здатність мережі звичайно обмежується швидкодією концентратора. Основна перевага зіркоподібної схеми у тому, що конструктивне виконання вузлів на кінцях cbcntvb може бути дуже простим.
Рис. 8.3. Зіркоподібна топологія ОС У деревоподібній топології (рис. 8.4) система будується за схемою двійкового дерева, де кожний вузол більш високого рівня зв’язаний з двома вузлами наступного за порядком більш низького рівня. Вузол, що знаходиться на більш високому рівні, називають батьківським, а два підключених до нього нижчерозташованих вузла – дочірніми. В свою чергу, кожний дочірній вузол виступає як батьківський для двох вузлів наступного більш низького рівня. Кожний вузол зв’язаний лише з двома дочірніми та одним батьківським.
Рис. 8.4. Деревоподібна топологія ОС При великих об’ємах передачі даних між несуміжними вузлами деревоподібна топологія виявляється недостатньо ефективною, оскільки повідомлення повинні проходити через один чи декілька проміжних процесорів. На більш високих рівнях системи ймовірність затору через недостатньо високу пропускну здатність ліній зв’язку вище. ОС з решітчастою топологією (рис. 8.5) орієнтовані на задачі, пов’язані з обробкою масивів. Їх конфігурація визначається видом та розмірністю масиву.
Рис. 8.5. Решітчаста топологія ОС У системах, де кожний процесор з’єднаний з декількома сусідніми процесорами, можна досягти компромісу між складністю системи міжпроцесорного зв’язку, її пропускною здатністю й затримкою обмінів даними. В одновимірних решітках процесорів, що часто називають лінійним масивом, кожний процесор, крім крайніх, з’єднаний з двома сусідніми. При цьому дані, що пересилаються із процесора-джерела в процесор-приймач, послідовно проходять транзитні процесори, розташовані між джерелом і приймачем. У двовимірній решітці кожний процесор з’єднаний з північним, південним, східним і західним сусідами. Решітки процесорів характеризуються регулярністю, локальністю і простотою маршрутизації міжпроцесорних зв’язків. У тривимірному масиві кожний із процесорів з’єднаний із шістьома сусідами. Перевагою такої системи є мінімальна кількість ліній зв’язку (з кожного процесору виходить не більше двох ліній зв’язку). У повністюзв’язаній системі кожний процесор має пряме з’єднання з будь-яким іншим процесором. При об’єднанні паралельних процесорів дуже популярна топологія гіперкуба. Лінія, що з’єднує два вузла (рис. 8.6, а), визначає одновимірний гіперкуб. Квадрат, що утворений чотирма вузлами (рис. 8.6, б) – двовимірний гіперкуб, а куб з 8 вузлів (рис. 8.6, в) – тривимірний гіперкуб та т.ін. Обмін повідомленнями в гіперкубі базується на двійковому поданні номерів вузлів. Нумерація вузлів робиться так, що для будь-якої пари суміжних вузлів двійкове подання номерів цих вузлів відрізняється лише в одній позиції. Вузли 0010 та 0110 – сусіди, а вузли 0110 та 0101 такими не є.
Рис. 8.6. Гіперкубова топологія ОС Така архітектура дає малу кількість зв’язків між процесорами. В ОС з такою архітектурою обчислювальний процес будується таким чином: кожний процесор у вузлі має власну пам’ять та відповідно володіє потужним обчислювальним ресурсом. Якщо обчислювальної потужності не вистачає, то до вирішення залучають процесори з сусідніх вузлів чи всього кубу. Якщо і цього недостатньо, то залучають процесори, які розташовані у вузлах зовнішнього гіперкубу відносно до даного. Недоліки окремих типів систем мінімізуються при їх комбінуванні (гібридні системи міжпроцесорного зв’язку). Наприклад, конфігурацію піраміди одержують додаванням зв’язків між процесорами, що належать одному ярусу дерева, відповідно до конфігурації двовимірних решіток. Таким чином, у піраміді об’єднані переваги дерева й решітки. Структури ОС із кластерами також відносять до гібридних систем зв’язку. У межах кластера процесори з’єднані відповідно до однієї з конфігурацій зв’язків, наприклад, загальною шиною, а кілька кластерів об’єднані у ОС за допомогою іншої конфігурації зв’язків, наприклад, у вигляді решітки або гіперкуба. У динамічній топології ОС з’єднання вузлів забезпечується електронними ключами, варіюючи установки яких можна змінювати топологію системи. У вузлах динамічних ОС розташовуються комутуючі елементи, а пристрої, що обмінюються повідомленнями (термінали), підключаються до входів та виходів цієї мережі. Як термінали можуть виступати процесори чи процесори та модулі пам’яті. Для таких ОС частіше всього використовується одно- або багатокаскадна комутація на основі матричних комутаторів. ОС з шинною архітектурою – найбільш простий та дешевий вид динамічних ОС. При одношинній топології (рис. 8.7), усі вузли підключені до однієї шини, що сумісно використовується. В кожний момент часу обмін повідомленнями може вести лише одна пара вузлів, тобто на період передавання повідомлення шину можна розглядати як мережу, що складається з двох вузлів.
Рис. 8.7. Одношинна топологія ОС Більш ефективною архітектурою динамічних ОС є система, в якій процесори зв’язані між собою за допомогою матричного комутатора. У цьому випадку в кожний момент часу обмін повідомленнями можуть вести n/2 - пар вузлів, де n – кількість вузлів у системі. Недоліком такої архітектури є висока вартість. Приклад:Побудувати часову діаграму роботи ОС для трипроцесорної ОС топології “Зірка” для заданного на рис. 8.8. дерева обчислювальної задачі:
Рис. 8.8. Дерево обчислювальної задачі ОС для трьох процесорів топології “Зірка” подана на рис. 8.9.
Рис. 8.9. Топологія “Зірка” Часову діаграму роботи ОС для трипроцесорної ОС топології “Зірка” наведено на рис. 8.10.
Рис. 8.10. Часова діаграма роботи ОС для трьохпроцесорної ОС топології “Зірка” Таблиця 8.1
|
