Коммутационные средства матричных СБИС-мультипроцессоров

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

КС ММП представляет собой матрицу идентичных коммутационных устройств, каждое из которых соединено со своими ближайшими соседями со­гласно топологической структуре сети (см., например, рис. 1.3). Коммутационные устройства (КУ), применяемые в современных мультипроцессорах, чаще всего используют режим пакетной коммутации (packet switching) [69, 73, 78, 110, 114], реже - схемную коммутацию (circuit switching), отдельно либо в сочетании с па­кетной коммутацией [70, 81, 83, 101-103]. Они во многом подобны ATM- коммутаторам вычислительных сетей, абонентских систем и мультикомпьютеров, реализующим принцип wormhole-маршрутизации [34-37, 67, 68, 76, 80, 107, 111]. Основным отличием КУ ММП является то, что пакеты имеют значительно мень­шую длину (длина ATM-пакета, согласно стандарту, составляет 64 байта [107]) и разбиваются на фрагменты одинаковой разрядности, которые передаются по ши­нам в параллельном коде за один-два такта. Указанные фрагменты (называемые

флитами, flit) могут группироваться (режим групповой передачи) либо переда­ваться независимо друг от друга (режим независимой передачи) [42, 74, 84, 116]. При независимой передаче разрядность флитов получается несколько больше, чем при групповой передаче, поскольку адрес приемника содержится в каждом флите, однако процедуры маршрутизации и коммутации значительно проще, так как не требуется поддержка механизма виртуальных каналов wormhole- маршрутизации, что приводит к более простым схемотехническим решениям [24, 29, 33, 42, 56].

КУ ММП включает множество входов (входных портов), множество выхо­дов (выходных портов) и состоит из коммутирующей и буферизующей.

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

В устройствах с входным расположением буферов (см. рис. 1.4,α) пакеты со входов первоначально поступают в соответствующие FIFO-буферы и только за­тем коммутируются на требуемые выходы [27, 32, 95]. Такие КУ не предъявляют жестких требований к быстродействию коммутирующей части и, как правило, об­ладают низкой аппаратной сложностью, что позволяет использовать их при боль­шом числе входов/выходов. Однако доказано [94], что подобные устройства (без модификации дисциплин обслуживания буферов) практически не могут обеспе­чить пропускную способность выше 0.64 из-за возникновения блокировок паке­тов в головных регистрах буферов (Head of line blocking = HOL blocking). Их

асимптотическая пропускная способность составляет около 0.586. Были предпри­няты многочисленные попытки уменьшить влияние блокировки путем предвари­тельного анализа пакетов, находящихся в буферах [71, 90, 95], что позволило не­сколько увеличить пропускную способность КУ, однако принципиально пробле­му не решило.

В коммутационных устройствах с выходным размещением буферов (см. рис. 1.4,6) пакеты сразу коммутируются на требуемые выходы и затем сохраня­ются в выходных буферах перед выдачей, что исключает блокировки пакетов, свойственные рассмотренной выше архитектуре КУ [18, 39, 46, 55, 69, 94, 96].

КУ с центральным расположением коммутирующей части (см. рис. 1.4,β) и КУ с общей буферной памятью (см. рис. 1.4,г) является компромиссными вариан­тами организации, сочетающими свойства ранее рассмотренных структур. Допол­нительная выходная буферизация в устройствах с центральным переключателем (рис. 1.4,β) позволяет ослабить эффект блокировки (HOL blocking), в особенности при большом числе входов/выходов. Кроме того, в таких КУ не требуется повы­шенная скорость работы переключателя, что упрощает его схемотехническую ре­ализацию. Подобная организация лежит в основе коммутаторов с буферизован­ным переключателем [38, 40, 41, 44, 99, 109, 117], подробно рассматриваемых да­лее. Единственным их отличием является то, что буферы непосредственно инте­грированы в переключатель (не переставая при этом оставаться выходными буфе­рами).

Рисунок 1. 4. Варианты взаимного расположения коммутирующей и буферизующей частей коммутационного устройства

Организация с общей буферной памятью (рис. 1.4,г) используется в низко­скоростных устройствах коммутации [76, 80]. Общая память в них является до­ступной как для входных линий, так и для выходных. Каждый вход и каждый вы­ход получают доступ к общей памяти через общую шину. Логически память рас­пределена между множеством выходных очередей. В один момент времени каж­дый вход может записать пакет в соответствующую логическую выходную оче­

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

