Файл: 481-550.pdf

Скачать файл (0,95Мб)

Заказать решение

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

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

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

Добавлен: 24.12.2021

Просмотров: 1532

Скачиваний: 4

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

Динамические топологии 5 4 1

(перестановок — permutations). Проблема усложняется, когда сеть должна обес-
печивать одновременную передачу данных между многими парами терминальных
узлов (multicast), причем так, чтобы не возникали конфликты (блокировки) из-за
передачи данных через одни и те же коммутирующие элементы в одно и то же
время. Подобные топологии должны поддерживать n" перестановок. С этих пози-
ций все топологии CMC с коммутацией разделяются на три типа: неблокирую-
щие, неблокирующие с реконфигурацией и блокирующие.

неблокирующих сетях

обеспечивается соединение между любыми парами

входных и выходных терминалов без перенастройки коммутирующих элементов

сети, В рамках этой группы различают сети строго неблокирующие (strictly non-
blocking) и неблокирующие в широком смысле (wide sense non-blocking), В

строго

неблокирующих сетях

возникновение блокировок принципиально невозможно

в силу примененной топологии. К таким относятся матричная сеть и сеть Клоша.

Неблокирующими в широком смысле

называют топологии, в которых конфликты

при любых соединениях не возникают только при соблюдении определенного ал-
горитма маршрутизации.

неблокирующих сетях с реконфигурацией

также возможна реализация соеди-

нения между произвольными входными и выходными терминалами, но для этого
необходимо изменить настройку коммутаторов сети и маршрут связи между со-
единенными терминалами. Примерами таких сетей служат сети Бенеша, Бэтчера,
«Мемфис» и др.

блокирующих сетях,

если какое-либо соединение уже установлено, это может

стать причиной невозможности установления других соединений. К блокирую-
щим относятся сети «Баньяна, «Омега», n-куб и др.

Шинная топология

Сети с шинной архитектурой — наиболее простой и дешевый вид динамических
сетей. При

одношинной топологии,

показанной на рис. 12,17, а, все узлы имеют по-

рядок 1 ( d = 1 ) и подключены к одной совместно используемой шине. В каждый
момент времени обмен сообщениями может вести только одна пара узлов, то есть
на период передачи сообщения шину можно рассматривать как сеть, состоящую
из двух узлов, в силу чего ее диаметр всегда равен 1 (D=1), Также единице равна
и ширина бисекции

(B),

поскольку топология допускает одновременную передачу

только одного сообщения. Однотипная конфигурация может быть полезной, ког-
да число узлов невелико, то есть когда трафик шины мал по сравнению с ее про-

пускной способностью. Одношинную архитектуру часто используют для объеди-
нения нескольких узлов в группу (кластер), после чего из таких кластеров образуют

сеть на базе других видов топологии.

Многошинная топология

предполагает наличие

независимых шин и подклю-

чение узлов к каждой из этих шин (рис, 12.17,

б),

что позволяет вести одновремен-

ную пересылку сообщений между

парами узлов. Такая топология вполне при-

годна для высокопроизводительных ВС. Диаметр сети по-прежнему равен 1, в то

время как пропускная способность возрастает пропорционально числу шин. По

сравнению с одношинной архитектурой управление сетью с несколькими шинами
сложнее из-за необходимости предотвращения конфликтов, возникающих, когда

5 4 2

Глава 12. Топологии вычислительных систем

в парах узлов, обменивающихся по разным шинам, присутствует общий узел. Кро-

ме того, с увеличением порядка узлов сложнее становится их техническая реали-
зация.

Рис. 12.17.

Шинная топология: а —с одной шиной; б —со многими шинами

Топология перекрестной коммутации

(«кроссбар»)

Топология перекрестной коммутации

мультипроцессорной системы (crossbar switch

system) на основе матричного (координатного) коммутатора представляет собой

классический пример одноступенчатой динамической сети. Не совсем официаль-

лый термин «кроссбар», который будет применяться в дальнейшем для обозначе-

ния данной топологии, берет свое начало с механических координатных (шаго-
вых) искателей, использовавшихся на заре, телефонии. Кроссбар nхm (рис. 12.18)
представляет собой коммутатор, способный соединить

входных и

выходных

терминальных узлов с уровнем параллелизма, равным min (n, m). Главное досто-

инство рассматриваемой топологии состоит том, что сеть получается неблокирую-
щей и обеспечивает меньшую задержку в передаче сообщений по сравнению с дру-
гими топологиями, поскольку любой путь содержит только один ключ. Тем не
менее, из-за того, что число ключей в сети равно

т,

использование кроссбара

в больших сетях становится непрактичным, хотя это достаточно хороший выбор

для малых сетей. Ниже будет показано, что для больших неблокирующих сетей

можно предложить иные топологии, требующие существенно меньшего количе-
ства ключей.

Рис.

12.18. Матричный коммутатор n x m

Когда

п = т,

о такой ситуации говорят

«полный кроссбар

» (присвоим мужской

род, хотя, как и все неодушевленное, в английском это средний род). «Полный крос-

сбар»- на n входов и

выходов содержит

ключей. Диаметр сети равен 1, ширина

бисекции — n/2. Этот вариант часто используют в сетях с древовидной топологией

Динамические топологии 5 4 3

для объединения узлов нижнего уровня, роль которых играют небольшие группы

