BC/NW 2006, №1 (8): 3.1

 

КОММУТАТОРЫ  ВЫЧИСЛИТЕЛЬНЫХ  СИСТЕМ 

 

 

А.А.Дерюгин

 

(Москва, Московский энергетический институт (технический университет), Россия)

 

 

 

ВВЕДЕНИЕ

 

Для реализации параллельных вычислений в зависимости от класса решаемых задач применяются многопроцессорные  и  многомашинные вычислительные системы [1, 2]. Основными средствами, обеспечивающими взаимодействие между элементами структуры в ВС, являются коммутаторы. Коммутатор может быть реализован как единое целое или в виде нескольких функционально законченных частей – коммутационных модулей. Коммутаторы многопроцессорных  и  многомашинных вычислительных систем,  реализуются по-разному.

 

1. КОММУТАТОРЫ МНОГОПРОЦЕССОРНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ

 

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

 

n₁ = n_A + n_D + n_C,

 

где n_A, n_D, n_C – число проводников для передачи сигналов адреса, данных и управления. При этом значение  n_D либо равно разрядности процессора, либо превосходит её в 2 или 4 раза. Часто сигналы адреса, данных и часть сигналов управления передаются по одним и тем же проводникам (n_AD), но в разное время. В этом случае

n₁ ≈ n_AD + n_C .

 

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

 

1.1.  Матричный коммутатор

 

В состав МПВС с матричным коммутатором (рисунок 1) входят N процессорных модулей PM (или процессоров) и М модулей памяти ММ, причем  М≤ N.  Точками в коммутаторе  SW условно показано наличие связи процессорных модулей с модулями памяти.

 

 

 

 

 

 

 

 

 

 

 

Рисунок 1 – МПВС с матричным коммутатором

 

Такой коммутатор можно рассматривать как М коммутационных модулей  SM, связанных с соответствующими модулями памяти. А такая связка представляет собой ни что иное, как многовходовую память (N-входовую). Основой коммутационного модуля SM являются ключевые элементы для однонаправленной (n_A, n_C) или двунаправленной (n_D) передачи сигналов (рисунок 2).

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Рисунок 2 – Ключевые элементы для однонаправленной (а) и двунаправленной (б) передачи сигналов

 

Каждый коммутационный модуль SM помимо ключевых элементов содержит устройство управления, выполняющее следующие функции:

- определение факта обращения процессорного модуля именно к данному модулю памяти (по коду части разрядов n_A), т.е. маршрут обращения,

- арбитраж:  к данному ММ одновременно могут обращаться несколько процессорных модулей,

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

- выработку управляющих сигналов для реализации передачи кодов A, D, C.

Затраты оборудования на реализацию матричного коммутатора SW пропорциональны N×M.

Подключение внешней памяти ЕМ и устройств ввода/вывода I/O производится к одной или нескольким шинам PM. При этом на входах ЕМ и I/O должны присутствовать коммутационные модули и устройства сопряжения (интерфейсные устройства).

 

1.2.  Многоступенчатый коммутатор  N×M

 

Для экономии оборудования  вместо матричного коммутатора может применяться многоступенчатый коммутатор (обычно для  N ≥ 8 и M ≥ 4). Такой коммутатор строится из 2-входовых (2×2, 2×1) или 4-входовых (4×1, 4×2, 4×4) коммутационных модулей (КМ). Затраты оборудования на реализацию многоступенчатого коммутатора SW в этом случае пропорциональны   2M×log₂N.

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

На рисунке 3 в качестве примера приведена схема двухступенчатого коммутатора 16×4. Устройство управления распределено по коммутационным модулям  (на рисунке не показано).

Экономия оборудования, получаемая при использовании многоступенчатого коммутатора, приводит к увеличению времени передачи сигналов через коммутатор, а также к конфликтам на самом коммутаторе. Выходы КМ первой ступени SM1,…SM4 являются общим ресурсом, на котором и могут быть конфликты, т.к. через каждый из этих КМ одновременно может пройти только одно обращение из 4-х, даже если обращения происходят к разным модулям памяти. Для борьбы с этими конфликтами разработано много методов создания обходных путей, однако все известные методы связаны с очень большими затратами оборудования, т.к. шина широкая.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Рисунок 3 – Двухступенчатый коммутатор 16×4

 

Отметим, что матричный коммутатор можно рассматривать как частный случай многоступенчатого коммутатора, в котором всего одна ступень, состоящая из М коммутационных модулей N×1.

 

1.3. Общая шина

 

 Рассмотрим частный случай МПВС с матричным коммутатором, в которой один модуль памяти (см. рисунок 1). Предположим, что коммутатор (в данном случае это один КМ),  включая его схему управления, разрезан на N  частей и эти части введены в состав соответствующих процессорных модулей. Соединение выводов PM и модуля памяти образуют общую шину. Отметим, что именно так сделаны процессоры Pentium 2 (3 и 4) фирмы INTEL, допускающие построение 4-процессорных МПВС.

 В состав МПВС с общей шиной (рисунок 4) входят N процессорных модулей PM и один модуль памяти ММ, а также ЕМ и I/O. Внешние устройства могут подключаться через интерфейсные устройства непосредственно к общей (системной) шине В1. Может быть применено также стандартное подключение внешних устройств с помощью шины PCI и моста между системной (общей) шиной и шиной PCI (Peripheral Component Interconnect).

Число процессоров в такой МПВС ограничено двумя факторами:

- пропускной способностью памяти (или общей шины),

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

 

 

 

 

 

 

 

Рисунок 4 – МПВС с общей шиной

 

Особенностью всех МПВС является то, что время обращения любого процессора к памяти одинаковое. В зарубежной литературе такие МПВС называют UMA (Uniform Memory Access) – МПВС с однородным доступом к памяти, а саму память общей. Работа МПВС характеризуется также аббревиатурой  SMP (Symmetrical Multiprocessor Processing) – симметричная многопроцессорная обработка, которая достигается за счет циклического изменения приоритетов процессоров.

 

2.  КОММУТАТОРЫ  МНОГОМАШИННЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ

 

В многомашинных вычислительных системах (ММВС) элементами структуры являются ЭВМ или МПВС с общей шиной, т.е. устройства, содержащие один или несколько процессоров и один модуль оперативной  памяти. Введем общий термин для такого элемента структуры ММВС – вычислительный модуль (ВМ). На схемах вычислительный модуль будем обозначать COM (COmputing Module). Устройства внешней памяти EM и ввода/вывода I/O могут  входить в состав ВМ или являться самостоятельными элементами структуры ММВС.

Основной особенностью ММВС является то, что связи между элементами структуры ослабленные (шина В2). Число линий связи обычно равно 8, 16 или 32 (не считая вспомогательных линий управления). Эти связи реализуются с помощью коммутатора SW (рисунок 5).

 

 

 

 

 

 

 

 

 

Рисунок 5 – Многомашинная ВС

 

