Файл: 481-550.pdf

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

  5 3 1

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

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

Соответствующая топология для

 т

 = 3 показана на рис. 12.5. Хотя для значе-

ний

 т <

 3 топология реверсирования битов совпадает с топологией «баттерфляй»,

при больших значениях

 т

 различия становятся очевидными.

Рис. 12.5.

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

Сдвиг

Функция

 маршрутизации по алгоритму сдвига

 имеет вид:

При

 т =

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

Рис. 12.6.

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

Сеть ILLIACIV

Комбинируя несколько вариантов функции сдвига, можно образовать более слож-

ные функции маршрутизации. Наиболее известной из таких «сложных» функций
является

 сеть ILLIAC IV,

 впервые реализованная в топологии вычислительной

системы ILLIAC IV:

5 3 2

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

Рис. 12.7.

 Топологии сети ILUACIV:

 а — в

 виде решетки;

 б —

 в виде хордального кольца

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

казанным на рис. 12.7.

Первый вариант представляет собой фигуру, построенную на базе плоской ре-

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

му кольцу с шагом хорды, равным 4.

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

Функция циклического сдвига

 (barrel shift) описывается выражениями

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

иллюстрирует рис. 12.8.

Рис.

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

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

К статическим топологиям CMC относят такие, где между двумя узлами возмо-

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

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

дачи, а в процессе всего времени вычислений топология CMC остается неиз-

менной.

Из возможных критериев классификации статических сетей чаще всего выби-

рают их размерность. С этих позиций различают:

-

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

-

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

-

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

- гиперкубическую топологию.

Ниже рассматриваются основные виды статических топологий CMC без ак-

центирования внимания на какой-либо их классификации, поскольку этот момент

для поставленных в учебнике целей несущественен.

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

В простейшей

 линейной топологии

 узлы сети образуют одномерный массив и со-

единены в

 цепочки

 (рис. 12.9). Линейная топология характеризуется следующими

параметрами:

Рис. 12.9. Линейная топология

Линейная топология не обладает свойством полной симметричности, посколь-

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

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

Стандартная

 кольцевая топология

 представляет собой линейную цепочку, концы

которой соединены между собой (рис, 12.10,

 а).

 В зависимости от числа каналов

между соседними узлами (один или два) различают

 однонаправленные

 и

 двуна-

правленные

 кольца. Кольцевая топология характеризуется следующими парамет-

рами:

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

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

Один из способов разрешения проблемы большого диаметра кольцевой сети —

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

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

 хордалъной.

 Если хорды соединяют узлы с

шагом 1 или N/2-1,диаметр сети уменьшается вдвое. На рис. 12.10,

6

 показана

 хор-

дольная кольцевая сеть

 с шагом 3.

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

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

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

В качестве практических примеров для топологии кольца следует назвать сети

Token Ring, разработанные фирмой IBM, а также вычислительные системы KSR1
и

  S C I .

Дальнейшее увеличение порядка узлов позволяет добиться еще большего со-

кращения тракта передачи сообщения. Примером такой топологии может служить
показанная на рис. 12.10,

 в

 топология с

 циклическим сдвигом связей.

 Здесь стандарт-

ная кольцевая топология с

 N

 узлами дополнена соединениями между всеми узла-

ми i и j, для которых |

i-j|

 совпадает с целой степенью числа 2. Алгоритмы марш-

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

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

Звездообразная сеть

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

специализированного центрального узла — концентратора (рис. 12.11). Топология
характеризуется такими параметрами:

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

Звездообразная организация узлов и соединений редко используется для объ-

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

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

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

По производительности эти топологии также идентичны. Основное преимущество

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

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

Еще одним вариантом структуры CMC является

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

 (рис.

12.12,

 а).

 Сеть строится по схеме так называемого строго двоичного дерева, где каж-

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

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

зывать

 родительским,

 а два подключенных к нему нижерасположенных узла —

дочерними.

 В свою очередь, каждый дочерний узел выступает в качестве родитель-

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

связан только с двумя дочерними и одним родительским. Если h

 —

 высота дерева

(количество уровней в древовидной сети), определяемая как max [log

2

 N], то такую

сетьможноохарактеризоватьследующимипараметрами:D=2(h- 1

);d=3;l=N-

 1;

В

 = 1. Так, вычислительная система из 262 144 узлов при решетчатой топологии

(немного забегаем вперед) будет иметь диаметр 512, а в случае строго бинарного де-
рева — только 36. Топология двоичного дерева была использована в мультипроцес-
сорной системе DADO из 1023 узлов, разработанной в Колумбийском университете.

а б

Рис. 12.12. Древовидная топология:

 a

 — стандартное дерево;

 б

 — "толстое" дерево

При больших объемах пересылок между несмежными узлами древовидная

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

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

топологии, называемой "

толстым" деревом

 (рис. 12.12,

 б).

Идея "толстого" дерева состоит в увеличении пропускной способности комму-

никационных линий на прикорневых уровнях сети. С этой целью на верхних

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

каналами, причем чем выше уровень, тем больше число каналов. На рисунке это

отображено в виде множественных линий между узлами верхних уровней. Топо-
логия «толстого» дерева реализована в вычислительной системе СМ-5.