Одной из весьма успешных попыток объединения преимуществ устройств с входными и выходными буферами является концепция коммутатора с виртуаль­ными выходными очередями (Virtual Output Queue - VOQ), впервые сформулиро­ванная в работе [120]. Формально VOQ-устройства следует отнести к устройствам с входным расположением буферов (см. рис. 1.4,α), однако их буферизующая часть имеет более сложную организацию (рис. 1.5). Каждому входному порту VOQ-устройства соответствует nпростых FIFO-буферов Qij,соединенных парал­лельно, каждый из которых, в свою очередь, отображен на определенный выход­ной порт. Очередной пакет, поступая на i-й вход КУ, проходит через демульти­плексор DX (выполняющий функции маршрутизатора) и заносится в FIFO-буфер Qij,соответствующий j-му выходному порту устройства, на который необходимо выдать пакет согласно реализуемому алгоритму маршрутизации. В результате в буфере Qijоказываются только те пакеты, которым необходима выдача на j-й вы­ход, что гарантирует отсутствие проблемы блокировки HOL blocking. Дальнейшая выдача пакетов из буферов осуществляется под управлением центрального пла­нировщика (диспетчера) [62], который назначает определенную очередность вы­дачи пакетов, поступивших с разных входов, на заданный выход (в схеме на рис. 1.5 планировщик условно представлен набором мультиплексоров MX).

Рисунок 1.5.

Концепция VOQ-коммутатора с теми или иными вариациями активно ис­пользуется в различных устройствах уже в течение трех десятилетий [66, 72, 75,

77, 79, 93, 105, 106, 108], позволяя достичь максимальной пропускной способно­сти КУ (до 1) при различных вариантах распределения входящего трафика. Ос­новным недостатком VOQ-устройства является необходимость работы коммути­рующей части на удвоенной скорости (минимально необходимое ускорение рабо­ты коммутирующей части VOQ-устройства на сегодня составляет 2 -¹ [89]). Это n

приводит к более сложным схемотехническим решениям КУ. Еще одним недо­статком подобных устройств является повышенная аппаратная сложность, асимп­тотическая оценка которой составляет примерно куб от числа входов/выходов n, что затрудняет их применение в матричных мультипроцессорах. Высокая аппа­ратная сложность VOQ-устройств обусловлена, с одной стороны, наличием nбу­феров длины Lв каждом из nвходных портов, а с другой стороны, - сложной коммутирующей частью с центральным планировщиком, рассчитанной на n² входов и nвыходов.

Альтернативой VOQ-коммутаторам являются коммутационные устройства с буферизованным матричным переключателем [38, 40, 41, 44, 99, 109, 117]. Осо­бый интерес представляют КУ, использующие простые FIFO-буферы на входах, и буферизованный переключатель (матрицу буферов) на выходе [99, 109], облада­ющие на порядок меньшей аппаратной сложностью по сравнению с VOQ- коммутаторами. Формально такие устройства вписываются в рамки организации, представленной на рис. 1.4,β. Известны и другие подходы к построению КУ, не использующие централизованную диспетчеризацию пакетов, например, [88].

Структурная организация КУ с буферизованным матричным переключате­лем в обобщенном виде приведена на рис. 1.6. Буферизующая часть устройства представлена множеством простых FIFO-буферов, коммутирующая часть - мат­ричный переключатель, в точках пересечения входных и выходных шин которого размещены дополнительные буферы.

тельно в порядке, определяемом распределенным диспетчером. Выдача пакетов непосредственно в порядке расположения буферов является простейшим решени­ем, однако приводит к дисбалансу длины входных FIFO-буферов. В связи с этим в известных схемах КУ с буферизованным переключателем [99, 109] диспетчериза­ция пакетов осуществляется равновероятно (uniform) или согласно круговой дис­циплине (round robin).

Рисунок 1.6. Структурная организация коммутационного устройства с буферизованным матричным переключателем

КУ с буферизованным матричным переключателем обладают значительно меньшей аппаратной сложностью, чем VOQ-коммутаторы; ее асимптотика пред­ставляет собой квадратичную функцию от числа входов/выходов nпротив куби­ческой зависимости, характерной для VOQ-устройств. Также они имеют простую коммутирующую часть, работающую с той же скоростью, что и внешние каналы КУ. В то же время, VOQ-устройства обеспечивают более высокую пропускную способность и меньшую задержку прохождения пакетов при наиболее распро­страненных на практике значениях n(до нескольких десятков).