Коммутатор конструктивно обычно делится на N связанных друг с другом коммутационных модулей (КМ) с L выводами (входами/выходами) каждый (L – число связей данного ВМ с другими  ВМ).

Средства связи между ВМ (рисунок 6, а) обычно представляют состоящими из двух частей – адаптера, предназначенного для согласования уровней сигналов и параметров шин (частоты f и ширины n), соответствующих сильной связи внутри ВМ (f₁, n₁ в точке В1) и ослабленной связи на выходах коммутатора (f₂, n₂ в точке В2), и коммутационного модуля SM. Основу адаптера составляет буферная память BFM, организованная по принципу FIFO. Емкость BFM должна быть не менее объема  передаваемого за один сеанс пакета данных (сообщения). Устройство управления CON  на рисунке 6, а для простоты показано как единый блок, общий для адаптера и КМ.

Коммутационный модуль может быть конструктивно  размещен вне ВМ либо в составе ВМ (рисунок 6, б, в). 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Рисунок 6 – Адаптер и  коммутационный модуль (а), упрощенное изображение ВМ  в предположении, что в ВМ встроен только

адаптер (в) или адаптер и  КМ (г)

 

Точка В1 – точка подключения SM к общей шине COM (см. рисунок 4). Общей шиной в ВМ может быть либо системная шина, либо шина PCI.

В простейших ММВС коммутатор может отсутствовать, а  в качестве адаптеров могут быть использованы стандартные порты ЭВМ: LPT-порт или порт SCSI. В этом случае взаимодействие между ЭВМ реализуется как обращение одной ЭВМ к другой как к внешнему устройству. Многообразие структур ММВС определяется тем, как сделаны коммутационные модули SM и узлы ключевых элементов SD, а также тем, как  соединены выводы L одного ВМ с выводами L других ВМ.

Прежде всего отметим, что связи между вычислительными модулями могут быть двух типов: в виде шин и в виде линков.

В случае шинных связей сигналы между ВМ передаются по одним и тем же линиям (проводникам) в двух направлениях (полудуплексные связи). Многомашинные ВС с такими связями рассмотрены в подразделах 2.1 и 2.2.

В случае линковых связей сигналы между ВМ передаются в одном направлении по одним линиям (линкам), а в другом направлении по другим линиям (симплексные связи). Многомашинные ВС с такими связями рассмотрены в подразделах 2.3, 2.4 и 2.5.

Во всех структурах ММВС оперативная память распределена по ВМ, причем время обращения процессора к оперативной памяти «своего» ВМ существенно меньше, чем время обращения к памяти «чужого» ВМ. В зарубежной литературе такие структуры ММВС называют NUMA (Non-Uniform Memory Access) – системы с неоднородным доступом к памяти, а саму память – распределенной  (distributed memory). Поскольку число ВМ в ММВС обычно велико (≥32), то работа ММВС характеризуется также аббревиатурой  MPP (Massively Parallel Processing) – ВС с массовой параллельной обработкой.

Отметим, что объединение отдельных ВМ в ММВС предполагает образование единого адресного пространства. Адреса ячеек памяти в ММВС состоят из номера ВМ (старшие разряды адреса) и адреса  ячейки памяти в ВМ (младшие разряды адреса).

Здесь уместно также отметить, что одним из основных вопросов, решаемых при проектировании ММВС, является её наращивание, т.е. увеличение числа ВМ в ММВС. Фактически речь идет о максимальном числе ВМ (N), которое может входить в состав проектируемой ММВС. Значение N определяется числом двоичных разрядов (m), которое отводится для указания номера (адреса) ВМ. Таким образом,  N = 2^m.

 

2.1.         Многомашинные вычислительные системы со связями между вычислительными модулями в виде шин

 

Многомашинная ВС со связями в виде шин показана на рисунке 7, а. Число шин равно L. Предполагается, что коммутационные модули входят в состав вычислительных модулей COM.

Узлы ключевых элементов выполнены по схеме, приведенной на рисунке 7, б. Здесь SC1…SCL – ключевые элементы для двунаправленной передачи пакетов, включающих сигналы A, D и C. Точкой В2 отмечено соединение узла ключевых элементов с адаптером ВМ, а точками 1, 2, …, L – соединения с соответствующими общими шинами. Затраты оборудования на выполнение всего коммутатора ММВС пропорциональны N×L. 

Чем больше L, тем больше связей между СОМ может быть реализовано одновременно. Наибольшее значение L равно N/2. В такой ММВС конфликтные ситуации отсутствуют, однако затраты оборудования очень велики.

 

 

 

 

 

 

 

 

 

Рисунок 7 – Схема многошинной ММВС (а) и узел ключевых элементов (б)

 

Число конфликтов считается приемлемым, если число шин выбирается из условия: одна шина не более, чем на 8 ВМ.

 Многошинные ММВС имеют очевидный недостаток – ограниченное число ВМ  (≤ 8L).

Частный случай многошинной ММВС – одношинная ММВС (L=1), в которой между ВМ в каждый временной интервал может быть реализована только одна связь.

 

2.2 Многомашинные вычислительные системы с иерархическими  связями  между  вычислительными  модулями

 

Такие ММВС часто называют ММВС с коммутатором иерархического типа. Применение коммутатора иерархического типа позволяет получить наиболее экономичную по затратам оборудования на коммутатор и удобно наращиваемую структуру ММВС.

Рассмотрим в качестве примера ММВС с иерархическим коммутатором и связями трех типов, которые назовем сильными, ослабленными и слабыми соответственно.

Предположим, что основу ММВС (рисунок 8) составляет вычислительный модуль, который представляет собой 4-процессорную МПВС с общей (системной) шиной (см. рисунок 4). Будем считать, что связи между процессорами и модулем памяти сильные, ширина системной шины – n₁ = 64 разряда, частота работы – f₁ = 400 МГц.

С внешним миром такой ВМ (СOМ1 на рисунке 8) связывается с помощью адаптера и коммутационного модуля  SM1, сделанных по схеме, показанной на рисунке 6, а при L = 1. Связи на выходе ослабленные, частота работы шины f₂ = 100 МГц, ширина шины n₂ = 16 разрядов. К этой шине подключены 8 таких ВМ и коммутационный модуль  SM2, образуя подсистему второго уровня иерархии СОМ2. На выходе SM2 связи тоже ослабленные – f₃ = 20 МГц, ширина шины n₃ = 16 разрядов. К этой шине подключены 16 таких подсистем, образуя систему в целом.

Коммутационный модуль SM2 делается по схеме, аналогичной схеме коммутационного модуля  SM1, и должен работать в двух режимах: на частоте 100 МГц (n₂=16) и на частоте 20 МГц (n₃=16).

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Рисунок 8 – ММВС иерархического типа

 

Таким образом, ММВС в целом состоит из 4×8×16 = 512 процессоров, 8×16 = 128 модулей  памяти и имеет 2 уровня связей (64 и 16  разрядов).

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

