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

Глава 12

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

В основе архитектуры любой многопроцессорной вычислительной системы лежит способность к обмену данными между компонентами этой ВС. Коммуникацион­ная система ВС представляет собой сеть, узлы которой связаны трактами передачи данных — каналами. В роли узлов могут выступать процессоры, модули памяти, устройства ввода/вывода, коммутаторы либо несколько перечисленных элемен­тов, объединенных в группу. Организация внутренних коммуникаций вычисли­тельной системы называется топологией.

Топологию сети межсоединений (CMC) определяет множество узлов N, объе­диненных множеством каналов С. Связь между узлами обычно реализуется по двух­точечной схеме (point-to-point). Любые два узла, связанные каналом связи, назы­вают смежными узлами или соседями. Каждый канал с = (х, у) Є С соединяет один узел-источник (source node) x с одним узлом-получателем (recipient node) у, где х, у Є N. Узел-источник, служащий началом канала с, будем обозначать sc, а узел-по­лучатель — второй конец канала — rс. Часто пары узлов соединяют два канала — по одному в каждом направлении. Канал с = (х, у) характеризуется шириной (wc или wxy) — числом сигнальных линий; частотой (ƒc или ƒxy) — скоростью передачи битов по каждой сигнальной линии; задержкой (tc или txy) — временем пересылки бита из узла х в узел у. Для большинства каналов задержка находится в прямой зави­симости от физической длины линии связи (lс) и скорости распространения сигнала (v): 4 = vtc. Полоса пропускания канала bс определяется выражением bc = wcƒc.

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

Узел в сети может быть терминальным, то есть источником или приемником данных, коммутатором, пересылающим информацию с входного порта на выход­ной, или совмещать обе роли. В сетях с непосредственными связями (direct networks)

каждый узел одновременно является как терминальным узлом, так и коммутато­ром, и сообщения пересылаются между терминальными узлами напрямую. В се­тях с косвенными связями (indirect networks) узел может быть либо терминальным, либо коммутатором, но не одновременно, поэтому сообщения передаются опосре­довано, с помощью выделенных коммутирующих узлов. (В дальнейшем для про­стоты изложения позволим называть оба варианта «прямыми» и «косвенными» сетями, также для краткости вместо терминального узла будем говорить «терми­нал», несмотря на некоторую языковую некорректность.) Существуют также та­кие топологии, которые нельзя однозначно причислить ни к прямым, ни к косвен­ным. Любую прямую CMC можно изобразить в виде косвенной, разделив каждый узел на два — терминальный узел и узел коммутации. Современные прямые сети реализуются именно таким образом — коммутатор отделяется от терминального узла и помещается в выделенный маршрутизатор. Основное преимущество пря­мых CMC в том, что коммутатор может использовать ресурсы терминальной час­ти своего узла. Это становится существенным, если учесть, что, как правило, по­следний включает в себя вычислительную машину или процессор.

Тремя важнейшими атрибутами CMC являются:

стратегия синхронизации; стратегия коммутации; стратегия управления.

Две возможных стратегии синхронизации операций в сети — это синхронная и асинхронная. В синхронных CMC все действия жестко согласованы во времени, что обеспечивается за счет единого генератора тактовых импульсов (ГТИ), сигна­лы которого одновременно транслируются во все узлы. В асинхронных сетях еди­ного генератора нет, а функции синхронизации распределены по всей системе, причем в разных частях сети часто используются локальные ГТИ.

В зависимости от выбранной стратегии коммутации различают сети с комму­тацией соединений и сети с коммутацией пакетов. Как в первом, так и во втором варианте информация пересылается в виде пакета. Пакет представляет собой группу битов, для обозначения которой применяют также термин сообщение.

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

Сети с коммутацией пакетов предполагают, что сообщение самостоятельно на­ходит свой путь к месту назначения. В отличие от сетей с коммутацией соедине­ний, маршрут от исходного пункта к пункту назначения каждый раз может быть иным. Пакет последовательно проходит через узлы сети. Очередной узел запоми­нает принятый пакет в своем буфере временного хранения, анализирует его и де­лает выводы, что с ним делать дальше. В зависимости от загруженности сети при­нимается решение о возможности немедленной пересылки пакета к следующему узлу и о дальнейшем маршруте следования пакета на пути к цели. Если все воз­можные тракты для перемещения пакета к очередному узлу заняты, в буфере узла формируется очередь пакетов, которая «рассасывается» по мере освобождения линий связи между узлами (если очередь также насыщается, согласно одной из стратегий маршрутизации может произойти так называемый «сброс хвоста» (tail drop), отказ от вновь поступающих пакетов).

Запросы и адреса в КС.

Сигналы "Занято" и "Подтверждение" из КС

Рис. 12.1. Структура сети с централизованным управлением

CMC можно также классифицировать по тому, как в них организовано управ­ление. В некоторых сетях, особенно с переключением соединений, принято цент­рализованное управление (рис. 12.1). Процессоры посылают запрос на обслужива­ние в единый контроллер сети, который производит арбитраж запросов с учетом заданных приоритетов и устанавливает нужный маршрут. К данному типу следу­ет отнести сети с шинной топологией. Процессорные матрицы также строятся как сети с централизованным управлением, которое осуществляется сигналами от цен­трального процессора. Приведенная схема применима и к сетям с коммутацией пакетов. Здесь тег маршрутизации, хранящийся в заголовке пакета, определяет адрес узла назначения. Большинство из серийно выпускаемых ВС имеют именно этот тип управления.