Скоростные характеристики коммутационных устройств зависят не только от расположения и организации буферизующей части, но и от способа построения коммутирующей части. Матричный переключатель (см. рис. 1.6) способен обес­печить наименьшую задержку прохождения пакетов на выходы КУ, поскольку каждый пакет всегда без блокировки проходит одну точку пересечения шин пере­ключателя, однако его структурная сложность при большом числе вхо- дов/выходов может оказаться неприемлемо высокой. В связи с этим при построе­нии КУ довольно часто используются одно- и многокаскадные динамические коммутаторы, в частности, неблокирующие коммутаторы [51, 78, 118, 128], полу­чившие развитие из техники телефонной связи. Они способны обеспечить мень­шую аппаратную сложность коммутационных средств за счет некоторого увели­чения задержки прохождения пакетов. Наиболее ощутимый эффект от их приме­нения начинает проявляться при большом числе входов/выходов. Так, например, сложность КУ на 100 входов/выходов при использовании матричного переключа­теля составляет 10000 элементарных коммутаторов (точек пересечения шин); в то же время, трехъярусная неблокирующая сеть Клоза на такое же число вхо- дов/выходов содержит всего 5700 элементарных коммутаторов.

Всё сказанное выше позволяет классифицировать методы (и устройства) коммутации пакетов, используемые в матричных СБИС-мультипроцессорах, по пяти ключевым признакам (см. рис. 1.7): 1) по расположению буферов относи­тельно коммутирующей части; 2) по способу организации буферов; 3) по способу организации коммутирующей части; 4) по наличию дополнительных буферов в коммутирующей части; 5) по способу передачи пакетов. Среди представленных в литературе методов и технических решений КУ можно найти самые разные соче­тания указанных признаков классификации, некоторые из которых обсуждались ранее.

Как уже отмечалось выше, наряду с режимом коммутации пакетов, СБИС ММП нередко используют режим схемной коммутации [83]. При схемной комму­тации перед обменом данными в коммуникационной сети создается временный канал, соединяющий источник с приемником (приемниками). Далее по этому ка­

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

Рисунок 1.7. Классификация методов (и устройств) коммутации пакетов, используемых в матричных СБИС-мультипроцессорах

Одной из последних тенденций развития матричных СБИС- мультипроцессоров является переход к гибридной коммутации [70, 81, 102, 103]. Такой подход предполагает применение схемной коммутации при передаче боль­ших блоков данных и использование пакетной коммутации при обмене неболь­шими порциями данных, короткими запросами, управляющими командами и т.п. Целесообразность такого сочетания режимов коммутации объясняется тем, что трафик, порождаемый типовой рабочей нагрузкой современных СБИС- мультипроцессоров, в основном состоит из коротких сообщений запроса выборки

и длинных ответных сообщений, несущих один или несколько блоков данных из удаленного модуля кэш-памяти. Подобные взаимодействия возникают тогда, ко­гда процессор не находит нужных данных в локальной кэш-памяти (т.е. имеет ме­сто ситуация локального «кэш-промаха»). Известны методы управления КУ ММП, позволяющие автоматически выбирать наиболее эффективный режим коммутации с учетом типа межпроцессорных сообщений [103].

В работе [102] рассмотрен один из механизмов организации работы КУ с гибридной коммутацией в матричных СБИС ММП, обозначенный аббревиатурой CIMA (Circuit-switched Inter-tile Memory Access mechanism = схемный механизм межпроцессорного доступа к памяти). Ключевые элементы устройства, реализу­ющего этот механизм, схематично представлены на рис. 1.8.

Все элементы, которые содержатся в данном устройстве, организационно относятся к двум независимым сетям: сети обмена данными (data network) и управляющей сети (control network). Сеть обмена данными обеспечивает передачу запросов выборки данных из удаленной памяти и передачу блоков данных про­цессорам. Ее элементами являются пять портов для подключения к соседним уз­лам и локальному процессору, буферы виртуальных каналов (ВК0, ..., ВКи), блок вычисления маршрутов, блок резервирования виртуальных каналов, блок арбит­ража, а также неблокирующий переключатель. Сеть реализует метод cut-through- маршрутизации с тремя виртуальными каналами на порт для обеспечения отсут­ствия блокировок (deadlock freedom). Управляющая сеть является более простой. Она не содержит буферов и виртуальных каналов и используется для настройки соединений в сети обмена данными. К управляющей сети относятся блок резер­вирования (логических) каналов, блок вычисления маршрутов, таблица (логиче­ских) каналов и неблокирующий переключатель. Особенностью организации управляющей сети, предложенной в [102], является передача короткого настроеч­ного пакета в направлении источника запроса выборки перед отправкой ему большого блока данных, что позволяет заранее настроить канал передачи.

Рисунок 1.8. Основные элементы КУ с гибридной коммутацией

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