Для адресации ячеек памяти в рассмотренной выше ММВС код адреса должен содержать 7 разрядов для указания номера ВМ (рисунок 9): 3 разряда для указания номера МПВС первого уровня (СОМ1) и 4 разряда для указания номера ММВС второго уровня (СОМ2).

 

 

 

 

 

 

Рисунок 9  – Адресация ячеек памяти в ММВС иерархического типа

 

Если 7-разрядный код адреса, сформированный каким-либо процессором, совпадает с 7-разрядным номером данного СОМ1, то это обращение производится к собственному модулю памяти. Если совпадают коды только 4-х старших разрядов, то обращение производится к модулю памяти другого СОМ1, но расположенного в том же СОМ2. Если же не совпадают коды в старшей 4-разрядной группе, то обращение идет к другому  СОМ2, а в этом СОМ2  – к СОМ1, номер которого указан в младшей тройке разрядов. Описанный анализ кода адреса и определение маршрута обращения  выполняются схемами управления коммутационных модулей  SM (по принципу самомаршрутизации).

В рассмотренном примере на каждом уровне иерархии применяются одношинные структуры. Для увеличения пропускной способности и наращивания системы можно на каждом уровне увеличивать число ВМ и соответственно число связывающих их шин, используя коммутационные модули с L = 2, 3 или 4.

Малые затраты оборудования в ММВС иерархического типа обусловлены как небольшим числом коммутационных модулей  на каждом из уровней иерархии (при L=1: SM1 – 8×16, SM2 – 16), так и простотой самих коммутационных модулей.

Кроме того, в ММВС иерархического типа имеются следующие достоинства:

- возможность подключения ЕМ и I/O к шинам на любом уровне иерархии,

- возможность реализации иерархической структуры управления. Можно предположить, что  в ММВС иерархического типа (рисунок 8) вместо SM установлены управляющие ЭВМ, реализующие не только функции управления коммутатором, но и функции управления системой: определение готовых к выполнению процессов, их установку на свободные процессоры, тестирование работы ММВС и т.п. Однако рассмотрение вопросов управления ММВС выходит за рамки настоящей работы.

 

2.3. Многомашинные вычислительные системы с регулярными связями между вычислительными модулями

 

Известны следующие варианты ММВС с регулярными связями между ВМ:  кольцевая (одномерная),  матричная (двухмерная),  многомерная (например, трехмерная),  гиперкуб  и  др.  На рисунке 10 в качестве примера приведена структурная схема кольцевой ММВС, в которой   8  ВМ.

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

Общий коммутатор ММВС реализуется в виде совокупности КМ, число которых равно числу ВМ. Предполагается, что адаптеры и коммутационные модули встроены в ВМ. Таким образом, на рисунке 10, а   СОМ – это совокупность ВМ и КМ, а каждая линия связи – это пара линков.

 

 

 

 

 

 

 

 

 

Рисунок 10 – Структурная схема кольцевой ММВС (а)

и граф связей между ВМ при N=8 (б)

 

В КМ с линковыми связями число линий связи удваивается, и соответственно, удваивается пропускная способность КМ. Затраты на ключевые элементы не изменяются: число ключевых элементов удваивается, но сами ключевые элементы упрощаются, поскольку они являются однонаправленными.

Возможны два варианта передачи пакета:

- с буферизацией пакета на каждом шаге передачи. Буферизация производится  в буферных памятях, которые организуются по принципу FIFO и устанавливаются на выходах линков. Возможность передачи пакета от предыдущего КМ к следующему является то, что в предыдущем КМ буферная память «не пуста», а в следующем – «пуста»;

- без буферизации. В этом случае буферные памяти отсутствуют. Перед передачей пакета делается подготовка всего тракта передачи путем перевода в состояние «замкнуто» всех ключевых элементов SC, участвующих в передаче пакета. Признаками возможности подготовки канала передачи является то, что  ключевые элементы SC предыдущего КМ «замкнуты», а следующего – «разомкнуты».

Типичная схема коммутационного модуля приведена на рисунке 11.

Коммутационным модулем обеспечиваются не только связи ВМ с каждым из двух входных и выходных линков (L = 2), но и транзитные связи между линками.

Верхняя часть рисунка 11  – это  адаптер КМ, а нижняя – это  узел ключевых элементов SD. В состав SD  помимо SC включены две буферные памяти (FIFO) – BFMT1   и  BFMT2   для транзитной передачи пакетов с буферизацией. Емкость каждой из буферных памятей должна быть не меньше, чем объем наибольшего из передаваемых пакетов. В случае передачи без буферизации буферные памяти отсутствуют.

Для лучшего понимания работы коммутационного модуля входы и выходы всех его узлов на рисунке 11 помечены стрелками.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Рисунок 11 – Адаптер и коммутационный модуль для  L=2

с транзитными связями (SC5 и SC6)

 

Работа коммутационных модулей это передача информационного пакета от ВМ-источника (инициатора) к ВМ-приемнику (целевому устройству) и иногда обратно.

В пакете обычно содержится следующая информация:

- код маршрута передачи пакета;

- адрес ВМ-источника;

- адрес ВМ приемника;

- начальный адрес данных в оперативной памяти ВМ-приемника;

- команда (запись или считывание);

- объем данных в пакете (типичные варианты 0, 16, 32, …, 256 байт);

- собственно данные (обычно это строка кэш-памяти);

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

Код маршрута определяется разностью адресов ВМ-приемника и ВМ-источника и отражает направление передачи и расстояние (кратчайшее) между этими модулями.

В режиме записи (send) сформированный пакет должен быть передан от ВМ-источника к ВМ-приемника по вычисленному маршруту. В процессе транзитной передачи пакета от одного ВМ к следующему значение кода маршрута на каждом шаге передачи уменьшается на 1. Если этот код >0, то пакет записывается в транзитную буферную память  BFMT1 (или BFMT2)  через  коммутационные элементы  (SC5 или SC6), если эта память свободна. В противном случае передача пакета приостанавливается до освобождения буферной памяти. Если код маршрута равен 0, то пакет записывается в BFMIN  ВМ-приемника через коммутационные элементы  SC2 (или SC3) и далее в оперативную память ВМ-приемника. Управление этой записью производится CON  приемника, содержащего блок, аналогичный контроллеру прямого доступа к памяти. Приоритет этой передачи наивысший.

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

В режиме считывания (receive) пакет должен быть считан из оперативной памяти ВМ-приемника и передан в память ВМ-источника. Вначале от ВМ-источника к ВМ-приемника передается пакет с командой «считать» и с нулевыми данными так же, как и в режиме записи. Затем под управлением CON  ВМ-приемника данные считываются из оперативной памяти в BFMOUT (также в режиме прямого доступа к памяти с наивысшим приоритетом), формируется пакет и передается из ВМ-приемника  в BFMIN ВМ-источника и оттуда в кэш-память ВМ-источника вместе с тэгом, на котором отражается тот факт, что эти данные приняты из ВМ-приемника.

