ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 24.12.2021
Просмотров: 6758
Скачиваний: 22
454
В першому варіанті з'єднання, наведеному на рис. 12.30, всі блоки пам'яті під'єднані до всіх шин. Тут, як і на наступних рисунках, прийнято, що кількість процесорів N = 6, кількість модулів пам'яті М = 4, кількість шин В = 4.
Цей варіант з'єднання є досить складним та дорогим, оскільки вимагає великої кількості шин, реалізація яких вимагає значних апаратних ресурсів.
В другому варіанті (рис. 12.31) кожний модуль пам'яті під'єднаний до деякої однієї шини.
Тут структура комунікаційної мережі спрощується, однак можливі конфлікти доступу до блоків пам'яті.
Це дозволяє зменшити кількість можливих конфліктів доступу до блоків пам'яті.
В третьому варіанті (рис. 12.32) кожен модуль пам'яті під'єднаний не до всіх, як в першому варіанті, а до деякої групи шин (в даному випадку до двох шин).
455
В четвертому варіанті (рис. 12.33) модулі
пам'яті згруповані в класи, які під'єднані
до свого набору шин.
Тут клас - це
довільно вибрана множина модулів
пам'яті. Такий підхід також дозволяє
зменшити кількість конфліктів шляхом
врахування особливостей виконуваних
задач (інтенсивності обміну процесорів
з пам'яттю). Можна характеризувати цей
тип мережі використовуючи кількість
необхідних зв'язків і навантаження на
кожну шину, як показано в табл. 12.2, де
наведені характеристики розглянутих
багатошинних з'єднань. У цій таблиці k
представляє число класів; g
представляє число шин на
групу, і Mj представляє
число модулів пам'яті в класі j.
В цілому багатошинна багатопроцесорна організація має кілька бажаних особливостей, таких як висока надійність і легкість нарощування. Коли кількість шин є меншою за кількість модулів пам'яті (або кількості процесорів), змагання за володіння шиною посилюється.
Важливим питанням в багатошинній багатопроцесорній організації є шинна синхронізація. Інформація може бути передана по шині синхронно або асинхронно. Час для будь-якої передачі по синхронній шині відомий наперед. При прийманні та відправленні інформації через шину потрібно брати до уваги час передачі. Організація асинхронної шини, з другого боку, залежить від наявності даних і готовності пристрою ініціювати шинні операції.
В одношинній багатопроцесорній системі потрібен шинний арбітраж для вирішення шинного конфлікту, який має місце, коли більш ніж один процесор конкурує за оволодіння шиною. В даному випадку процесори, які хочуть використовувати шину, подають запити до шинної арбітражної логіки. Арбітр вирішує, використовуючи схему пріоритету, якому процесору буде надано доступ до шини протягом певного часового інтервалу.
456
Процес асинхронної взаємодії одного процесора з іншим називають квітуванням. Він вимагає використання трьох керуючих сигналів: запит шини, надання шини та інформування про її зайнятість. Перший вказує, що процесор подав запит про надання шини, тоді як другий вказує, що шина надана. Третій сигнал зазвичай використовується, щоб вказати, чи зайнятою є шина в даний час. Рис. 12.34 ілюструє механізм квітування шини.
Для прийняття рішення якому процесору надати контроль над шиною, шинна арбітражна логіка використовує вбудовану схему пріоритету. Використовують різні типи схем пріоритету, наприклад випадковий пріоритет, однаковий пріоритет, пріоритет найдовше не використовуваного LRU.
У однаковому пріоритеті, коли два або більше запитів зроблено, є рівний шанс у будь-якого з них. При використанні правила LRU найвищий пріоритет надано процесору, який не використав шину протягом найдовшого часу.
12.9.5. Комутуючі динамічні комунікаційні мережі багатопроцесорних систем
12.9.5.1. Типи комутуючих динамічних комунікаційних мереж
В мережах цього типу з'єднання між процесорами та модулями пам'яті здійснюється використовуючи прості комутуючі елементи.
Всі топології комутуючих комунікаційних мереж багатопроцесорних систем розділяють на три типи: неблокуючі, неблокуючі з реконфігурацією і блокуючі.
У неблокуючих мережах забезпечується з'єднання між будь-якими парами вхідних і вихідних терміналів без зміни режиму роботи комутуючих елементів мережі. В рамках цієї групи розрізняють мережі строго неблокуючі та неблокуючі в широкому сенсі.
457
У строго неблокуючих мережах виникнення блокувань принципово неможливе через застосовану топологію. До таких належать матрична мережа та мережа Клоса. Неблоку-ючими в широкому сенсі називають топології, в яких конфлікти при будь-яких з'єднаннях не виникають тільки при дотриманні певного алгоритму маршрутизації.
У неблокуючих мережах з реконфігурацією також можлива реалізація з'єднання між довільними вхідними і вихідними терміналами, але для цього необхідно змінити настройку комутаторів мережі та маршрут зв'язку між сполученими терміналами. Прикладами таких мереж служать мережі Бенеша, Бетчера, "Мемфіс" й інші.
У блокуючих мережах, якщо яке-небудь з'єднання вже встановлене, це може стати причиною неможливості встановлення інших з'єднань. До блокуючих належать мережі "Баньян", "Омега", n-куб і інші.
Існує три базові топології комутуючих динамічних комунікаційних мереж багатопроцесорних систем: координатні, одноярусні та багатоярусні.
12.9.5.2. Координатна мережа
Координатна мережа забезпечує одночасне з'єднання всіх входів з усіма виходами. Вона містить комутуючий елемент (КЕ) на перетині будь-яких двох ліній. На рис. 12.35 наведено приклад координатної мережі розміром 8x8. В цьому випадку КЕ знаходяться на кожному з 64 перетинів. На рисунку показано випадок, коли забезпечується одночасне з'єднання між входами Р. та виходами М8-1. для і від 1 до 8. Два можливих стани КЕ показано внизу рисунка: прямо та навхрест.
В загальному для координатної мережі розміром NxN кількість КЕ рівна N2, тобто апаратна асимптотична складність, виражена кількістю КЕ, є 0(N2), тоді як часова асимптотична складність є О(І).
Потрібно зауважити, що координатна мережа є неблокуючою.
458
Топологія комутуючої комунікаційної мережі на основі матричного координатного комутатора є класичним прикладом одноярусної динамічної мережі. Головна перевага даної топології полягає в тому, що мережа є неблокуючою і забезпечує меншу затримку передачі повідомлень в порівнянні з іншими топологіями, оскільки будь-який шлях містить тільки один ключ. Проте через те, що число ключів в мережі рівне NxM, використання координатного комутатора у великих мережах стає непрактичним, хоча це достатньо хороший вибір для малих мереж. Нижче буде показано, що для великих не-блокуючих мереж можна запропонувати інші топології, що вимагають істотно меншої кількості ключів.
12.9.5.3. Матрична одноярусна комутуюча мережа
Матрична одноярусна комутуюча мережа є найшвидшою. Вона забезпечує реалізацію всіх типів з'єднань і є неблокуючою. Структура матричної одноярусної комутуючої мережі наведена на рис. 12.36.
Дана мережа складається з М N-входових мультиплексорів, які керуються М кодами К0 , К1 ,..., Кm-1 , розрядність кожного з яких рівна log2N. Кожний з мультиплексорів реалізується на основі N двовходових схем І, об'єднаних N-входовою схемою АБО. Тому для комутації N входів на М виходів дана комунікаційна мережа повинна містити М груп по N двовходових схем І, об'єднаних N-входовою схемою АБО. Витрати обладнання на двовходову схему І, як і на двовходову схему АБО, рівні одному вентилю. Позначимо затримку одного вентиля через і. Тоді витрати обладнання на дану комунікаційну мережу, без врахування витрат на керування, складуть WKMM = M(2N-1) вентилів, а затримка TKMM = (logN+l)t.
12.9.5.4. Багатоярусні блокуючі комутуючі мереж
Економнішими порівняно з координатною та матричною КММ є багатоярусні комутуючі мережі, які будуються на базі комутуючого елементу, що зазвичай має два входи і два виходи. Можливі комбінації з'єднання входів з виходами такого КЕ показані на рис. 12.36.