В схемах с децентрализованным управлением функции управления распреде­лены по узлам сети.

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

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

Метрики сетевых соединений

При описании CMC их обычно характеризуют с помощью следующих параметров:

·  размера сети (N);

·  числа связей (/);

·  диаметра (D);

·  порядка узла (d);

·  пропускной способности (W);

·  задержки (T);

·  связности (Q);

·  ширины бисекции (В );

·  полосы бисекции (b).

Размер сети (network size) численно равен количеству узлов, объединяемых сетью.

Число связей (number of links) — это суммарное количество каналов между всеми узлами сети. В плане стоимости лучшей следует признать ту сеть, которая требует меньшего числа связей.

Диаметр сети (network diameter), называемый также коммуникационным расстоянием, определяет минимальный путь, по которому проходит сообщение между двумя наиболее удаленными друг от друга узлами сети. Путь (path) в сети — это упорядоченное множество каналов Р = {c1, с2,..., сп}, по которым данные от узла-источника, последовательно переходя от одного промежуточного узла к другому, поступают на узел-получатель. Для обозначения отрезка пути между парой смежных узлов применяют термин переход (hop — в живой речи также «транзит» и «хоп»). Минимальный путь от узла х до узла у — это путь с минимальным числом переходов. Если обозначить число переходов в минимальном пути от узла х до узла у через Н(х, y), то диаметр сети D — это наибольшее значение Н(х, у) среди всех возможных комбинаций х и у. Так, в цепочке из четырех узлов наибольшее число переходов будет между крайними узлами, и «диаметр» такой цепочки равен трем. С возрастанием диаметра сети увеличивается общее время прохождения со­общения, поэтому разработчики ВС стремятся по возможности обходиться мень­шим диаметром.

Порядок узла. Каждый узел сети связан с прочими узлами множеством каналов С1х = Clx u СОх, где С1х = {с: rс = х} — множество входных каналов, а СОх = {с: sc = х} — множество выходных каналов. Порядок узла х представляет собой сумму числа входных |С1х|и выходных |СОх| каналов узла, то есть равен числу узлов сети, с которыми данный узел связан напрямую. Например, в сети, организованной в виде матрицы, где каждый узел имеет каналы только к ближайшим соседям (слева, справа, сверху и снизу), порядок узла равен четырем. В вычислительной системе СМ-1, построенной по топологии гиперкуба, каждый узел связан с 12 другими узлами, следовательно, порядок узлов равен 12. Увеличение значения этой метрики ведет к усложнению коммутационных устройств сети и, как следствие, к дополнительным задержкам в передаче сообщений. С другой стороны, повышение порядка узлов позволяет реализовать топологии, имеющие меньший диаметр сети, и тем самым сократить время прохождения сообщения. Так, если сеть, состоящая из 4096 узлов (212 или 642), построена по матричной схеме, ее диаметр составляет 126, а для гиперкуба — только 12. Разработчики ВС обычно отдают предпочтение та­ким топологиям, где порядок всех узлов одинаков, что позволяет строить сети по модульному принципу.

Пропускная способность сети (network bandwidth) характеризуется количеством информации, которое может быть передано по сети в единицу времени. Обычно измеряется в мегабайтах в секунду или гигабайтах в секунду без учета издержек на передачу избыточной информации, например битов паритета.

Задержка сети (network latency) — это время, требуемое на прохождение сообщения через сеть. В сетях, где время передачи сообщений зависит от маршрута, говорят о средней, минимальной и максимальной задержках сети.

Связность сети (network connectivity) можно определить как минимальное число узлов или линий связи, которые должны выйти из строя, чтобы сеть распалась на две непересекающихся сети. Следовательно, связность сети характеризует устойчивость сети к повреждениям, то есть ее способность обеспечивать функ­ционирование ВС при отказе компонентов сети.

Ширина бисекции (bisection width). Для начала определим понятие среза сети (cut of network). Срез сети C(N1 , N2) — это множество каналов, разрыв которых разделяет множество узлов сети N на два непересекающихся набора узлов N1 и N2, Каждый элемент C(N1 , N2) — это канал, соединяющий узел из набора N, с узлом из N2. Бисекция сети — это срез сети, разделяющий ее примерно пополам, то есть так, что |N2| < |N1| < |N2|+ 1. Ширину бисекции В характеризуют минимальным числом каналов, разрываемых при всех возможных бисекциях сети:

В= min |C(N1 , N2)|.

bisection

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

Полоса бисекции (bisection bandwidth) — это наименьшая полоса пропускания по всем возможным бисекциям сети. Она характеризует пропускную способность тех линий связи, которые разрываются при бисекции сети, и позволяет оценить наихудшую пропускную способность сети при попытке одномоментной передачи нескольких сообщений, если эти сообщения должны проходить из одной половины сети в другую. Полоса бисекции b определяется выражением b = min B(N1, N2 ). Для сетей с одинаковой шириной полосы во всех bс каналах справедливо соотношение: b= bс *В. Малое значение полосы бисекции свидетель­ствует о возможности конфликтов при одновременной пересылке нескольких сообщений.