Таким образом, время выполнения считывания почти в два раза больше времени выполнения записи.

Далее приведены схемы других ММВС с регулярными структурами.

На рисунке 12 изображена структурная схема матричной ММВС, в которой связи между ВМ как по горизонтали, так и по вертикали кольцевые, а граф связей представляет собой  тор.

В ММВС, приведенной на рисунке 12 предполагается, что в каждый ВМ встроен КМ с 4-я парами линков: две пары для связи по горизонтали и две – для связи по вертикали.

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Рисунок 12 – Структурная схема матричной ММВС (а)

и граф связей между ВМ при N=16 (б)

 

Возможны и другие маршруты передачи пакета. Например, вначале передавать по вертикали и затем по горизонтали, можно передавать по шагам, чередуя передачи по горизонтали и по вертикали и т.п.

На рисунке 13, а и б приведены графы связей между ВМ других вариантов матричных ММВС  (в виде решетки и витого тора).

Многомерные структуры ММВС строятся аналогично. Так например, в трехмерной  структуре каждый ВМ имеет связи по трем координатам (рисунок 13, в).

Предельным вариантом многомерной структуры является структура гиперкуба (рисунок 13, г). В каждый ВМ такой структуры встроен коммутационный модуль, аналогичный показанному на рисунке 11 со значением L = m = log₂N.

Код маршрута в случае гиперкуба определяется путем поразрядного сравнения адресов ВМ-источника и ВМ-приемника. Каждый разряд кода адреса соответствует одной определенной координате. Передача пакета по k-ой координате (1≤ k ≤ m) производится, если коды адресов ВМ-источника и ВМ-приемника не совпадают. В какой последовательности производится поразрядное сравнение и передача не имеет значения. Поэтому можно получить k! (k – число несовпадающих разрядов) альтернативных трактов передачи (в пределе – m!).

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Рисунок 13 – Графы связей между ВМ в матричных ММВС (N=16)

со структурой  в виде решетки (а), витого тора (б),

фрагмент графа связей в трехмерной структуре (в)

и в ММВС (N=8) со структурой гиперкуб (г)

 

Для характеристики коммутаторов ММВС с регулярными связями между ВМ используются следующие структурные параметры:

- число  выводов (портов)  у каждого КМ, встроенного в ВМ – L;

- длина тракта передачи, выраженная в числе линий связи между ВМ-источником и ВМ-приемником в наихудшем случае – W. (Отметим, что число КМ, входящих в тракт передачи, на 1 больше и равно W+1);

- затраты оборудования в у.е. на реализацию узла ключевых элементов SD, приведенные к одному ВМ – Q₀. (1 у.е. – это затраты на один двунаправленный или на два однонаправленных ключевых элемента). Резонно предположить, что затраты на КМ в целом пропорциональны затратам на SD. Поэтому значения Q₀ удобно использовать для сравнительной оценки сложности КМ для различных структур ММВС. (Q₀=Q/N, где Q – общие затраты на коммутатор, N – число ВМ).

Значения структурных параметров для рассмотренных выше структур ММВС приведены в таблице 1 (строки 1 – 5).

 

Таблица 1 – Структурные параметры ММВС

* m = log₂N

 

На рисунке 14 показаны зависимости  Q₀ = f(N), а на рисунке 15 – зависимости  W = f(N) для разных структур ММВС. Номера линий соответствуют номерам структур, указанным в таблице 1.

 

 

 

 

 

 

 

 

 

 

 

Рисунок 14 – Графики зависимости Q₀ = f(N) для разных структур ММВС

 

 

 

 

 

 

 

 

 

 

 

 

Рисунок 15 – Графики зависимости W = f(N) для разных структур ММВС

 

Из анализа приведенных зависимостей следует, что если ранжировать показатели качества ММВС в следующем порядке: Q, W, то предпочтительными являются кольцевые структуры, а также:

- многошинные ММВС при N≤32,  

- матричные ММВС или ММВС типа гиперкуб при N>32.

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

 

Для определения временных параметров коммутаторов ММВС рассмотрим диаграммы передачи пакета данных от одного ВМ к другому. Для определенности предположим, что производится передача пакета с буферизацией из СОМ1 в СОМ3 (режим записи) в кольцевой ММВС, изображенной на рисунке 10, а. Диаграмма этой передачи показана на рисунке 16, а.

Пакет формируется в СОМ1 и записывается в буферную память его адаптера ВFMOUT  с частотой  f₁ (интервал Т₁). Затем сформированный пакет передается из BFMOUT COM1 c частотой f₂ в транзитную буферную память BFMT2  COM2  и  далее  в BFMIN COM3.

Отметим, что передача из одной (передающей) BFM в другую (принимающую) начинается сразу после записи первой порции данных в передающую BFM, т.е. когда передающая BFM «не пуста». Двойные линии в начале и в конце некоторых диаграмм означают следующее: первая линия в начале – начало процесса записи в BFM (W), вторая – начало процесса считывания из BFM (R), первая линия в конце – конец процесса записи, вторая – конец процесса считывания.

 Время передачи  пакета в коммутаторе по всему тракту от ВМ-источника до ВМ-пиемника (интервал Т₂) определяется по формуле:

 

Т₂ = (Е/n₂ + W)/f₂ ≈ Е/(n₂f₂),

 

где Е – размер пакета, Е/n₂ – число порций данных в пакете, W – число транзитных BFM,  участвующих в передаче пакета (W << Е/n₂)_.

Передача завершается записью данных пакета в оперативную память ВМ-приемника (интервал Т₃).

 

 

 

 

 

 

 

 

 

 

 

 

T_TP – время передачи пакета из одного ВМ к другому,

T₁ – время формирования пакета при записи в BFMOUT,

T₂ – время передачи пакета в коммутаторе (время занятости тракта передачи),

T₃ – время записи данных пакета в оперативную память ВМ-приемника,

T₄ – время установления тракта передачи пакета,

T₅ – время передачи пакета по подготовленному тракту в коммутаторе

 

Рисунок 16 – Диаграмма бесконфликтной передачи пакета данных

с буферизацией (а) и без буферизации (б)

 

Полное время передачи пакета данных от ВМ-источника к ВМ-приемнику Т_ТР равно:

Т_ТР= Т₁+Т₂+Т₃.

 

В этом выражении Т₂ это время передачи пакета в коммутаторе, а Т₁ и Т₃ –это время формирования и расформирования пакета и его передачи через выходную и  входную буферные памяти ВМ-источника и ВМ-приемника соответственно. Другими словами Т₁ и Т₃ – это задержки прохождения пакета через адаптеры ВМ-источника и ВМ-приемника.

Рассмотрим теперь аналогичную передачу пакета данных в коммутаторе без буферизации. В этом случае буферные памяти в узлах ключевых элементов SD отсутствуют (см. рисунок 11).

