Файл: 481-550.pdf

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

Решетчатые топологии

Поскольку значительная часть научно-технических задач связана с обработ-

кой массивов, вполне естественным представляется стремление учесть это и в
топологии ВС, ориентированных на подобные задачи. Такие топологии отно-
сят к

 решетчатым

 (mesh), а их конфигурация определяется видом и размер-

ностью массива.

Простейшими примерами для одномерных массивов могут служить цепочка

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

дом (рис. 12.13, а). Такая сеть размерности имеет следующие ха-

рактеристики;

 D = 2(т- 1);d=4;I=2N- 2m; В-т.

Если провести операцию

 свертывания

 (wraparound) плоской матрицы, соеди-

нив информационными трактами одноименные узлы левого и правого столбцов
или одноименные узлы верхней и нижней строк плоской матрицы, то из плоской

конструкции получаем топологию типа цилиндра (рис. 12.13,

 б).

 В топологии ци-

линдра каждый ряд (или столбец) матрицы представляет собой кольцо. Если од-
новременно произвести свертывание плоской матрицы в обоих направлениях, по-
лучим тороидальную топологию сети (рис. 12.13,

 в).

 Двумерный тор на базе решетки

т x т

 обладает следующими параметрами:

Статические топологии  5 3 7

Объемный вид тороидальной топологии для массива размерности  4 x 8 показан на
рис. 12.13, г.

Помимо свертывания к плоской решетке может быть применена операция

 скру-

чивания

 (twisting). Суть этой операции состоит в том, что вместо колец все узлы

объединяются в разомкнутую или замкнутую спираль, то есть узлы, расположен-
ные с противоположных краев плоской решетки, соединяются с некоторым сдви-
гом. Если горизонтальные петли объединены в виде спирали, образуется так назы-
ваемая сеть типа ILLI АС. На рис. 12.13,

 д

 показана подобная конфигурация CMC,

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

ющими метриками: D

 = т-

 1; d = 4; / = 2N;

 В = 2т.

Следует упомянуть и трехмерные сети. Один из вариантов, реализованный в ар-

хитектуре суперЭВМ Cray T3D, представляет собой трехмерный тор, образован-

ный объединением процессоров в кольца по трем координатам:

 х,у и z.

Примерами ВС, где реализованы различные варианты решетчатых топологий,

могут служить: ILLIAC IV, МРР, DAP, CM-2, Paragon и др.

Полносвязная топология

В

 полносвязной топологии

 (рис. 12.14), известной также под названием топологии

«максимальной группировки» или «топологии клика»

 (clique — полный подграф [ма-

тем.]), каждый узел напрямую соединен со всеми остальными узлами сети. Сеть,

состоящая из

 N

 узлов, имеет следующие параметры:

Рис. 12.14. Полносвязная топология

Если размер сети велик, топология становится дорогостоящей и трудно реали-

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

чтобы узел проанализировал состояние всех своих

 N—

 1 входов. Для ускорения

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

Топология гиперкуба

При объединении параллельных процессоров весьма популярна топология ги-
перкуба, показанная на рис. 12.15. Линия, соединяющая два узла (рис. 12.15,

 а).

5 3 8

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

определяет одномерный гиперкуб. Квадрат, образованный четырьмя узлами

(рис. 12.15, б) — двумерный гиперкуб, а куб из 8 узлов (рис. 12.15,

 в) —

 трех-

мерный гиперкуб и т. д. Из этого ряда следует алгоритм получения m-мерного ги-
перкуба: начинаем с (m - 1)-мерного гиперкуба, делаем его идентичную копию,

а затем добавляем связи между каждым узлом исходного гиперкуба и одноименным
узлом копии. Гиперкуб размерности

 т (N -

 2

m

) имеет следующие характеристики:

Увеличение размерности гиперкуба на 1 ведет к удвоению числа его узлов, увели-

чению порядка узлов и диаметра сети на единицу.