Функции маршрутизации данных

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

Функция маршрутизации данных задает правило вычисления возможного адреса одного из смежных узлов по адресу второго узла. Сводится это к описанию алгоритма манипуляции битами адреса-источника для определения адреса-получателя. Ниже приводится формальное описание основных функций маршрутизации данных, применяемых в известных топологиях CMC, без анализа их достоинств и недостатков. Последнее, по мере надобности, будет сделано при рассмотрении конкретных топологий CMC. Для всех функций предполагается, что размерность сети равна N, а разрядность адреса — т, где т=log2N. Биты адреса обозначены как bi.

Перестановка

Функция перестановки (exchange) отвечает следующему соотношению:

Работающим примером для данной функции маршрутизации может служить топология гиперкуба (рис. 12.2).

Рис. 12.2. Пример топологии с функцией перестановки (трехмерный гиперкуб)

Тасование

Функция тасования (shuffle) может быть реализована в одном из четырех вариан тов: идеальное тасование (perfect shuffle), отсутствие тасования (unshuffle), субта­сование по i-му биту (ith subshuffle) и супертасование по i-му биту (ith supershuffle). Ниже приведены формальные описания каждого из перечисленных вариантов, а на рис. 12.3 — примеры соответствующих им топологий.

Из приведенной формулы видно, что два узла с адресами i и j имеют между собой непосредственную связь при условии, что двоичный код j получен из двоичного кода i циклическим сдвигом влево. Идеальное тасова-ние — наиболее распространенный среди рассматриваемых вариантов функции тасования.

Ш отсутствие тасования:

субтасование по i-му биту:

Ш супертасование по г-му биту:

Рис. 12.3. Примеры топологий с тасованием для m = 3: а — идеальное тасование; б — отсутствие тасования; в — субтасование по второму биту; г — супертасование

по второму биту

Баттерфляй

Функция «баттерфляй» (butterfly) — «бабочка» была разработана в конце 60-х годов Рабинером и Гоулдом. Свое название она получила из-за того, что построенная в соответствии с ней сеть по конфигурации напоминает крылья бабочки (рис. 12.4). Математически функция может быть записана в виде

Рис. 12.4. Примеры топологии «баттерфляй» для: а — т = 2;б — т = 3

Хотя функция «баттерфляй» используется в основном при объединении сту-пеней в сетях с динамической многоступенчатой топологией, известны также и «чистые» «баттерфляй»-сети.

Реверсирование битов

Как следует из названия, функция сводится к перестановке битов адреса в обрат­ном порядке:

R(bm, b m-1 , …, b 1 ) = (b 1 , b 2 , …, b m ).

Соответствующая топология для т = 3 показана на рис. 12.5. Хотя для значе­ний т < 3 топология реверсирования битов совпадает с топологией «баттерфляй», при больших значениях т различия становятся очевидными.

Рис. 12.5. Пример топологии на основе формулы реверсирования битов (m = 3)

Сдвиг

Функция маршрутизации по алгоритму сдвига имеет вид:

SH(x) - (х + 1) mod N (N = 2m).

При т = 3 данной функции соответствует топология кольца (рис. 12.6).

Рис. 12.6. Пример топологии на основе функции сдвига (m = 3)

Сеть ILLIAC IV

Комбинируя несколько вариантов функции сдвига, можно образовать более слож­ные функции маршрутизации. Наиболее известной из таких «сложных» функций является сеть ILLIAC IV, впервые реализованная в топологии вычислительной системы ILLIAC IV:

R+1 = (i+ l) mod N; R-1 = (i- l) mod N;

R+r = (i + r) mod N (0≤i≤N - 1); R-r = (i - r) mod N (r = √N).

Рис. 12.7. Топологии сети ILLIAC IV: а — в виде решетки; б — в виде хордального кольца

Приведенные соотношения для N= 4 отвечают двум вариантам топологии, по­казанным на рис. 12.7.

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

Циклический сдвиг

Функция циклического сдвига (barrel shift) описывается выражениями

B+I(j) = (j+ 2>) mod N,

B-IU) = U - 2') mod N, где 0 <j< N - 1,0 < i < hg2N - 1.

Топологию сети на базе рассматриваемой функции маршрутизации данных иллюстрирует рис. 12.8.

Рис. 12.8. Пример топологии на основе функции циклического сдвига ±2i

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

К статическим топологиям CMC относят такие, где между двумя узлами возмо­жен только один прямой фиксированный путь, то есть статические топологии не предполагают наличия в сети коммутирующих устройств. Если же такие устрой­ства имеются, то используются они только перед выполнением конкретной задачи, а в процессе всего времени вычислений топология CMC остается неиз­менной.

Из возможных критериев классификации статических сетей чаще всего выби­рают их размерность. С этих позиций различают:

V одномерные топологии (линейный массив);

.^ двумерные топологии (кольцо, звезда, дерево, решетка, систолический массив);

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

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

Линейная топология

В простейшей линейной топологии узлы сети образуют одномерный массив и со­единены в цепочку (рис. 12.9). Линейная топология характеризуется следующими параметрами: D = N - \\d= 2; /= /S/"— 1;5= 1.