После формирования и записи пакета в BFMOUT ВМ-источника (интервал Т₁ на рисунке 16, б) начинается подготовка тракта передачи пакета в соответствии с кодом маршрута через ключевые элементы в каждом из КМ тракта передачи. Это интервал времени Т₄ на рисунке 16, б, иногда называемый латентностью. После подготовки тракта передачи производится передача пакета по всему тракту на частоте  f₂   за время
 Т₅  = Е/(n₂f₂). Поскольку  обычно Т4<<Т5, то можно считать, что время передачи пакета в коммутаторе без буферизации приблизительно равно времени передачи пакета в коммутаторе с буферизацией, т.е. Т₄ + Т₅  ≈ Т_2..

Ключевые элементы SС5 и SС6 и буферные памяти BFМТ1 и BFМТ2 в каждом КМ коммутатора являются общим ресурсом для трактов передачи пакетов. На этом ресурсе возможны конфликтные ситуации, называемые также блокировками. Эти ситуации приводят к задержкам при передаче пакетов.

Поясним эти ситуации на следующем примере. Пусть в ММВС, изображенной на рисунке 10, а одновременно инициируется передача пакета Р1 из СОМ1 в СОМ3 и такого же по размеру пакета Р2 из СОМ2 в СОМ4. Общий ресурс – SС6 и BFМТ2 коммутационного модуля, входящего в состав СОМ2. Процесс передачи иллюстрируется диаграммой, приведенной на рисунке 17.

 

 

Рисунок 17 –  Диаграмма одновременной передачи пакета Р1

из СОМ1 в СОМ3 и  пакета Р2 из СОМ2 в СОМ4 кольцевой ММВС

 

Из диаграммы видно, что передача пакета Р1 через BFМТ2 СОМ2 задерживается из-за того, что BFМТ2 занята пакетом Р2, поскольку запрос на передачу Р2 пришел раньше, чем запрос на передачу Р1.  Пакет Р1 ожидает освобождения общего ресурса, находясь в BFМТ2 СОМ1. Время ожидания не превышает времени передачи пакета Р2 (интервал Т₂).

Более подробный анализ различных временных диаграмм передачи пакетов данных, как с буферизацией так и без неё позволяет заключить, что

- минимальное время передачи пакета через коммутатор,  равное E/(f₂n₂), получим при условии, что тракт передачи свободен и E>>W;

- максимальное время передачи пакета через коммутатор,  равное EW/(f₂n₂),  получим при условии, что тракт передачи занят. 

Какому варианту передачи с буферизацией или без нее следует отдать предпочтение?

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

Еще одним фактором, влияющим на выбор варианта, является максимальная длина пути передачи пакета  W.  Чем этот путь длиннее, тем вероятнее конфликты.

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

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

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

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

Подводя итог, отметим, что основными временными параметрами коммутатора являются  f₂,  n₂ и W. Последний параметр характеризует вероятность конфликтных ситуаций и связанное с ними увеличение времени передачи пакета через коммутатор.

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

Другие параметры являются производными от этих основных. Так, например, пропускная способность тракта (канала) передачи определяется выражением:  2f₂n₂ [байт/с]. Коэффициент 2 здесь учитывает возможность одновременной передачи пакетов по каждому из двух линков в противоположных направлениях.

 

2.4.         Многомашинные вычислительные системы

с полносвязными коммутаторами

 

В ММВС с полносвязным коммутатором обеспечиваются одинаковые связи каждого ВМ с другими ВМ, причем W = 1. Граф связей между ВМ для N = 8 приведен на рисунке 18, структурная схема ММВС на рисунке 19. Устройство управления коммутатором на рисунке 19 не показано.

 Коммутатор представляет собой матрицу 8×8 однонаправленных ключевых элементов SС, в которой диагональные элементы отсутствуют. Предполагается, что адаптеры встроены в ВМ, так что каждый ВМ имеет входную и выходную шины (B2IN и B2OUT). Соединенные  с ними выводы  коммутатора обозначены на рисунке соответственно 1OUT …8OUT и  1IN … 8IN.

 

 

 

 

 

 

 

 

 

           Рисунок 18 – Граф связей

             между ВМ для N = 8

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Рисунок 19 – Структурная схема ММВС

с полносвязным матричным коммутатором для N = 8

 

Каждый столбец матрицы по своей структуре является мультиплексором на N–1 вход, а каждая строка – селектором на N–1 выход. Однако обычно коммутатор не делят на коммутационные модули, поскольку каждый такой модуль должен содержать N входных/выходных шин. Коммутатор выполняют как единую конструктивную единицу с N парами выводов (входов/выходов), которые называют портами.

Обычно матричный коммутатор выполняют с введенными в его состав диагональными SC. Затраты оборудования небольшие, но достигается универсальность применения.

Структурные параметры матричного полносвязного коммутатора приведены в таблице 1 (строка 6). Конфликтные ситуации в тракте коммутатора отсутствуют, однако конфликты могут быть на ВМ-приемниках, т.е. на выходах каждого из портов коммутатора. Для разрешения конфликтных ситуаций для каждого выхода в блоке управления коммутатором должен быть предусмотрен  арбитр.

Код маршрута для матричного полносвязного коммутатора это номер (адрес) ВМ-приемника.

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

Варианты условных обозначений 8-портового коммутатора приведены на рисунке 20.  

 

 

 

 

 

 

 

 

Рисунок 20 – Варианты условных обозначений

8-портового коммутатора

 

Затраты оборудования, необходимые для построения матричного полносвязного коммутатора,  велики, поэтому такие коммутаторы строят для N£32.

Для сокращения затрат оборудования полносвязные коммутаторы реализуются в виде многоступенчатых коммутаторов на базе коммутационных модулей 4´4  или 4´4 в сочетании с 2´2, если  log₂N – нечетное число (рисунок 21).

В КМ 2´2 одноразрядный код маршрута определяет номер выхода. При коде маршрута равном 0 пакет передается на верхний выход, а при коде маршрута равном 1 – на нижний,  независимо от того, на какой из входов поступает пакет. В КМ 4´4 номер выхода определяется двухразрядным кодом маршрута.

Затраты оборудования на построение КМ 2´2 составляют 2 у.е., а на построение КМ 4´4 – 8 у.е. (напомним, что 1 у.е. – это затраты на построение двух однонаправленных ключевых элементов SC).

 

 

 

 

 

 

 

 

 

 

 

 

 

Рисунок 21 – Коммутационные модули 2´2 и 4´4

а – 2´2,  CON – блок управления, SD – узел ключевых элементов SC,

 С1, С3, С5, С7 – сигналы  ЗАПРОС, С2, С4, С6, С8 – сигналы ЗАНЯТО;

б – 4´4, блок управления не показан, ключевые элементы показаны условно

 

На рисунке 22 в качестве примера приведены многоступенчатые  8-портовые коммутаторы, построенные на базе коммутационных модулей 2´2 и 4´4.

