ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 24.12.2021
Просмотров: 1743
Скачиваний: 7
5 2 6 Глава 12. Топологии вычислительных систем
формируется очередь пакетов, которая «рассасывается» по мере освобождения
линий связи между узлами (если очередь также насыщается, согласно одной из
стратегий маршрутизации может произойти так называемый «сброс хвоста» (tail
drop), отказ от вновь поступающих пакетов).
Рис. 1 2 . 1 . Структура сети с централизованным управлением
CMC можно также классифицировать по тому, как в них организовано управ-
ление. В некоторых сетях, особенно с переключением соединений, принято
цент-
рализованное управление
(рис. 12.1). Процессоры посылают запрос на обслужива-
ние в единый контроллер сети, который производит арбитраж запросов с учетом
заданных приоритетов и устанавливает нужный маршрут. К данному типу следу-
ет отнести сети с шинной топологией. Процессорные матрицы также строятся как
сети с централизованным управлением, которое осуществляется сигналами от цен-
трального процессора. Приведенная схема применима и к сетям с коммутацией
пакетов. Здесь тег маршрутизации, хранящийся в заголовке пакета, определяет
адрес узла назначения. Большинство из серийно выпускаемых ВС имеют именно
этот тип управления.
В схемах с
децентрализованным управлением
функции управления распреде-
лены по узлам сети.
Вариант с централизацией проще реализуется, но расширение сети в этом слу-
чае связано со значительными трудностями. Децентрализованные сети в плане
подключения дополнительных узлов значительно гибче, однако взаимодействие
узлов в таких сетях существенно сложнее.
В ряде сетей связь между узлами обеспечивается посредством множества ком-
мутаторов, но существуют также сети с одним коммутатором. Наличие большого
числа кoммутаторов ведет к увеличению времени передачи сообщения, но позво-
ляет использовать простые переключающие элементы. Подобные сети обычно стро-
ятся как многоступенчатые.
Метрики сетевых соединений 5 2 7
Метрики сетевых соединений
При описании CMC их обычно характеризуют с помощью следующих параметров:
-
размера сети
(N
);
-
числа связей (/);
-
диаметра (D);
-
порядка узла
(d
);
-
пропускной способности (W);
-
задержки (T);
-
связности (Q);
-
ширины бисекции (В );
-
полосы бисекции (6).
Размер сети
(network size) численно равен количеству узлов, объединяемых
сетью.
Число связей
(number of links) — это суммарное количество каналов между
всеми узлами сети. В плане стоимости лучшей следует признать ту сеть, которая
требует меньшего числа связей.
Диаметр сети
(network diameter), называемый также
коммуникационным рас-
стоянием,
определяет минимальный путь, по которому проходит сообщение меж-
ду двумя наиболее удаленными друг от друга узлами сети.
Путь
(path) в сети —
это упорядоченное множество каналов
Р =
{с,,
с
2
,..., с
п
}
по которым данные от узла-
источника, последовательно переходя от одного промежуточного узла к другому,
поступают на узел-получатель. Для обозначения отрезка пути между парой
смежных узлов применяют термин
переход
(hop — в живой речи также «тран-
зит» и «хоп»). Минимальный путь от узла
х
до узла
у
— это путь с минимальным
числом переходов. Если обозначить число переходов в минимальном пути от узла
х
до узла
у
через
Н(х, у),
то диаметр сети
D
— это наибольшее значение H
(х, у)
среди
всех возможных комбинаций
х и у.
Так, в цепочке из четырех узлов наибольшее
число переходов будет между крайними узлами, и «диаметр» такой цепочки равен
трем. С возрастанием диаметра сети увеличивается общее время прохождения со-
общения, поэтому разработчики ВС стремятся по возможности обходиться мень-
шим диаметром.
Порядок узла.
Каждый узел сети связан с прочими узлами множеством кана-
лов — множество входных каналов, а —
множество выходных каналов. Порядок узла
х
представляет собой сумму числа
входных |C
ix
| и выходных |C
Ox
| каналов узла, то есть равен числу узлов сети, с кото-
рыми данный узел связан напрямую. Например, в сети, организованной в виде мат-
рицы, где каждый узел имеет каналы только к ближайшим соседям (слева, справа,
сверху и снизу), порядок узла равен четырем. В вычислительной системе СМ-1,
построенной по топологии гиперкуба, каждый узел связан с 12 другими узлами,
следовательно, порядок узлов равен 12. Увеличение значения этой метрики ведет
к усложнению коммутационных устройств сети и, как следствие, к дополнитель-
ным задержкам в передаче сообщений. С другой стороны, повышение порядка
5 2 8 Глава 12. Топологии вычислительных систем
узлов позволяет реализовать топологии, имеющие меньший диаметр сети, и тем
самым сократить время прохождения сообщения. Так, если сеть, состоящая из
4096 узлов (2
12
или 64
2
), построена по матричной схеме, ее диаметр составляет 126,
а для гиперкуба — только 12. Разработчики ВС обычно отдают предпочтение та-
ким топологиям, где порядок всех узлов одинаков, что позволяет строить сети по
модульному принципу. *
Пропускная способность сети
(network bandwidth) характеризуется количе-
ством информации, которое может быть передано по сети в единицу времени. Обыч-
но измеряется в мегабайтах в секунду или гигабайтах в секунду без учета издер-
жек на передачу избыточной информации, например битов паритета.
Задержка сети
(network latency) — это время, требуемое на прохождение сооб-
щения через сеть. В сетях, где время передачи сообщений зависит от маршрута,
говорят о средней, минимальной и максимальной задержках сети.
Связность сети
(network connectivity) можно определить как минимальное
число узлов или линий связи, которые должны выйти из строя, чтобы сеть распа-
лась на две непересекающихся сети. Следовательно, связность сети характеризует
устойчивость сети к повреждениям, то есть ее способность обеспечивать функ-
ционирование ВС при отказе компонентов сети.
Ширина бисекции
(bisection width). Для начала определим понятие
среза сети
(cut of network). Срез сети C(N
1
,
N
2
)
— это множество каналов, разрыв которых
разделяет множество узлов сети N нa два непересекающихся набора узлов
N
1
и
N
2
.
Каждый элемент
C(N
1
, N
2
) —
это канал, соединяющий узел из набора N
1
с узлом из
N
2
Бисекция сети — это срез сети, разделяющий ее примерно пополам, то есть так,
что |N
2
| <= |N
1
| <= |N
2
| + 1. Ширину бисекции
В
характеризуют минимальным числом
каналов, разрываемых при всех возможных бисекциях сети:
Ширина бисекции позволяет оценить число сообщений, которые могут быть
переданы по сети одновременно, при условии что это не вызовет конфликтов из-за
попытки использования одних и тех же узлов или линий связи.
Полоса бисекции
(bisection bandwidth) — это наименьшая полоса пропуска-
ния по всем возможным бисекциям сети. Она характеризует пропускную способ-
ность тех линий связи, которые разрываются при бисекции сети, и позволяет
оценить наихудшую пропускную способность сети при попытке одномоментной
передачи нескольких сообщений, если эти сообщения должны проходить из
одной половины сети в другую. Полоса бисекции
b
определяется выражением
. Для сетей с одинаковой шириной полосы во всех b
с
каналах
справедливо соотношение: b
- b
с
х В .
Малое значение полосы бисекции свидетель-
ствует о возможности конфликтов при одновременной пересылке нескольких со-
общений.
Функции маршрутизации данных
Кардинальным вопросом при выборе топологии CMC является способ маршрути-
зации данных, то есть правило выбора очередного узла, которому пересылается
сообщение. Основой маршрутизации служат адреса узлов. Каждому узлу в сети
Функции маршрутизации данных 5 2 9
присваивается уникальный адрес. Исходя из этих адресов, а точнее, их двоичных
представлений, производится соединение узлов в статических топологиях или их
коммутация в топологиях динамических. В сущности, принятая система соответ-
ствия между двоичными кодами адресов смежных узлов —
функция маршрутиза-
ции данных
— и определяет сетевую топологию. Последнюю можно описать как
набор функций маршрутизации, задающий порядок выбора промежуточных уз-
лов на пути от узла-источника к узлу-получателю. В некоторых топологиях ис-
пользуется единая для всей CMC функция маршрутизации, в других — многосту-
пенчатых — при переходе от одной ступени к другой может применяться иная
функция маршрутизации.
Функция маршрутизации данных задает правило вычисления возможного ад-
реса одного из смежных узлов по адресу второго узла. Сводится это к описанию
алгоритма манипуляции битами адреса-источника для определения адреса-полу-
чателя. Ниже приводится формальное описание основных функций маршрути-
зации данных, применяемых в известных топологиях CMC, без анализа их досто-
инств и недостатков. Последнее, по мере надобности, будет сделано при рас-
смотрении конкретных топологий CMC. Для всех функций предполагается,
что размерность сети равна
N
1
а разрядность адреса —
т,
где
т =
log
2
N. Биты адре-
са обозначены как
b
i
.
Перестановка
Функция перестановки
(exchange) отвечает следующему соотношению:
Работающим примером для данной функции маршрутизации может служить
топология гиперкуба (рис. 12.2).
Рис. 12.2. Пример топологии с функцией перестановки (трехмерный гиперкуб)
Тасование
Функция тасования
(shuffle) может быть реализована в одном из четырех вариан-
тов: идеальное тасование (perfect shuffle), отсутствие тасования (unshuffle), субта-
сование по i-му биту (i
th
subshuffle) и супертасование по i-му биту (i
th
supershuffle).
Ниже приведены формальные описания каждого из перечисленных вариантов, а на
рис. 12.3 — примеры соответствующих им топологий.
- идеальное тасование:
Из приведенной формулы видно, что два узла с адресами
i и j
имеют между
собой непосредственную связь при условии, что двоичный код j может быть
5 3 0 Глава 12. Топологии вычислительных систем
получен из двоичного кода i циклическим сдвигом влево. Идеальное Тасова-
ние — наиболее распространенный среди рассматриваемых вариантов функции
тасования.
- отсутствие тасования:
- субтасование по i-му биту:
- супертасование по i-му биту:
а б в г
Рис. 12.3. Примеры топологий с тасованием для m = 3:
a —
идеальное тасование;
б —
отсутствие тасования;
в —
субтасование по второму биту; г — супертасование
по второму биту
Баттерфляй
Функция
«
баттерфляй»
(butterfly) — «бабочка» была разработана в конце 60-х
годов Рабинером и Гоулдом. Свое название она получила из-за того, что построенная
в соответствии с ней сеть по конфигурации напоминает крылья бабочки (рис. 12.4).
Математически функция может быть записана в виде
Рис. 12.4. Примеры топологии «баттерфляй» для: а — m = 2;б — m = 3
ХОТЯ функция -«баттерфляй» используется в основном при объединении сту-
пеней в сетях с динамической многоступенчатой топологией, известны также
и -«чистые» «баттерфляй»-сети.