Линейная топология не обладает свойством полной симметричности, посколь­ку узлы на концах цепочки имеют только одну коммуникационную линию, то есть их порядок равен 1, в то время как порядок остальных узлов равен 2. Время пере­сылки сообщения зависит от расстояния между узлами, а отказ одного из них спо­собен привести к невозможности пересылки сообщения. По этой причине в ли­нейных CMC используют отказоустойчивые узлы, которые при отказе изолируют себя от сети, позволяя сообщению миноватьнеисправный узел.

Кольцевые топологии

Стандартная кольцевая топология представляет собой линейную цепочку, концы которой соединены между собой (рис. 12.10, а). В зависимости от числа каналов между соседними узлами (один или два) различают однонаправленные и двуна­правленные кольца. Кольцевая топология характеризуется следующими парамет­рами:

D = min|— };d=2;I = N;B = 2.

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

Один из способов разрешения проблемы большого диаметра кольцевой сети — добавление линий связи в виде хорд, соединяющих определенные узлы кольца. Подобная топология носит название хордалъной. Если хорды соединяют узлы с

N шагом 1 или — - 1, диаметр сети уменьшается вдвое. На рис. 12.10, б показана хор-

дальная кольцевая сеть с шагом 3.

Рис. 12.10. Кольцевые топологии: а— стандартная; б — хордальная; в — с циклическим

сдвигом связей

В качестве практических примеров для топологии кольца следует назвать сети Token Ring, разработанные фирмой IBM, а также вычислительные системы KSR 1 и SCI.

Дальнейшее увеличение порядка узлов позволяет добиться еще большего со
кращения тракта передачи сообщения. Примером такой топологии может служить
показанная на рис. 12.10, в топология с циклическим сдвигом связей. Здесь стандарт
ная кольцевая топология с N узлами дополнена соединениями между всеми узла ми i и j, для которых | i -j| совпадает с целой степенью числа 2. Алгоритмы марш
рутизации для подобной сети чрезвычайно эффективны, однако порядок узлов по
мере разрастания сети увеличивается.

Звездообразная топология

Звездообразная сеть объединяет множество узлов первого порядка посредством специализированного центрального узла — концентратора (рис. 12.11). Топология характеризуется такими параметрами: D = 2; d = N - 1; I = N - 1; B = 1.

Рис. 12.11. Звездообразная топология

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

Древовидные топологии

Еще одним вариантом структуры CMC является древовидная топология (рис. 12.12, а). Сеть строится по схеме так называемого строго двоичного дерева, где каж­дый узел более высокого уровня связан с двумя узлами следующего по порядку более низкого уровня. Узел, находящийся на более высоком уровне, принято на­зывать родительским, а два подключенных к нему нижерасположенных узла — дочерними. В свою очередь, каждый дочерний узел выступает в качестве родитель­ского для двух узлов следующего более низкого уровня. Отметим, что каждый узел связан только с двумя дочерними и одним родительским. Если h — высота дерева (количество уровней в древовидной сети), определяемая как max [log2N], то такую сеть можно охарактеризовать следующими параметрами: D= 2(h— 1); d = 3; I =N - 1; B=1. Так, вычислительная система из узлов при решетчатой топологии (немного забегаем вперед) будет иметь диаметр 512, а в случае строго бинарного де­рева — только 36. Топология двоичного дерева была использована в мультипроцес­сорной системе DADO из 1023 узлов, разработанной в Колумбийском университете.

Рис. 12.12. Древовидная топология: а — стандартное дерево; б — «толстое» дерево

При больших объемах пересылок между несмежными узлами древовидная топология оказывается недостаточно эффективной, поскольку сообщения долж­ны проходить через один или несколько промежуточных звеньев. Очевидно, что на более высоких уровнях сети вероятность затора из-за недостаточно высокой пропускной способности линий связи выше. Этот недостаток устраняют с помощью топологии, называемой «толстым» деревом (рис. 12.12, б).

Идея «толстого» дерева состоит в увеличении пропускной способности комму­никационных линий на прикорневых уровнях сети. С этой целью на верхних уровнях сети родительские и дочерние узлы связывают не одним, а несколькими каналами, причем чем выше уровень, тем больше число каналов. На рисунке это отображено в виде множественных линий между узлами верхних уровней. Топо­логия «толстого» дерева реализована в вычислительной системе СМ-5.

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

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

в г д

Рис. 12.13. Решетчатые топологии: а — плоская; б — цилиндрическая; в — тороидальная;

д — витая тороидальная

Простейшими примерами для одномерных массивов могут служить цепочка и кольцо. Для двумерных массивов данных наиболее подходит топология плоской прямоугольной матрицы узлов, каждый из которых соединен с ближайшим сосе дом (рис. 12.13, а). Такая сеть размерности т x т () имеет следующие ха рактеристики: D = 2(т - 1); d = 4; I= 2N - 2т; В = т.

Если провести операцию свертывания (wraparound) плоской матрицы, соединив информационными трактами одноименные узлы левого и правого столбцов или одноименные узлы верхней и нижней строк плоской матрицы, то из плоской конструкции получаем топологию типа цилиндра (рис. 12,13, б). В топологии цилиндра каждый ряд (или столбец) матрицы представляет собой кольцо. Если одновременно произвести свертывание плоской матрицы в обоих направлениях, по лучим тороидальную топологию сети (рис. 12.13, в). Двумерный тор на базе решетки т х т обладает следующими параметрами:

; d = 4; I=2N; B = 2m.

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

рис. 12.13, г.

Помимо свертывания к плоской решетке может быть применена операция скру чивания (twisting). Суть этой операции состоит в том, что вместо колец все узлы объединяются в разомкнутую или замкнутую спираль, то есть узлы, расположен ные с противоположных краев плоской решетки, соединяются с некоторым сдви гом. Если горизонтальные петли объединены в виде спирали, образуется так назы ваемая сеть типа ILLIAC. На рис. 12.13, д показана подобная конфигурация CMC, соответствующая хордальной сети четвертого порядка и характеризуемая следу ющими метриками: D = т - 1; d = 4; I = 2N; В = 2т.

Следует упомянуть и трехмерные сети. Один из вариантов, реализованный в ар хитектуре суперЭВМ Cray T3D, представляет собой трехмерный тор, образован ный объединением процессоров в кольца по трем координатам: x,y и z.

Примерами ВС, где реализованы различные варианты решетчатых топологий, могут служить: ILLIAC IV, МРР, DAP, CM-2, Paragon и др.

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

В полносвязной топологии (рис. 12.14), известной также под названием топологии «максимальной группировки» или «топологии клика» (clique - полный подграф [ма-тем.]), каждый узел напрямую соединен со всеми остальными узлами сети. Сеть, состоящая из N узлов, имеет следующие параметры:

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

Если размер сети велик, топология становится дорогостоящей и трудно реали зуемой. Более того, топология максимальной группировки не дает существенного улучшения производительности, поскольку каждая операция пересылки требует, чтобы узел проанализировал состояние всех своих N-1 входов. Для ускорения этой операции необходимо, чтобы все входы анализировались параллельно, что, в свою очередь, усложняет конструкцию узлов.

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

При объединении параллельных процессоров весьма популярна топология ги перкуба, показанная на рис. 12.15. Линия, соединяющая два узла (рис. 12.15, а),определяет одномерный гиперкуб. Квадрат, образованный четырьмя узлами (рис. 12.15, б) — двумерный гиперкуб, а куб из 8 узлов (рис. 12.15, в) — трехмерный гиперкуб и т. д. Из этого ряда следует алгоритм получения m-мерного гиперкуба: начинаем с (т - 1)-мерного гиперкуба, делаем его идентичную копию, а затем добавляем связи между каждым узлом исходного гиперкуба и одноименным узлом копии. Гиперкуб размерности m(N= 2m) имеет следующие характеристики:

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

Обмен сообщениями в гиперкубе базируется на двоичном представлении номеров узлов. Нумерация узлов производится так, что для любой пары смежных узлов двоичное представление номеров этих узлов отличается только в одной позиции. В силу сказанного, узлы 0010 и 0110 — соседи, а узлы 0110 и 0101 таковыми не являются. Простейший способ нумерации узлов при создании m-мерного гиперкуба из двух (m - 1)-мерных показан на рис. 12.15, д. При копировании (т - 1)-мерного гиперкуба и соединении его с исходным (т - 1)-мерным гиперкубом не­обходимо, чтобы соединяемые узлы имели одинаковые номера. Далее к номерам узлов исходного гиперкуба слева добавляется бит, равный 0, а к номерам узлов копии — единичный бит.

Рис. 12.15. Топология гиперкуба: а - одномерная; б - двумерная; в - трехмерная; г - четырехмерная; д - схема формирования четырехмерного гиперкуба из двух трехмерных

Номера узлов являются основой маршрутизации сообщений в гиперкубе. Такие номера в m-мерном гиперкубе состоят из m битов, а пересылка сообщения из узла А в узел В выполняется за тп шагов. На каждом шаге узел может либо сохранить сообщение и не пересылать его дальше до следующего шага, либо отправить его дальше по одной из линий. На шаге i узел, хранящий сообщение, сравнивает i-й бит своего собственного номера с i-м битом номера узла назначения. Если они совпадают, продвижение сообщения прекращается, если нет — сообщение переда ется вдоль линии i-ro измерения. Линией г-го измерения считается та, которая была добавлена на этапе построения i-мерного гиперкуба из двух (i - 1)-мерных.

Создание гиперкуба при большом числе процессоров требует увеличения порядка узлов, что сопряжено с большими техническими проблемами. Компромиссное решение, несколько увеличивающее диаметр сети при сохранении базовой структуры, представляет собой куб из циклически соединенных узлов (рис. 12.16). Здесь порядок узла равен трем при любом размере сети.

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

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

Название топологии означает, что в ней реализуется куб, имеющий п измерений, причем каждое измерение содержит k узлов (JV = kn). Каждому узлу назначен n-разрядный номер в системе счисления с основанием k, и он связан с узлом, номер которого отличается только в одной цифре и только на единицу. k-ичный п-куб может быть построен путем объединения k экземпляров k-ичных (n - 1)-кубов в кольцо.

Многие ранее рассмотренные топологии представляют собой варианты топологии k-ичного и n-куба:

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

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

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

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

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

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

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