Для этих коммутаторов, как и для полносвязных коммутаторов, трехразрядный код маршрута – это номер ВМ-приемника.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Рисунок 22 – Многоступенчатые 8-портовые коммутаторы

на базе коммутационных модулей 2´2 и 4´4 (а) и 4´4 и 2´2 (б)

 

В многоступенчатых коммутаторах невозможно выделить части, относящиеся к конкретным ВМ. Поэтому затраты  оборудования, приходящиеся на один ВМ (Q₀) следует определять по формуле: Q₀ = Q/N, где Q – общие затраты на коммутатор, N – число ВМ или портов.

На рисунке 23, а показан 16-портовый коммутатор, выполненный на КМ 4´4. Выходы КМ первой ступени коммутатора являются общим ресурсом коммутатора, на котором возможны конфликтные ситуации (блокировки).

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Рисунок 23 – Многоступенчатый 16-портовый коммутатор

без обходных путей (а) и с обходными путями (б),

показанными более толстыми линиями

 

Рассмотрим маршрутизацию пакетов в коммутаторе с обходными путями на примере приведенного выше 16-портового коммутатора. Будем полагать, что коммутатор передает пакеты без буферизации.

Предположим, что на вход 1IN коммутатора приходит пакет Р1 с кодом маршрута, т.е. адресом порта, к которому подключен ВМ-приемник, 0110. Следом за ним на вход 2IN приходит пакет Р2 с кодом маршрута 0111. Код маршрута делится на две группы разрядов: старшие два разряда – это код маршрута для первой ступени коммутатора, а младшие – для третьей ступени. В блоке управления КМ SM1 прежде всего анализируются старшие разряды кода маршрута Р1 и начинается подготовка тракта для его передачи.

Далее из анализа старших разрядов кода маршрута Р2 выясняется, что этот пакет должен передаваться через выход 01 SM1, однако этот выход уже занят для передачи пакета Р1.

Затем проверяются младшие разряды кода маршрута Р1 и Р2. Если эти разряды тоже совпадают, т.е. обращение идет к одному и том же ВМ-приемнику, то передача пакета Р2 приостанавливается до конца передачи пакета Р1. В противном случае начинается подготовка обходного маршрута для передачи пакета Р2.

Для этого в блоке управления SM1 к старшим разрядам кода маршрута Р2 добавляется единица (получим 10) и выясняется свободен ли выход 10 SM1. Если этот выход свободен, то начинает готовиться тракт для передачи пакета Р2 на следующую ступень коммутатора по обходному маршруту. В противном случае к старшим разрядам кода маршрута Р2 добавляется еще единица и выясняется свободен ли следующий выход SM1 и т.д. до нахождения свободного выхода.

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

Все описанные выше действия выполняются с помощью аппаратуры устройств управления КМ первой и второй ступеней коммутатора по сигналам ЗАПРОС и ЗАНЯТО.

Кодом маршрута пакета Р2 для управления второй (дополнительной) ступенью коммутатора является код 01, которым производится как бы возвращение пакета Р2 на его первоначальный маршрут. Код маршрута пакета Р1 для второй ступени коммутатора остается таким же, как и для первой ступени, т.е. 01, поскольку при передаче пакета Р1 конфликта нет.

Таким образом, код обходного маршрута для основной ступени (в нашем примере первой) формируется блоком управления этой ступени, а код маршрута дополнительной ступени остается исходным и обеспечивает возвращение пакета Р2 на его первоначальный маршрут.

После завершения подготовки трактов для передачи каждого из пакетов начинается их передача по подготовленным маршрутам.

Произведем оценку структурных параметров коммутаторов с обходными путями с КМ 4´4 без буферизации.

Длина тракта передачи W равна сумме основных и дополнительных ступеней коммутатора: log₂N–1 (см. таблицу 1).

Затраты оборудования определяются аналогично: 2(log₂N–1).

Зависимости Q₀(N) и W(N) полносвязных коммутаторов показаны на рисунках 14 и 15 (кривые 6, 7 и 8).

В литературных источниках упоминается структура ММВС типа «звезда». Однако термин «звезда» представляется неудачным из-за его неоднозначного толкования. В самом деле, этот термин одинаково подходит, если под коммутатором (см. рисунок 5) понимать как полносвязный коммутатор, так и общую шину (см. рисунок 7, а при L=1). В дальнейшем термин «звезда» применяться не будет.

 

2.5. Многомашинные вычислительные системы

с составными коммутаторами

 

Рассмотренные выше матричные и ступенчатые полносвязные коммутаторы обладают тем свойством, что их порты являются универсальными в том смысле, что к любому порту могут быть подключены либо адаптер вычислительного модуля, либо порт другого коммутатора. Последнее обстоятельство позволяет просто выполнять наращивание ММВС, причем можно представить себе множество вариантов соединения коммутаторов, наращивая ММВС как «вширь», так и «ввысь».

При дальнейшем изложении полносвязные коммутаторы будем называть групповыми коммутационными модулями (ГКМ, обозначение на схемах – GSM), а подключенные к одному ГКМ вычислительные модули группой вычислительных модулей (ГВМ, обозначение на схемах – GCOM). На этих двух типах элементов структуры можно построить множество вариантов структур ММВС, приспосабливая эти варианты под классы задач, решаемых на ММВС.

Рассмотрим несколько вариантов построения составных ММВС введя следующие ограничения:

-         в каждом из вариантов ММВС используются ГКМ только одного типа;

-         связи между элементами структуры – регулярные.

Благодаря этим ограничениям просто решается задача определения кода маршрута между ВМ-источником и ВМ-приемником, а маршрутизация выполняется по принципу самомаршрутизации

Составная кольцевая структура. На рисунке 24, а приведен фрагмент схемы для построения кольцевой структуры. Здесь ГКМ имеет 4 порта, два из которых используются для подключения ГВМ, состоящей из двух ВМ, а другие используются для соединения с соседними ГКМ.

 

 

 

 

 

 

 

 

Рисунок 24 – Фрагменты составной ММВС с кольцевой структурой с  одной (а) и двумя (б) связями между ГКМ

 

При передаче данных между ВМ, входящими в одну группу, W = 1, а при передаче данных в ВМ других групп в худшем случае – W = G/2 = N/4, где G – число групп в ММВС.

Затраты оборудования, приведенные к одному ВМ, равны затратам на один  4-портовый ГКМ, деленным на число ВМ в группе: Q₀=8/2=4.

Число связей между ГКМ обычно делают  ³ 2, во-первых, для повышения пропускной способности, и, во-вторых, для сохранения работоспособности ММВС в случае отказа одной из связей.

На рисунке 24, б приведен фрагмент составной кольцевой ММВС с числом связей, равным двум. Легко показать, что для этой структуры Q₀ =7,  а W=N/8.

Интересно отметить, что в составных ММВС с регулярными структурами значение Q₀ минимально, если число портов, связывающих данную группу с другими, равно числу ВМ в группе.

