Одним из худших свойств перекрестной коммутации является то, что число узлов растет как п2. Для средних по размеру систем перекрестная коммутация
является хорошим решением, и далее в этой главе мы рассмотрим одно из таких решений — NUMA-мультипроцессор Sun Fire Е25К. Однако для 1000 процессоров и 1000 модулей памяти понадобится миллион узлов, что неприемлемо. Необходимо нечто совершенно иное.
UMA-мультипроцессоры с многоступенчатой коммутацией
В основе этого «совершенно иного» лежит небольшой коммутатор 2x2 (рис. 8.24, а) с двумя входами и двумя выходами. Сообщения, приходящие на любую из входных линий, могут переключаться на любую выходную линию. В нашем примере сообщения будут содержать до четырех частей (рис. 8.24, б). Поле модуля показывает, какой модуль памяти запрашивается. Поле адреса определяет адрес в этом модуле памяти. В поле кода операции указывается одна из доступных операций, например, READ или WRITE. Наконец, дополнительное поле значения может содержать операнд, например, 32-разрядное слово, которое нужно записать при выполнении операции WRITE. Коммутатор проверяет поле модуля и с его помощью определяет, через какую выходную линию нужно отправить сообщение: через X или через Y.
Рис. 8.24. Коммутатор 2x2 (а); формат сообщения (б)
Наши коммутаторы 2x2 можно компоновать различными способами и получать сети с многоступенчатой коммутацией. Один из возможных вариантов — сеть omega (рис. 8.25). Здесь 8 процессоров соединены с 8 модулями памяти через 12 коммутаторов. Для п процессоров и п модулей памяти понадобится log2n ступеней и п/2 коммутаторов на каждую ступень, то есть, всего (n/2)log2n коммутаторов, что намного меньше, чем п2 коммутационных узлов при перекрестной коммутации, особенно для больших значений п.
Схему разводки проводов сети omega часто называют полной перетасовкой (perfect shuffle), поскольку смешение сигналов на каждой ступени напоминает тасование колоды карт. Чтобы понять, как работает сеть omega, предположим, что процессору 011 нужно считать слово из модуля памяти 110. Процессор посылает сообщение READ, чтобы переключить коммутатор 1D, который содержит 110 в поле модуля. Коммутатор берет первый (то есть крайний левый) бит от 110 и по нему узнает направление (0 указывает на верхний выход, 1 — на нижний). Поскольку в данном случае этот бит равен 1, сообщение отправляется через нижний выход к коммутатору 2D.
Все коммутаторы второй ступени, включая 2D, для определения направления используют второй бит. В данном случае он равен 1, поэтому сообщение отправляется через нижний выход к коммутатору 3D, который проверяет третий бит. Он равен 0, следовательно, сообщение проходит через верхний выход и прибы вает в модуль памяти 110, чего мы и добивались. Путь, пройденный сообщением, обозначен на рис. 8.25 буквой а.
По мере прохождения через сеть сообщение поочередно перестает нуждаться во всех битах номера модуля, начиная с самого левого. Их можно использовать для записи номеров входных линий, чтобы было известно, по какому пути посылать ответ. Для пути а входные линии — это 0 (верхний вход в ID), 1 (нижний вход в 2D) и 1 (нижний вход в 3D) соответственно. Таким образом, при отправке ответа тоже используется последовательность 011, только прочтенная справа налево.