Таблица 12.1	. Характеристики сетей со статической топологией
Топология	Диаметр	Порядок узла	Число связей	Ширина бисекции	Симме­тричность	Размер сети
Полно-связная	1	N-1			Да	N узлов
Звезда	2	1	N-1	1	Нет	N узлов
Двоичное дерево	2(А-1)	3	N-1	1	Нет	Высота дерева h = log2N
					прооолжениеÈ

Таблица 12.1 {продолжение)

Топология	Диаметр	Порядок узла	Число связей	Ширина бисекции	Симме­тричность	Размер сети
Линейный массив	N-1	2	N-1	1	Нет	N узлов
Кольцо		2	N	2	Да	N узлов
Двумерная решетка	2(m-1)	4	2N-2m		Нет	Решетка m х т, где m=√N
Двумерный тор		4	2N	2т	Да	Тор т х т, где т =√N
Гиперкуб	n	п			Да	N узлов; n =log.2N
k-ичный n-куб		2n	nN	2kn-1	Да	N = kn узлов

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

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

Если входы и выходы сети коммутирующих элементов разделены, сеть называ­ют двусторонней (two-sided). При совмещенных входах и выходах сеть является односторонней (one-sided).

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

Блокирующие и неблокирующие многоуровневые сети

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

В неблокирующих сетях обеспечивается соединение между любыми парами входных и выходных терминалов без перенастройки коммутирующих элементов сети. В рамках этой группы различают сети строго неблокирующие (strictly non-blocking) и неблокирующие в широком смысле (wide sense non-blocking). В строго неблокирующих сетях возникновение блокировок принципиально невозможно в силу примененной топологии. К таким относятся матричная сеть и сеть Клоша. Неблокирующими в широком смысле называют топологии, в которых конфликты при любых соединениях не возникают только при соблюдении определенного алгоритма маршрутизации.

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

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

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

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

Многошинная топология предполагает наличие п независимых шин и подключение узлов к каждой из этих шин (рис. 12.17, б), что* позволяет вести одновременную пересылку сообщений между п парами узлов. Такая топология вполне пригодна для высокопроизводительных ВС. Диаметр сети по-прежнему равен 1, в то время как пропускная способность возрастает пропорционально числу шин. По сравнению с одношинной архитектурой управление сетью с несколькими шинами сложнее из-за необходимости предотвращения конфликтов, возникающих, когда в парах узлов, обменивающихся по разным шинам, присутствует общий узел. Кроме того, с увеличением порядка узлов сложнее становится их техническая реализация.

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

Топология перекрестной коммутации («кроссбар»)

Топология перекрестной коммутации мультипроцессорной системы (crossbar switch system) на основе матричного (координатного) коммутатора представляет собой классический пример одноступенчатой динамической сети. Не совсем официальна ный термин «кроссбар», который будет применяться в дальнейшем для обозначая ния данной топологии, берет свое начало с механических координатных (шаговых) искателей, использовавшихся на заре телефонии. Кроссбар п х т (рис. 12.18) 'i представляет собой коммутатор, способный соединить п входных и т выходных терминальных узлов с уровнем параллелизма, равным min (n, т). Главное достоинство рассматриваемой топологии состоит том, что сеть получается неблокирующей и обеспечивает меньшую задержку в передаче сообщений по сравнению с другими топологиями, поскольку любой путь содержит только один ключ. Тем не менее, из-за того, что число ключей в сети равно п х т, использование кроссбара в больших сетях становится непрактичным, хотя это достаточно хороший выбор для малых сетей. Ниже будет показано, что для больших неблокирующих сетей можно предложить иные топологии, требующие существенно меньшего количества ключей.

Рис. 12.18. Матричный коммутатор nxm

Когда п = т, о такой ситуации говорят «полный кроссбар» (присвоим мужской род, хотя, как и все неодушевленное, в английском это средний род). «Полный крос­сбар» на п входов и п выходов содержит п2 ключей. Диаметр сети равен 1, ширина бисекции — n/2. Этот вариант часто используют в сетях с древовидной топологией

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

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

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

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

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

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

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

В сетях, относящихся к первой группе, в качестве базового коммутирующего элемента используется кроссбар пхт. Для второй категории роль коммутирующего элемента играет «полный кроссбар» 2x2. Потенциально такой коммутатор управляется четырехразрядным двоичным кодом и обеспечивает 16 вариантов коммутации, из которых полезными можно считать 12. На практике же обычно задействуют только четыре возможных состояния кроссбара 2x2, которые определяются двухразрядным управляющим кодом (рис. 12.19). Подобный кроссбар называют базовым коммутирующим элементом (БКЭ) или β-элементом. Первые два состояния БКЭ являются основными: в них входная информация может транслироваться на выходы прямо либо перекрестно. Два следующих состояния предназначены для широковещательного режима, когда сообщение от одного узла одновременно транслируется на все подключенные к нему прочие узлы. Широковещательный режим используется редко. Сигналы на переключение БКЭ в определенное состояние могут формироваться устройством управления сетью. В более сложном варианте БКЭ эти сигналы формируются внутри самого Р-элемента, исходя из адресов пунктов назначения, содержащихся во входных сообщениях.

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

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

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

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