(кластеры) процессоров и модулей памяти.

Современные коммерчески доступные матричные коммутаторы способны со-

единять до 256 устройств. Топология используется для организации соединений
в некоторых серийно выпускаемых вычислительных системах, например в Fujitsu
VPP500 224x224.

Коммутирующие элементы сетей

с динамической топологией

Поскольку последующие рассматриваемые топологии относятся к многоступен-

чатым, сначала необходимо определить типы коммутирующих элементов, приме-

няемых в ступенях коммутации таких сетей. По этому признаку различают:

сети на основе перекрестной коммутации;

сети на основе базового коммутирующего элемента.

В сетях, относящихся к первой группе, в качестве базового коммутирующего

элемента используется кроссбар

т.

Для второй категории роль коммутирую-

щего элемента играет -«полный кроссбар» 2x2. Потенциально такой коммутатор

управляется четырехразрядным двоичным кодом и обеспечивает 16 вариантов ком-

мутации, из которых полезными можно считать 12. На практике же обычно задей-

ствуют только четыре возможных состояния кроссбара 2x2, которые определяются
двухразрядным управляющим кодом (рис. 12.19). Подобный кроссбар называ-

ют

базовым коммутирующим элементом

(БКЭ) или

b-элементом.

Первые два

состояния БКЭ являются основными: в них входная информация может трансли-
роваться на выходы прямо либо перекрестно. Два следующих состояния предна-
значены для широковещательного режима, когда сообщение от одного узла одновре-
менно транслируется на все подключенные к нему прочие узлы. Широковещатель-
ный режим используется редко. Сигналы на переключение БКЭ в определенное
состояние могут формироваться устройством управления сетью. В более сложном
варианте БКЭ эти сигналы формируются внутри самого

-элемента, исходя из ад-

ресов пунктов назначения, содержащихся во входных сообщениях.

Рис. 12.19. Состояния

-элемента

Структура

-элемента показана на рис. 12.20.

Выбор в пользу того или иного варианта коммутации входных сообщений (па-

кетов) осуществляется схемой логики принятия решения

-элемента. Конкретный

вид коммутации реализуется сдвоенным мультиплексором, управляемым с выхо-

да защелки, где хранится результат работы схемы логики принятия решения. Эле-

менты задержки обеспечивают синхронизацию процессов принятия решения и пе-
ресылки пакетов с входов на выходы.

5 4 4 Глава

12.

Топологии вычислительных систем

Рис.12.20. Структура

-элемента

Сложность

-элемента находится в зависимости от логики принятия решения.

В ряде архитектур БКЭ их состояние определяется только битом активности па-

кета. В иных архитектурах используются адреса источника и получателя данных,
хранящиеся в заголовке пакета, что может потребовать поддержания в БКЭ спе-
циальных таблиц. Тем не менее во всех своих вариантах

-элементы достаточно

просты, что позволяет реализовать их на базе интегральных микросхем.

Топология «Баньян»

Данный вид сети получил свое название из-за того, что его схема напоминает воз-

душные корни дерева баньян (индийской смоковницы) [98]. В топологии «Бань-

ян» между каждой входной и выходной линиями существует только один путь

[156]. Сеть n х

п (п - 2

)

состоит из

тп/2

базовых коммутирующих элементов.

Сеть «Баньян» 4x4 по топологии совпадаете сетью «Баттерфляй». На рис. 12.21

показана сеть «Баньян» 8x8. Передаваемый пакет в своем заголовке содержит
трехразрядный двоичный номер узла назначения. Данная сеть относится к

сетям

самомаршрутизацией

(self-routing), поскольку адрес пункта назначения не толь-

ко определяет маршрут сообщения к нужному узлу, но и используется для управ-
ления прохождением сообщения по этому маршруту. Каждый БКЭ, куда попадает

пакет, просматривает один бит адреса и в зависимости от его значения направляет

сообщение на выход 1 или 2. Состояние

-элементов первой ступени сети (левый

столбец БКЭ) определяется старшим битом адреса узла назначения. Средней сту-
пенью (второй столбец) управляет средний бит адреса, а третьей ступенью (пра-
вый столбец) — младший бит. Если значение бита равно 0, то сообщение пропус-
кается через верхний выход БКЭ, а при единичном значении — через нижний. На
рисунке показан маршрут сообщения с входного узла 2 (0102) к выходному узлу 5
(1012). Адрес узла назначения содержится в заголовке сообщения.

Топология «Баньян» весьма популярна из-за того, что коммутация обеспечи-

вается простыми БКЭ, работающими с одинаковой скоростью, сообщения переда-
ются параллельно. Кроме того, большие сети могут быть построены из стандарт-
ных модулей меньшего размера.

Динамические топологии 5 4 5

Топология «Омега»

Сеть с топологией «Омега» по сути является подклассом «баньян»-сетей [71,148,
203] и представляет собой многоуровневую структуру, где смежные уровни связа-
ны между собой согласно функции идеального тасования. Сеть nхn, где

= 2

состоит из

уровней БКЭ, при общем числе БКЭ —

тп/2.

Количество соедине-

ний, обеспечиваемых сетью «Омега», равно n

n/2

что гораздо меньше, чем n!, то есть

топология «Омега» является блокирующей. Так, при

п =

8 процент комбинаций,

возможных в сети «Омега», по отношению к потенциально допустимому числу