ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 24.12.2021
Просмотров: 1535
Скачиваний: 4
5 4 6 Глава 12. Топологии вычислительных систем
реключается БКЭ на i-й ступени, определяется с помощью операции сложения по
модулю 2 значений i-ro бита в адресах входного и выходного терминальных узлов.
Если то БКЭ, расположенный на
i-й
ступени сети, обеспечивает пря-
мую связь входа с выходом, а при — перекрестное соединение. На
рис. 12.22 показан процесс прохождения сообщения по сети «Омега» 8 х 8 от вход-
ного терминала 2 (010
2
) к выходному терминалу 6(110
2
). Таким образом, если в со-
общении присутствуют адреса источника и получателя сообщений, сеть может
функционировать в режиме самомаршрутизации.
Топология «Дельта»
Важный подкласс «баньян»-сетей образуют сети «Дельта», предложенные Пате-
лом в 1981 году [176]. В них основание системы счисления при адресации узлов
для маршрутизации может отличаться от 2. Сеть соединяет a
n
входов с
b
n
выхода-
ми посредством
п
ступеней кроссбаров
а
х
b
(в сетях с такими топологиями, как
«Омега», «базовая линиям и «косвенный» n-куб, используется двоичная система
счисления, то есть
а
= 2 и b
=
2). Адрес получателя задается в заголовке сообще-
ния числом в системе счисления с основанием b
,
а для прохождения сообщения по
сети организуется самомаршрутизация. Каждая цифра адреса имеет значение
в
диа-
пазоне от 0 до b
-
1 и выбирает один из b выходов коммутирующего элемента типа
кроссбар
а
х
Ь.
Пример сети «Дельта» показан на рис. 12.23,
а.
Рис. 12.23. Структура сети «Дельта»:
a —
по базе 4;
б —
с дополнительной ступенью
Динамические топологии 5 4 7
В отличие от сети «Омега» входы не подвергаются тасованию. Это не влияет на
алгоритм маршрутизации, поскольку важность имеет не адрес источника, а адрес
получателя. На рис. 12.23,
а
связь между ступенями соответствует идеальному та-
сованию — коммутаторы соединены так, что для связи любого входа с любым
выходом образуется единственный путь, причем пути для любой пары равны по длине.
В сеть «Дельта» могут быть введены и дополнительные ступени (рис. 12.23,
б),
что-
бы обеспечить более чем один маршрут от входа к выходу.
Топология Бенеша
Как уже отмечалось, в топологии «Баньян» между каждой входным и выходным
терминалом существует только один путь. С добавлением к такой сети дополни-
тельной ступени БКЭ число возможных маршрутов удваивается. Дополнитель-
ные пути позволяют изменять трафик сообщения с целью устранения конфликтов.
При добавлении к сети -«Баньян»
(т
- 1)-го уровня, где я - 2
m
, получаем тополо-
гию Бенеша (рис. 12.24) [152,172]. В сети Бенеша
п
х
п
число ступеней определя-
ется выражением
2т
- 1, а число БКЭ равно —n/2 (2m-1).
Сеть Бенеша с
п
входами и n выходами имеет симметричную структуру, в каж-
дой половине которой (верхней и нижней) между входными и выходными БКЭ
расположена такая же сеть Бенеша, но с
п/2
входами и n/2 выходами.
Р и с . 1 2 . 2 4 . Т о п о л о г и я Б е н е ш а : а —
4 х 4; б —
8 x 8
5 4 8 Глава 12. Топологии вычислительных систем
Рассматриваемая топология относится к типу неблокирующих сетей с рекон-
фигурацией.
Топология Клоша
В 1953 году Клош показал, что многоступенчатая сеть на основе элементов типа
кроссбар, содержащая не менее трех ступеней, может обладать характеристиками
неблокирующей сети [62,7
6].
Сеть Клоша с тремя ступенями, показанная на рис. 12.25, содержит r
1
, кроссба-
ров во входной ступени,
т
кроссбаров в промежуточной ступени и r
2
кроссбаров
в выходной ступени. У каждого коммутатора входной ступени есть n
1
входов и
т
выходов — по одному выходу на каждый кроссбар промежуточной ступени. Ком-
мутаторы промежуточной ступени имеют r
1
, входов по числу кроссбаров входной
ступени и r
2
выходов, что соответствует количеству переключателей в выходной
ступени сети. Выходная ступень сети строится из кроссбаров с
т
входами и n
2
вы-
ходами. Отсюда числа n
2
,n
2
, r
1
,r
2
и т
полностью определяют сеть. Число входов
сети
N = r
1
n
1
а выходов —
М = r
2
n
2
.
Рис. 12.25. Трехступенчатая сеть с топологией Клоша
Связи внутри составного коммутатора организованы по следующим правилам:
- k
-й выход i-ro входного коммутатора соединен с i-м входом k-го промежуточно-
го коммутатора;
- k-й
вход j-го выходного коммутатора соединен
c j-м
выходом k-го промежуточ-
ного коммутатора.
Динамические топологии 5 4 9
Каждый модуль первой и третьей ступеней сети соединен с каждым модулем
второй ее ступени.
Хотя в рассматриваемой топологии обеспечивается путь от любого входа
к любому выходу, ответ на вопрос, будет ли сеть неблокирующей, зависит от числа
промежуточных.звеньев. Клош доказал, что подобная сеть является неблокирую-
щей, если количество кроссбаров в промежуточной ступени
т
удовлетворяет ус-
ловию:
т =
n
2
+ п
2
- 1. Если n
1
=
п
2
,
то матричные переключатели в промежуточ-
ной ступени представляют собой «полный кроссбар» и критерий неблокируемости
приобретает вид:
т — 2п-\.
При условии
т = п
2
сеть Клоша можно отнести к не-
блокирующим сетям с реконфигурацией. Во всех остальных случаях данная топо-
логия становится блокирующей.
Вычислительные системы, в которых соединения реализованы согласно топо-
логии Клоша, выпускают многие фирмы, в частности Fujitsu (FETEX-150), Nippon
Electric Company (ATOM), Hitachi. Частный случай сети Клоша при n
1
= r
1
,=r
2
=
n
2
называется сетью «Мемфис». Топология «Мемфис» нашла применение в вычис-
лительной системе GF-11 фирмы IBM.
Топология двоичной n-кубической сети
с косвенными связями
На рис. 12.26 показана косвенная двоичная n-кубическая сеть 8 х 8 [ 180,188].
Рис. 12.26. Топология двоичной n-кубической сети
Здесь ступени коммутации связаны по топологии «Баттерфляй», а на послед-
ней ступени используется функция идеального тасования. Фактически сеть пред-
ставляет собой обращенную матрицу сети «Омега», В этом можно убедиться, если
соответствующим образом поменять местами БКЭ в каждом уровне сети «Омега»,
за исключением первого и последнего.
Топология базовой линии
Данный вид сети представляет собой многоступенчатую топологию, где в каче-
стве коммутаторов служат
b
-элементы (12.27). Топология обеспечивает очень удоб-
5 5 0 Глава 12. Топологии вычислительных систем
ный алгоритм самомаршрутизации, в котором последовательные ступени комму-
таторов управляются последовательными битами адреса получателя. Каждая сту-
пень сети на принципе базовой линии делит возможный диапазон маршрутов по-
полам. Старший бит адреса назначения управляет первой ступенью. При нулевом
значении этого бита сообщения с любого из входов поступят на вторую ступень
сети с верхних выходов БКЭ первой ступени, то есть они смогут прийти только на
верхнюю половину выходов (в нашем примере это выходы с номерами 000-011),
а при единичном значении бита— на нижнюю половину выходов (100-111). Вто-
рой бит адреса назначения управляет коммутаторами второй ступени, которая де-
лит половину выходов, выбранную первой ступенью, также пополам. Процесс
повторяется на последующих ступенях до тех пор, пока младший бит адреса
назначения на последней ступени не выберет нужный выход сети. Таким образом,
сеть на 8 входов требует наличия трех ступеней коммутации, сеть на 16 входов —
4 ступеней и т. д.
Рис. 12.27.Топология базовой линии
Как видно из рисунка, сеть с топологией базовой линии совпадает с первыми
т
(п
- 2
m
) уровнями сети Бенеша на
п
входов и
п
выходов. Если к последнему уров-
ню этой сети добавить сеть с инверсной перестановкой битов, то получим так на-
зываемую
R-сеть.
Сеть с инверсной перестановкой битов имеет фиксированные
связи входного терминала (a
m
a
m-1
... а
1
) с выходным терминалом (a
1
,а
2
...
а
т
)
и фак-
тически представляет собой косвенную двоичную n-кубическую сеть.
Контрольные вопросы
1. Прокомментируйте классификацию сетей по топологии, функциональности
узлов, изменяемости взаимосвязей, синхронизации, коммутации и управлению.
2. Дайте развернутую характеристику метрик, описывающих соединения сети.
3. Сформулируйте достоинства и недостатки наиболее известных функций мар-
шрутизации данных.
4. Обоснуйте достоинства и недостатки линейной топологии сети.