Данный вид сети получил свое название из-за того, что его схема напоминает воз­душные корни дерева баньян (индийской смоковницы) [98]. В топологии «Бань­ян» между каждой входной и выходной линиями существует только один путь [156]. Сеть пхп(п = 2т) состоит из тп/2 базовых коммутирующих элементов.

Сеть «Баньян» 4 х 4 по топологии совпадает с сетью «Баттерфляй». На рис. 12.21 показана сеть «Баньян» 8x8. Передаваемый пакет в своем заголовке содержит трехразрядный двоичный номер узла назначения. Данная сеть относится к сетям с самомаршрутизацией (self-routing), поскольку адрес пункта назначения не толь­ко определяет маршрут сообщения к нужному узлу, но и используется для управ­ления прохождением сообщения по этому маршруту. Каждый БКЭ, куда попадает пакет, просматривает один бит адреса и в зависимости от его значения направляет сообщение на выход 1 или 2. Состояние р-элементов первой ступени сети (левый столбец БКЭ) определяется старшим битом адреса узла назначения. Средней сту-~пенью (второй столбец) управляет средний бит адреса, а третьей ступенью (пра­вый столбец) — младший бит. Если значение бита равно 0, то сообщение пропус­кается через верхний выход БКЭ, а при единичном значении — через нижний. На рисунке показан маршрут сообщения с входного узла 2 (0102) к выходному узлу 5 (1012). Адрес узла назначения содержится в заголовке сообщения.

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

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

Сеть с топологией «Омега» по сути является подклассом «баньян»-сетей [71,148, 203] и представляет собой многоуровневую структуру, где смежные уровни связа­ны между собой согласно функции идеального тасования. Сеть и х п, где п = 2т, состоит из т уровней БКЭ, при общем числе БКЭ - тп/2. Количество соедине­ний, обеспечиваемых сетью «Омега», равно п"/г, что гораздо меньше, чем и!, то есть топология «Омега» является блокирующей. Так, при п = 8 процент комбинаций, возможных в сети «Омега», по отношению к потенциально допустимому числу

комбинаций составляет%

