Танненбаум Е. Архітектура компютера [pdf]
.pdf
5 6 4 Глава 8. Архитектуры компьютеров параллельного действия
Сети межсоединений
На рис. 8.2 мы показали, что мультикомпьютеры связываются через сети м динений. Рассмотрим их подробнее. Интересно отметить, что мультикомпь и мультипроцессоры очень сходны в этом отношении, поскольку мультипро ры часто содержат несколько модулей памяти, которые также должны быть ны друг с другом и с процессорами. Следовательно, многое из того, о чем мы говорить в этом разделе, применимо к обоим типам систем.
Основная причина сходства коммуникационных связей в мультипроце мультикомпьютере заключается в том, что в обоих случаях применяется пе сообщений. Даже в однопроцессорной машине, когда процессору нужно с или записать слово, он устанавливает определенные линии на шине и ждет Это действие представляет собой то же самое, что и передача сообщений: и тор посылает запрос и ждет ответа. В больших мультипроцессорах взаимоде между процессорами и удаленной памятью почти всегда состоит в том, чт цессор посылает в память сообщение, так называемый пакет, который запр ет определенные данные, а память посылает процессору ответный пакет.
Сети межсоединений могут состоять максимум из пяти компонентов:
1.Центральные процессоры.
2.Модули памяти.
3.Интерфейсы.
4.Каналы связи.
5.Коммутаторы.
Процессоры и модули памяти мы уже рассматривали в этой книге и бол будем к этому возвращаться. Интерфейсы — это устройства, которые вводя водят сообщения из центральных процессоров и модулей памяти. Во мног работках интерфейс представляет собой микросхему или плату, к которой п диняется локальная шина каждого процессора и которая может передавать с процессору и локальной памяти (если таковая есть). Часто внутри инте содержится программируемый процессор со своим собственным ПЗУ, к принадлежит только этому процессору. Обычно интерфейс способен считы записывать информацию в различные мсдули памяти, что позволяет ему п щать блоки данных.
Каналы связи — это каналы, по которым перемещаются биты. Каналы быть электрическими или оптико-волоконными, последовательными (ши 1 бит) или параллельными (шириной более 1 бита). Каждый канал связи х ризуется максимальной пропускной способностью (это максимальное чис тов, которое он способен передавать в секунду). Каналы могут быть симпл ми (передавать биты только в одном направлении), полудуплексными (пере информацию в обоих направлениях, но не одновременно) и дуплексными
давать биты в обоих направлениях одновременно).
Вопросы разработки компьютеров параллельного действия |
|
5 |
Сети межсоединений можно сравнить с улицами города. Улицы похожи на налы связи. Каждая улица может быть с односторонним и двусторонним дви нием, она характеризуется определенной «скоростью передачи данных» (имеет в виду ограничение скорости движения) и имеет определенную ширину (чис рядов). Перекрестки похожи на коммутаторы. На каждом перекрестке прибыва щий пакет (пешеход или машина) выбирает, в какой выходной порт (улицу)
ступить дальше в зависимости от того, каков конечный пункт назначения. При разработке и анализе сети межсоединений важно учитывать несколь
ключевых моментов. Во-первых, это топология (то есть способ расположения ко понентов). Во-вторых, это то, как работает система переключения и как осущес ляется связь между ресурсами. В-третьих, какой алгоритм выбора маршрута пользуется для доставки сообщений в пункт назначения. Ниже мы рассмотр каждый из этих пунктов.
Топология
Топология сети межсоединений определяет, как расположены каналы связи и ко мутаторы (это, например, может быть кольцо или решетка). Топологии мож изображать в виде графов, в которых дуги соответствуют каналам связи, а узлы коммутаторам (рис. 8.4). С каждым узлом в сети (или в соответствующем гра связан определенный ряд каналов связи. Математики называют число канал
степенью узла, инженеры — коэффициентом разветвления. Чем больше степе тем больше вариантов маршрута и тем выше отказоустойчивость. Если кажд узел содержит к дуг и соединение сделано правильно, то можно построить с межсоединений так, чтобы она оставалась полносвязной, даже если к-1 канал повреждены.
Следующее свойство сети межсоединений — это ее диаметр. Если расстояни между двумя узлами мы будем считать число дуг, которые нужно пройти, что попасть из одного узла в другой, то диаметром графа будет расстояние между д мя узлами, которые расположены дальше всех друг от друга. Диаметр сети опре ляет самую большую задержку при передаче пакетов от одного процессора к д гому или от процессора к памяти, поскольку каждая пересылка через канал свя занимает определенное количество времени. Чем меньше диаметр, тем выше п изводительность. Также имеет большое значение среднее расстояние между д мя узлами, поскольку от него зависит среднее время передачи пакета.
Еще одно важное свойство сети межсоединений — это ее пропускная спос ность, то есть количество данных, которое она способна передавать в секун Очень важная характеристика — бисекционная пропускная способность. Что вычислить это число, нужно мысленно разделить сеть межсоединений на две р ные (с точки зрения числа узлов) несвязанные части путем удаления ряда дуг графа. Затем нужно вычислить общую пропускную способность дуг, которые удалили. Существует множество способов разделения сети межсоединений на
Вопросы разработки компьютеров параллельного действия |
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, з показан
5 7 0 Глава 8. Архитектуры компьютеров параллельного действия
рым нужен занятый в данный момент выходной порт, пропадали бы. Прим три метода буферизации. При буферизации на входе один или нескольк ров связываются с каждым входным портом в форме очереди типа FIFO (« вошел, первым вышел»). Если пакет в начале очереди нельзя передать по п занятости нужного выходного порта, этот пакет просто ждет своей очеред
Однако если пакет ожидает, когда освободится выходной порт, то пак щий за ним, тоже не может передаваться, даже если нужный ему порт св Ситуация называется блокировкой начала очереди. Проиллюстрируем си на примере. Представим дорогу из двух рядов. Вереница машин в одном и не может двигаться дальше, поскольку первая машина в этом ряду хочет нуть налево, но не может из-за движения машин другого ряда. Даже если в всем следующим за ней машинам нужно ехать прямо, первая машина в ря пятствует их движению.
Проблему можно устранить с помощью буферизации на выходе. В этой ме буферы связаны с выходными портами. Биты пакета по мере пребыва храняются в буфере, который связан с нужным выходным портом. Поэтом ты, направленные в порт т, не могут блокировать пакеты, направленные в И при буферизации на входе, и при буферизации на выходе с каждым связано определенное количество буферов. Если места недостаточно для ния всех пакетов, то какие-то пакеты придется выбрасывать. Чтобы разреш проблему, можно использовать общую буферизацию, при которой один ный пул динамически распределяется по портам по мере необходимости. такая схема требует более сложного управления, чтобы следить за буфе позволяет одному занятому соединению захватить все буферы, оставив дру единения ни с чем. Кроме того, каждый коммутатор должен вмещать самы шой пакет и даже несколько пакетов максимального размера, а для этого п ется ужесточить требования к памяти и снизить максимальный размер па Хотя метод коммутации с промежуточным хранением гибок и эффективе возникает проблема возрастающей задержки при передаче данных по сети единений. Предположим, что время, необходимое для перемещения пакет ному транзитному участку на рис. 8.6, занимает Т не. Чтобы переместить п процессора 1 в процессор 2, нужно скопировать его 4 раза (в А, в С, в D и в сор 2), и следующее копирование не может начаться, пока не закончится п щее, поэтому задержка по сети составляет 4Т. Чтобы выйти из этой ситуации разработать гибридную сеть межсоединений, объединяющую в себе комм каналов и коммутацию пакетов. Например, каждый пакет можно разде части. Как только первая часть поступила в коммутатор, ее можно сразу на
вследующий коммутатор, даже если оставшиеся части пакета еще не п
вэтот коммутатор.
Вопросы разработки компьютеров параллельного действия |
57 |
превратится в коммутацию с промежуточным хранением. При другом типе марш рутизации, так называемой «wormhole routing» (червоточина), если первый бло не может двигаться дальше, в исходный пункт передается сигнал остановить пе редачу, и пакет может оборваться, будучи растянутым на два и более коммутато ров. Когда необходимые ресурсы становятся доступными, пакет может двигатьс дальше.
Следует отметить, что оба подхода аналогичны конвейерному выполнению ко манд в центральном процессоре. В любой момент времени каждый коммутато выполняет небольшую часть работы, и в результате получается более высокая про изводительность, чем если бы эту же работу выполнял один из коммутаторов.
Алгоритмы выбора маршрута
В любой сети межсоединений с размерностью один и выше можно выбирать, п какому пути передавать пакеты от одного узла к другому. Часто существует мно жество возможных маршрутов. Правило, определяющее, какую последовательност узлов должен пройти пакет при движении от исходного пункта к пункту назначе ния,называетсяалгоритмомвыборамаршрута.
Хорошие алгоритмы выбора маршрута необходимы, поскольку часто свобод ными оказываются несколько путей. Хороший алгоритм поможет равномерно рас пределить нагрузку по каналам связи, чтобы полностью использовать имеющую ся в наличии пропускную способность. Кроме того, алгоритм выбора маршрут помогает избегать взаимоблокировки в сети межсоединений. Взаимоблокировк возникает в том случае, ее та при одновременной передаче нескольких пакетов ре сурсы затребованы таким образом, что ни один из пакетов не может продвигатьс дальше и все они блокируются навечно.
Пример тупиковой ситуации в сети с коммутацией каналов приведен нарис. 8.7 Тупиковая ситуация может возникать и в сети с пакетной коммутацией, но е легче представить графически в сети с коммутацией каналов. Здесь каждый про цессор пытается послать пакет процессору, находящемуся напротив него по диа гонали. Каждый из них смог зарезервировать входной и выходной порты своег локального коммутатора, а также один входной порт следующего коммутатора, н он уже не может получить необходимый выходной порт на втором коммутаторе поэтому он просто ждет, пока не освободится этот порт. Если все четыре процессо ра начинают этот процесс одновременно, то все они блокируются и сеть зависает
Алгоритмы выбора маршрута можно разделить на две категории: маршрутиза ция от источника и распределенная маршрутизация. При маршрутизации от ис точника источник определяет весь путь по сети заранее. Этот путь выражаетс списком из номеров портов, которые нужно будет использовать в каждом комму таторе по пути к пункту назначения. Если путь проходит через к коммутаторов, т первые к байтов в каждом пакете будут содержать к номеров выходных портов