Составная матричная ММВС может быть построена из фрагментов, изображенных на рисунке 25.

 

 

 

 

 

 

 

 

 

Рисунок 25 – Фрагмент составной матричной ММВС

 с одной (а) и двумя (б) связями между ГКМ

 

Для этих структур Q₀  равно 7 и 15,  а W –   и  соответственно.

При использовании кольцевых и матричных ММВС просто решается вопрос наращивания «вширь», правда при этом растет значение W.

Составные многомерные структуры (вплоть до структуры типа гиперкуб) строятся аналогично матричным.

Составные древовидные (иерархические) структуры ММВС.

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

В различных вариантах структур ММВС будут использоваться ГКМ различных типов, т.е. здесь не будет учитываться первое из принятых ранее допущений о построении составных ММВС.

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

Различные варианты древовидных (иерархических) структур проиллюстрируем на примере дерева, состоящего из 16-и  ВМ.

В качестве исходной структуры ММВС возьмем структуру типа двоичное дерево, построенную с использованием 3-портовых полносвязных КМ (рисунок 26, а). Для наглядности на рисунке показан только граф связей между КМ, а ВМ не показаны.

Код маршрута в такой ММВС определяется по номерам (адресам) ВМ-источника  и ВМ-приемника. Вначале делается сравнение  номеров ВМ-источника  и ВМ-приемника последовательно по разрядам, начиная со старшего, и производится подъем по дереву до яруса, для которого эти коды еще отличаются. Начиная с этого яруса, производится спуск по дереву, при этом, если очередной разряд кода ВМ-приемника 0, то спуск идет по левой ветви, а если – 1, то по правой.

Основными параметрами, характеризующими древовидные (иерархические) структуры, являются:

- число ярусов групповых КМ в структуре ММВС. В исходной структуре (рисунок 26, а ) их 4;

- число уровней коммутации, которое равно числу групп в коде маршрута. В исходной структуре  – 4 одноразрядных группы;

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

Исходная древовидная структура ММВС экономична по затратам оборудования (Q₀ → 3 при N→ ∞), но имеет существенные недостатки:

- большая длина тракта передачи пакета данных;

- большая вероятность блокировок, которые возможны уже на выходах ГКМ нижнего яруса структуры ММВС.

Совершенствование древовидных структур ММВС направлено на преодоление этих недостатков и может идти по двум направлениям. Это:

1)                уменьшение числа ярусов ГКМ за счет расшифровки на одном ярусе не одного, а двух и более разрядов кода маршрута. Причем такие сжатые ярусы могут создаваться как в верхней, так и нижней частях дерева, а также в верхней  и нижней частях одновременно;

2)                увеличение пропускной способности связей между ярусами ГКМ или, как говорят, увеличение «толщины» дерева.

Рассмотрим вначале варианты сжатия дерева (рисунок  26 и таблица 2). Для наглядности на рисунке не показаны ВМ, а число связей везде принято равным 1.

В первой строке таблицы 2 приведены параметры исходной структуры ММВС (N=16).

 

Рисунок 26 – Графы связей различных вариантов древовидных структур ММВС

а – исходное двоичное дерево: число ярусов – 4, число уровней коммутации – 4, наибольшая длина тракта передачи – 8; б – дерево с параметрами 3, 4, 7; в– дерево, сжатое сверху, параметры 3, 3, 6;  г, д – деревья, сжатые в центре и снизу, параметры 2, 3, 5; е, ж – двухъярусные деревья, параметры 2, 2, 4; з, и – одноярусные деревья, параметры 1 , 2, 3

 

Вторая строка соответствует структуре, которую не предполагается наращивать «ввысь», поэтому ГКМ верхнего яруса исключен.

В строках 3, 4 и 5 отражены структуры, в которых «сжаты» два яруса (и уровни коммутации) сверху, в центре и снизу соответственно.

Строка 6 – структура, в которой сжаты 3 верхних яруса ГКМ исходной структуры.

Строки 7 и 8 – структуры, в которых сжаты как верхние, так и нижние ярусы ГКМ.

Строка 9 – структура, в которой сжаты 3 нижних яруса ГКМ.

Строка 10 соответствует структуре предельного сжатия, когда все ВМ, как равноправные, подключены к одному ГКМ. Очевидно, что в этом случае образуется полносвязная структура.

 

Таблица 2 – Параметры различных вариантов построения

древовидных структур ММВС (N=16)

 

Анализ вариантов структур ММВС, приведенных в таблице 2, позволяет сделать вывод о перспективности структур, сжатых как сверху так и снизу и имеющих малую длину тракта передачи пакетов (4 или 3). Это двухъярусные и одноярусные структуры, соответствующие строкам 7 и 8 таблицы 2.

Рассмотрим  теперь увеличение пропускной способности связей между ярусами ГКМ. В качестве исходной возьмем структуру ММВС, приведенную в строке 2 таблицы 2 (рисунок 26, б).

Минимальное число связей, как указывалось выше должно быть две, а максимальное таким, чтобы получить коммутатор без блокировок. Это значит, что сумма выходов ГКМ на каждом ярусе должна быть равна  N.
В рассматриваемом примере это 16. Отметим, что если связей несколько, а именно 2, 3, 4, …, то для передачи пакета может использоваться любая из них, как при подъеме по дереву, так и при спуске.

Некоторые из возможных вариантов числа связей в исходной структуре приведены в таблице 3 (строки 1 – 4).

Интересна структура ММВС, соответствующая строке 1 таблицы 3, в том отношении, что для её  построения (и наращивания) используются однотипные 6-портовые КМ. Такую структуру  ММВС целесообразно применять тогда, когда вероятность передачи пакета данных между ВМ-источником и ВМ-приемником тем меньше, чем дальше друг от друга они отстоят. Для этой структуры Q₀→ 7,5  при N→ ∞. Отметим, что эта структура нашла практическое применение (Raceway фирмы Cypress).

 

Таблица 3 – Параметры различных вариантов структур ММВС

типа «толстое» дерево (N=16)

 

Для структур ММВС с более толстыми связями (строки 2, 3 и 4 таблицы 3) требуются очень большие затраты оборудования, причем бóльшие, чем для полносвязной структуры. Применение таких структур бесперспективно.

Рассмотрим далее увеличение пропускной способности связей для других структур ММВС (строки 7, 8 и 9 таблицы 2).

В структурах ММВС с двухъярусным коммутатором (см. рисунок 26, ж) число КМ верхнего яруса  равно толщине дерева. Каждый из них связан  с каждым из КМ нижнего яруса (рисунок 27).

Параметры этих коммутаторов приведены соответственно в строках 5, 6 и 7 таблицы 3. Отметим, что первый и второй коммутаторы блокируемые, а третий – неблокируемый, благодаря возможности выбора обходного пути без каких-либо дополнительных затрат.

 

 

 

 

 

 

 

 

 