Рассмотрим порядок установки (3-элементов сети для соединения входного и выходного терминальных узлов, двоичное и-разрядное представление номеров которых есть соответственно (а„оп_, ... а,) и (&„£„_, ... 6,). Состояние, в которое пе-реключается БКЭ на i-й ступени, определяется с помощью операции сложения по модулю 2 значений i-го бита в адресах входного и выходного терминальных узлов. Если аi Å bi = О, то БКЭ, расположенный на i-й ступени сети, обеспечивает прямую связь входа с выходом, а при аp Å bp = 1 — перекрестное соединение. На рис. 12.22 показан процесс прохождения сообщения по сети «Омега» 8 х 8 от входного терминала 2 (0102) к выходному терминалу 6(1102). Таким образом, если в сообщении присутствуют адреса источника и получателя сообщений, сеть може-йфункционировать в режиме самомаршрутизации.

Топология «Дельта»

Важный подкласс «баньян»-сетей образуют сети «Дельта», предложенные Пателом в 1981 году [176]. В них основание системы счисления при адресации узловдля маршрутизации может отличаться от 2. Сеть соединяет аn входов с bn выходами посредством п ступеней кроссбаров а х b (в сетях с такими топологиями, как «Омега», «базовая линия» и «косвенный» n-куб, используется двоичная система счисления, то есть а=2иb=2). Адрес получателя задается в заголовке сообщения числом в системе счисления с основанием b, а для прохождения сообщения по сети организуется самомаршрутизация. Каждая цифра адреса имеет значение в диапазоне от 0 до b - 1 и выбирает один из b выходов коммутирующего элемента типа кроссбар а х b. Пример сети «Дельта» показан на рис. 12.23, а.

Рис. 12.23. Структура сети «Дельта»: а — по базе 4; б — с дополнительной ступенью

В отличие от сети «Омега» входы не подвергаются тасованию. Это не влияет на алгоритм маршрутизации, поскольку важность имеет не адрес источника, а адрес получателя. На рис. 12.23, а связь между ступенями соответствует идеальному тасованию — коммутаторы соединены так, что для связи любого входа с любым выходом образуется единственный путь, причем пути для любой пары равны по длине. В сеть «Дельта» могут быть введены и дополнительные ступени (рис. 12.23, б), чтобы обеспечить более чем один маршрут от входа к выходу.

Топология Бенеша

Как уже отмечалось, в топологии «Баньян» между каждой входным и выходным терминалом существует только один путь. С добавлением к такой сети дополнительной ступени БКЭ число возможных маршрутов удваивается. Дополнительные пути позволяют изменять трафик сообщения с целью устранения конфликтов. При добавлении к сети «Баньян» (т - 1)-го уровня, где п = 2m, получаем топологию Бенеша (рис. 12.24) [152, 172]. В сети Бенеша п х п число ступеней определяется выражением 2т - 1, а число БКЭ равно —

Сеть Бенеша с п входами и п выходами имеет симметричную структуру, в каж­дой половине которой (верхней и нижней) между входными и выходными БКЭ расположена такая же сеть Бенеша, но с п/2 входами и n/2 выходами.

Рис. 12.24. Топология Бенеша: а — 4x4; б — 8x8

Рассматриваемая топология относится к типу неблокирующих сетей с рекон­фигурацией.

Топология Клоша

В 1953 году Клош показал, что многоступенчатая сеть на основе элементов типа кроссбар, содержащая не менее трех ступеней, может обладать характеристиками неблокирующей сети [62, 76].

Сеть Клоша с тремя ступенями, показанная на рис. 12.25, содержит г, кроссбаров во входной ступени, m кроссбаров в промежуточной ступени и r2 кроссбаров в выходной ступени. У каждого коммутатора входной ступени есть n1 входов и m выходов — по одному выходу на каждый кроссбар промежуточной ступени. Коммутаторы промежуточной ступени имеют r1, входов по числу кроссбаров входной ступени и r2 выходов, что соответствует количеству переключателей в выходной ступени сети. Выходная ступень сети строится из кроссбаров с m входами и n2 выходами. Отсюда числа n1, n2, r1, r2 и m полностью определяют сеть. Число входов ceти N= r1 n1 а выходов — М = r2 n2.

Рис. 12.25. Трехступенчатая сеть с топологией Клоша

Связи внутри составного коммутатора организованы по следующим правилам:

·  k-й выход i-гo входного коммутатора соединен с i-м входом k-го промежуточно го коммутатора;

·  k-й вход j-го выходного коммутатора соединен c j-м выходом k-го промежуточ­ного коммутатора.

Каждый модуль первой и третьей ступеней сети соединен с каждым модулем второй ее ступени.

Хотя в рассматриваемой топологии обеспечивается путь от любого входа к любому выходу, ответ на вопрос, будет ли сеть неблокирующей, зависит от числа промежуточных звеньев. Клош доказал, что подобная сеть является неблокирующей, если количество кроссбаров в промежуточной ступени т удовлетворяет условию: т = п2 + п2 - 1. Если n1 = п2, то матричные переключатели в промежуточ­ной ступени представляют собой «полный кроссбар» и критерий неблокируемости приобретает вид: т = 2п - 1. При условии т = п2 сеть Клоша можно отнести к неблокирующим сетям с реконфигурацией. Во всех остальных случаях данная топология становится блокирующей.

Вычислительные системы, в которых соединения реализованы согласно топологии Клоша, выпускают многие фирмы, в частности Fujitsu (FETEX-150), Nippon Electric Company (ATOM), Hitachi. Частный случай сети Клоша при n = r1 = r2 = п2 называется сетью «Мемфис». Топология «Мемфис» нашла применение в вычислительной системе GF-11 фирмы IBM.

Топология двоичной п-кубической сети с косвенными связями

На рис. 12.26 показана косвенная двоичная «-кубическая сеть 8x8 [180,188].

Рис. 12.26. Топология двоичной n-кубической сети

Здесь ступени коммутации связаны по топологии «Баттерфляй», а на последней ступени используется функция идеального тасования. Фактически сеть представляет собой обращенную матрицу сети «Омега». В этом можно убедиться, если соответствующим образом поменять местами БКЭ в каждом уровне сети «Омега», за исключением первого и последнего.

Топология базовой линии

Данный вид сети представляет собой многоступенчатую топологию, где в качестве коммутаторов служат β-элементы (12.27). Топология обеспечивает очень удобный алгоритм самомаршрутизации, в котором последовательные ступени коммутаторов управляются последовательными битами адреса получателя. Каждая ступень сети на принципе базовой линии делит возможный диапазон маршрутов пополам. Старший бит адреса назначения управляет первой ступенью. При нулевом значении этого бита сообщения с любого из входов поступят на вторую ступень сети с верхних выходов БКЭ первой ступени, то есть они смогут прийти только на верхнюю половину выходов (в нашем примере это выходы с номерами 000-011), а при единичном значении бита — на нижнюю половину выходов (100-111). Второй бит адреса назначения управляет коммутаторами второй ступени, которая делит половину выходов, выбранную первой ступенью, также пополам. Процесс повторяется на последующих ступенях до тех пор, пока младший бит адреса назначения на последней ступени не выберет нужный выход сети. Таким образом, сеть на 8 входов требует наличия трех ступеней коммутации, сеть на 16 входов — 4 ступеней и т. д.

Рис.12.27.Топология базовой линии

5.  Дайте характеристику плюсов и минусов кольцевой топологии сети. Какие варианты этой топологии практически используются?

6.  Проведите сравнительный анализ звездообразной и древовидной топологий сети.

7. Выполните сравнительный анализ известных вариантов решетчатой топологии сети.

8.  Поясните смысл топологии k-ичного n-куба сети. Как строится такой куб?

9.  Дайте сравнительную характеристику блокирующих и неблокирующих многоуровневых сетей.

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

11.  Сравните популярные разновидности «баньян»-сетей: «Омега», «Дельта». Можно ли причислить к этому классу сети Бенеша, и если можно, то почему?

12. Дайте развернутое объяснение отличий топологии Клоша от «баньян»-сетей. Можно ли найти у них сходные черты, и если можно, то какие?

13. С какой топологией сходна организация двоичной и-кубической сети с косвенными связями? Ответ обоснуйте, приведя конкретный пример.

14. Охарактеризуйте смысл топологии на принципе базовой линии. Изобразите структуру соответствующей сети на 20 входов.