Обмен сообщениями в гиперкубе базируется на двоичном представлении но-

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

узлов двоичное представление номеров этих узлов отличается только в одной по-
зиции. В силу сказанного, узлы 0010 и 0110 — соседи, а узлы 0110 и 0101 таковыми

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

 (т-

 1)-мерных показан на рис. 12.15,

 д.

 При копировании (m- 1)-

мерного гиперкуба и соединении его с исходным

 (т

 - 1)-мерным гиперкубом не-

обходимо, чтобы соединяемые узлы имели одинаковые номера. Далее к номерам
узлов исходного гиперкуба слева добавляется бит, равный 0, а к номерам узлов
копии — единичный бит,

г

 а

Рис. 12.15. Топология гиперкуба:

 а —

 одномерная; б —двумерная; в — трехмерная;

 г —

четырехмерная; д — схема формирования четырехмерного гиперкуба из двух трехмерных

Номера узлов являются основой маршрутизации сообщений в гиперкубе. Та-

кие номера в m-мерном гиперкубе состоят из

 т

 битов, а пересылка сообщения из

узла

 А

 в узел

 В

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

нить сообщение и не пересылать его дальше до следующего шага, либо отправить

его дальше по одной из линий. На шаге

 i

 узел, хранящий сообщение, сравнивает

(i-й бит своего собственного номера с i-м битом номера узла назначения. Если они

совпадают, продвижение сообщения прекращается, если нет — сообщение переда-

Статические топологии  5 3 9

ется вдоль линии i-гo измерения. Линией i-го измерения считается та, которая была
добавлена на этапе построения t-мерного гиперкуба из двух (i - 1)-мерных.

Создание гиперкуба при большом числе процессоров требует увеличения по-

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

 куб из циклически соединенных узлов

 (рис. 12.16).

Здесь порядок узла равен трем при любом размере сети.

Рис. 12.16. Куб из циклически соединенных узлов третьего порядка

Топология k-ичного n-куба

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

 (N = k

ll

).

 Каждому узлу назначен n-разрядный

номер в системе счисления с основанием

 k,

 и он связан с узлом, номер которого отли-

чается только в одной цифре и только на единицу. k-ичный n-куб может быть построен
путем объединения

 k

 экземпляров k-ичных (n - 1)-кубов в кольцо.

Многие ранее рассмотренные топологии представляют собой варианты топо-

логии k-ичного n-куба:

- k

-ичный 1-куб— кольцо;

- k-ичный 2-куб — двумерный тор;

- k

-ичный 3-куб — трехмерный тор;

- 4-ичный 2-куб — плоская решетка  4 x 4 ;

-

 2-ичный n-куб — гиперкуб.

Доказано, что эффективность топологии, а также ее масштабируемость улуч-

шаются с ростом значения

 k

 и уменьшением количества измерений

 п.

Данные по рассмотренным статическим топологиям сведены в табл. 12.1.

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

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

Б

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

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

ключами, варьируя установки которых можно менять топологию сети. В отличие

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

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

элементы, а устройства, обменивающиеся сообщениями (терминалы), подключа-
ются к входам и выходам этой сети. В роли терминалов могут выступать процессо-
ры или процессоры и модули памяти.

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

ют

 двусторонней

 (two-sided). При совмещенных входах и выходах сеть является

односторонней

 (one-sided).

Обычно ключи в динамических CMC группируются в так называемые

 ступени

коммутации.

 В зависимости от того, сколько ступеней коммутации содержит сеть,

она может быть

 одноступенчатой

 или

 многоступенчатой.

 Наличие более чем од-

ной ступени коммутации позволяет обеспечить множественность путей между

любыми парами входов и выходов.

Блокирующие и неблокирующие

многоуровневые сети

Минимальным требованием к сети с коммутацией является поддержка соедине-

ния любого входа с любым выходом. Для этого в сети с

 п

 входами и

 п

 выходами

система ключей обязана предоставить

 п\

 вариантов коммутации входов и выходов