Файл: Tannenbaum.pdf

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

Машина 1

Машина 2

Машина 1

Машина 2

Прикладной

уровень

Система

поддержки

исполнения

программ

Операционная

система

Прикладной

уровень

Система

поддержки

исполнения

программ

Операционная

система

Аппаратное

обеспечение

Аппаратное

обеспечение

Совместно используемая память

Машина 1 Машина 2

Прикладной

уровень

Система

поддержки

исполнения

программ

Операционная

система

Аппаратное

обеспечение

Прикладной

уровень

Система

поддержки

исполнения

программ

Операционная

система

Аппаратное

обеспечение

Прикладной

уровень

Система

поддержки

исполнения

программ

Прикладной

уровень

Система

поддержки

исполнения

программ

Операционная

система

Аппаратное

обеспечение

Операционная

система

Аппаратное

обеспечение

Совместно используемая память

Совместно используемая память

Рис. 8.3. Уровни, на которых можно реализовать память совместного использования:

аппаратное обеспечение (а); операционная система (б); программное обеспечение (в)

5 6 4 Глава 8. Архитектуры компьютеров параллельного действия

Сети межсоединений

На рис. 8.2 мы показали, что мультикомпьютеры связываются через сети межсое-

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

ны друг с другом и с процессорами. Следовательно, многое из того, о чем мы будем
говорить в этом разделе, применимо к обоим типам систем.

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

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

Это действие представляет собой то же самое, что и передача сообщений: инициа-

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

Сети межсоединений могут состоять максимум из пяти компонентов:

1. Центральные процессоры.

2. Модули памяти.
3. Интерфейсы.
4. Каналы связи.
5. Коммутаторы.

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

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

диняется локальная шина каждого процессора и которая может передавать сигналы
процессору и локальной памяти (если таковая есть). Часто внутри интерфейса

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

Каналы связи — это каналы, по которым перемещаются биты. Каналы могут

быть электрическими или оптико-волоконными, последовательными (шириной

1 бит) или параллельными (шириной более 1 бита). Каждый канал связи характе-

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

Коммутаторы — это устройства с несколькими входными и несколькими вы-

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

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

Сети межсоединений можно сравнить с улицами города. Улицы похожи на ка-

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

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

При разработке и анализе сети межсоединений важно учитывать несколько

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

Топология

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

степенью

 узла, инженеры —

 коэффициентом разветвления.

 Чем больше степень,

тем больше вариантов маршрута и тем выше отказоустойчивость. Если каждый
узел содержит

 к

 дуг и соединение сделано правильно, то можно построить сеть

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

Следующее свойство сети межсоединений — это ее

 диаметр.

 Если расстоянием

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

Еще одно важное свойство сети межсоединений — это ее пропускная способ-

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

Очень важная характеристика —

 бисекционная пропускная способность.

 Чтобы

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

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

566

Глава 8. Архитектуры компьютеров параллельного действия

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

•

I

/

•

•

•

 ;

•-—_

 7

~~~

"\.

4

1

/

/

Рис.

 8.4. Различные топологии. Жирные точки соответствуют коммутаторам. Процессоры

и модули памяти не показаны: звезда (а); полное межсоединение (full interconnect) (б);

дерево (в); кольцо (г); решетка (д); двойной тор (е); куб (ж); гиперкуб (з)

Сети межсоединений можно характеризовать по их

 размерности.

 Размерность

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

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

то сеть одномерна. Если есть две оси и пакет может направиться направо или налево

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

На рис. 8.4 показано несколько топологий. Здесь изображены только кана-

лы связи (это линии) и коммутаторы (это точки). Модули памяти и процессоры
(они на рисунке не показаны) подсоединяются к коммутаторам через интерфей-
сы. На рис. 8.4,

 а

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

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

На рис. 8.4,

 б

 изображена другая нульмерная топология —

 полное межсоеди-

нение

 (full interconnect). Здесь каждый узел непосредственно связан с каждым

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

 к

 узлов требуется к(к-1)/2 каналов, а это совершенно неприемле-

мо для больших значений к.

На рис. 8.4,

 в

 изображена третья нульмерная топология —

 дерево.

 Здесь основ-

ная проблема состоит в том, что пропускная способность между секциями равна
пропускной способности каналов. Обычно у верхушки дерева наблюдается очень
большой поток обмена информации, поэтому верхние узлы становятся препятстви-
ем для повышения производительности. Можно разрешить эту проблему, увели-
чив пропускную способность верхних каналов. Например, самые нижние каналы
будут иметь пропускную способность Ь, следующий уровень — пропускную способ-
ность 2Ь, а каждый канал верхнего уровня — пропускную способность 4b. Такая
схема называется

 толстым деревом (fat tree).

 Она применялась в коммерческих

мультикомпьютерах Thinking Machines' CM-5.

Кольцо

 (рис. 8.4,

 г) —

 это одномерная топология, поскольку каждый отправ-

ленный пакет может пойти направо или налево.

 Решетка

 или

 сетка

 (рис. 8.4,

 д)

 —

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

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

 Двойной тор

 (рис. 8.4,

 е)

 явля-

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

Куб

 (рис. 8.4,

 ж)

 — это правильная трехмерная топология. На рисунке изобра-

жен куб 2x2x2, но в общем случае он может быть kxkxk. На рис. 8.4,

 з

 показан

четырехмерный куб, полученный из двух трехмерных кубов, которые связаны меж-
ду собой. Можно сделать пятимерный куб, соединив вместе 4 четырехмерных куба.
Чтобы получить 6 измерений, нужно продублировать блок из 4 кубов и соединить
соответствующие узлы и т. д.; n-мерный куб называется

 гиперкубом.

 Эта тополо-

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