Рисунок 27 – Графы связи между ГКМ в двухъярусных блокируемой (а, б)

 и неблокируемой (в) структурах ММВС (N=16)

 

Многомашинные ВС с двухъярусным коммутатором могут быть построены с использованием КМ одного типа. В качестве примера на рисунке 28 приведен 128-портовый коммутатор, построенный на 24-х 16-портовых КМ (фирма Myrinet). Для этого коммутатора сжатие сверху –
4 разряда, сжатие снизу – 3 разряда;  Q₀= 24, W = 3, если КМ матричные.

Дополнительная экономия оборудования в этом двухступенчатом коммутаторе может быть получена, если допустить увеличение длины тракта передачи  на 2 и использовать многоступенчатые КМ (Q₀=12, если КМ блокируемые и   Q₀=18, если КМ неблокируемые).

 

 

 

 

 

 

 

 

 

 

Рисунок 28 – Древовидный двухъярусный неблокируемый

128-портовый коммутатор

 

Параметры одноярусной структуры с толстыми связями (2) приведены в строке 6 таблицы 3. Видно, что уменьшение длины тракта передачи  обходится очень дорого: даже при двойной толщине связи затраты оборудования превышают затраты для матричного коммутатора. Одноярусная структура самая неэкономичная.

Некоторая экономия может быть достигнута в случае применения многоступенчатых КМ.

Например, на многоступенчатых 32-портовых КМ построен 64-портовый коммутатор SP-2 фирмы IBM (рисунок 29). Для этого коммутатора толщина связей 5 или 6, сжатие сверху – 2 разряда, сжатие снизу – 4 разряда;  Q₀=32, W = 4.

 

 

Рисунок 29 – Древовидный одноярусный блокируемый

64-портовый коммутатор

 

Общий недостаток древовидных структур с толстыми связями – большие удельные затраты оборудования.

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

 

 

ЗАКЛЮЧЕНИЕ

 

Сделаем попытку упорядочить варианты построения ММВС, связав вид структуры ММВС с определением кода маршрута для передачи пакета данных от ВМ-источника к ВМ-приемнику.

1.     Регулярные структуры ММВС.

Их рассмотрение начнем с простейшей кольцевой структуры ММВС (рисунок 10). Код маршрута для такой ММВС определяется адресами ВМ-источника и ВМ-приемника. Вначале из адреса ВМ-приемника вычитается адрес ВМ-источника. Этим действием начало маршрута как бы переносится в точку кольца, соответствующую ВМ-источнику. В полученной разности старший разряд покажет направление передачи, а младшие разряды – длину пути от ВМ-источника до ВМ-приемника.

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

Для матричной структуры ММВС c витым тором (рисунок 13, б) одну группу разрядов составляют старшие разряды, а другую – все разряды. Алгоритм определения маршрута более сложный, однако число шагов здесь в худшем случае на один меньше, чем для матричной структуры  ММВС с кольцевыми связями.

Для трехмерной структуры ММВС с кольцевыми связями по каждой из координат (рисунок 13, в), адреса ВМ-источника и ВМ-приемника делятся на три группы в соответствии с координатами X, Y и Z. Маршрут по каждой из координат определяется по разности кодов соответствующих групп так, как указано выше.

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

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

2. В каждой из рассмотренных выше (в п. 1) структур ММВС связи между соседними ВМ представляют собой общий ресурс, который может потребоваться для передачи пакетов данных между различными парами ВМ. Если эти передачи выполняются одновременно, то создается конфликтная ситуация (блокировка). Конфликтные ситуации приводят к увеличению времени передачи пакетов, а значит и к снижению производительности ММВС в целом.

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

-                     создание не одной, а нескольких связей между ВМ. Например, дублирование связей в кольцевой структуре;

-                     использование альтернативных трактов передачи пакетов. Например, в структуре типа гиперкуб, если не совпадают коды в k разрядах адресов ВМ-источника и ВМ-приемника, то можно организовать  k!  различных трактов передачи пакета.

3. Можно предусмотреть свои линии связи для каждой возможной передачи пакета между любыми парами ВМ. В этом случае блокировок не может быть по определению. Такие ММВС называют полносвязными, а коммутаторы, реализующие все требуемые связи без блокировок, – матричными полносвязными.

Код маршрута в полносвязных ММВС определяется кодом адреса ВМ-приемника и не зависит от кода адреса ВМ источника.

Затраты оборудования для создания коммутаторов полносвязных ММВС очень велики – они пропорциональны числу ВМ.

4. Для уменьшения затрат оборудования в полносвязных ММВС могут быть применены многоступенчатые коммутаторы, которые строятся на базе 4-портовых и 2-портовых матричных коммутационных модулей. Однако в многоступенчатых коммутаторах возможны блокировки. Устранение блокировок здесь может быть достигнуто организацией обходных путей для связи между ВМ, но для этого требуется дополнительное оборудование.

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

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

Если разряды второй части рассматривать как единую группу, то получим составную кольцевую структуру ММВС.

Если разряды второй части разделить на две группы, то получим составную матричную структуру ММВС и т.д. до получения составной структуры типа гиперкуб.

Отметим, что для уменьшения вероятности блокировок и повышения надежности ММВС число связей между КМ целесообразно увеличить по крайней мере до двух.

Отметим также, что если к каждому КМ подключен только один ВМ, то составные структуры ММВС (кольцевая, матричная и т.п.) превращаются в аналогичные регулярные структуры ММВС. Иными словами регулярные структуры – это частный случай составных регулярных структур.

5. Рассмотрим теперь древовидные (иерархические) структуры ММВС, в которых ВМ занимают место листьев дерева. Простейший вариант древовидной структуры ММВС это двоичное дерево, содержащее  m–1  ярус групповых КМ и m уровней коммутации  (m =log₂N, N – число ВМ). Каждый уровень коммутации соответствует одному разряду кода маршрута. Тракт передачи пакета (подъем по дереву и затем спуск) составляют в худшем случае 2m–1 линий связи. Для сокращения длины тракта передачи производится сжатие дерева (сверху и/или снизу), при этом делается соответствующая группировка разрядов кода маршрута (слева и/или справа).

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

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

Достоинством древовидных структур ММВС является более простое (чем регулярных структур) разрезание их на части, необходимое при конструктивной реализации ММВС.

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

 

 

ЛИТЕРАТУРА

 

1.                 Дерюгин А. А. Электронные вычислительные машины и системы. Основные термины, определения и обозначения. Электронный журнал «Вычислительные сети .Теория и практика» 2005 №2(7) : 2.1

http://network-journal.mpei.ac.ru/cgi-bin/main.pl?l=ru&n=7&pa=2&ar=1

2.                 Дерюгин А. А. Вычислительные системы. Классификация. Электронный журнал «Вычислительные сети .Теория и практика» 2005 №2(7) : 2.2

http://network-journal.mpei.ac.ru/cgi-bin/main.pl?l=ru&n=7&pa=2&ar=2