Способ организации системной сети в виде неблокируемого самомаршрутизируемого трехмерного р-ичного мультикольца Российский патент 2019 года по МПК G06F15/163 

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

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

В работе «Подлазов B.C. p-р-перестраиваемость и отказоустойчивость сдвоенных р-ичных мультиколец и обобщенных гиперкубов // Автоматика и телемеханика. - 2002. -№7. - С. 138 - 148» показано, что p-ичное мультикольцо любой размерности r с удвоенным набором межузловых каналов является перестраиваемым для р-р-перестановок (одновременно реализуемых р разных перестановок). Однако в перестраиваемых сетях бесконфликтная маршрутизация предполагает предварительное вычисление маршрутов для каждой перестановки отдельно, то есть отсутствует возможность самомаршрутизации.

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

В работе «Каравай М.Ф., Подлазов B.C. Распределенный полный коммутатор как «идеальная» системная сеть для многопроцессорных вычислительных систем // Управление большими системами. - 2011. - Вып. 34. - С. 92 - 116» показано, что неблокируемую самомаршрутизируемую сеть из N узлов можно построить в виде двумерного p-ичного мультикольца, при этом N=р², а каждый узел содержит коммутатор р×р и абонента (процессор) с р входными и р выходными портами.

Однако, для получения мультиколец большой размерности потребуются коммутаторы с большим р. Например, для сети в 1000 и 10000 узлов потребуются коммутаторы соответственно на 33 и 100 входов-выходов, а доступные микросхемы сетевых коммутаторов имеют 8×8 входов-выходов (практически недоступные фирменные - 64×64 входов-выходов).

В патенте RU 2435295 С, 27.11.2011 предложен способ расширения сети путем построения неблокируемого мультикольца с N_R=р³ узлами, в котором в качестве узлов используются двумерные мультикольца с N=p². В этом способе используются мультиплексоры-демультиплексоры и, хотя для этого мультикольца требуются коммутаторы меньшей размерности, но общая его сложность оказывается больше, чем у двумерного мультикольца с тем же числом узлов.

Рассмотренная в главе 2.1 работы «Каравай М.Ф., Подлазов B.C. Распределенный полный коммутатор как «идеальная» системная сеть для многопроцессорных вычислительных систем // Управление большими системами. - 2011. - Вып. 34. - С. 92 - 116» системная сеть в виде двумерного р-ичното мультикольца выбрана в качестве прототипа.

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

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

Техническим результатом изобретения является способ организации новой неблокируемой самомаршрутизируемой системной сети в виде 3-мерного p-ичного мультикольца, отличающийся кубической зависимостью числа узлов сети N от размерности коммутаторов р (N=р³).

Технический результат достигается тем, что предложен новый способ организации системной сети в виде неблокируемого самомаршрутизируемого трехмерного p-ичного мультикольца, характеризующийся тем, что каждый i-ый узел из N=p³ узлов, пронумерованных от 1 до N, соединяют 3-мя группами симплексных линий передачи сетевых пакетов, соответствующим 3-м измерениям мультикольца, с m узлами, номера которых вычисляют по формулам i+m, i+mp, i+mp² соответственно в первом, втором и третьем измерениях, значение m равно 0, 1, 2, …, р-1 и задает номер линии в группе (где р - натуральное число), при этом каждый узел включает процессор с 2р входами и р выходами, а также коммутатор с 5(р-1)+1 входами и 6(р-1)+2 выходами, соединяемых семью группами линий, а именно, группой линий X_O в первом измерении, группами линий Y_I, Y_M, Y_D, Y_R во втором измерении и группами линий Z_I, Z_M в третьем измерении,

причем, р линий группы X_O прокладывают с р выходов процессора i-го узла на входы р коммутаторов соответствующих m узлов,

р линий группы Y_I прокладывают с р выходов коммутатора i-го узла на входы р процессоров соответствующих m узлов,

р линий группы Z_I прокладывают с р выходов коммутатора i-го узла на входы р процессоров соответствующих m узлов,

р-1 линий групп Y_M, Y_D, Y_R, Z_M прокладывают на входы р-1 коммутаторов соответствующих m узлов, номера которых вычисляют при m=1, 2, …, р-1, а именно,

р-1 линий группы Y_M прокладывают с р-1 выходов коммутатора i-го узла на входы р-1 коммутаторов соответствующих m узлов,

р-1 линий группы Y_D прокладывают с р-1 выходов коммутатора i-го узла на входы р-1 коммутаторов соответствующих m узлов,

р-1 линий группы Y_R прокладывают с р-1 выходов коммутатора i-го узла на входы р-1 коммутаторов соответствующих m узлов, причем в данной группе при вычислении номера следующего узла значения m задают с отрицательным знаком, то есть i-mp,

р-1 линий группы Z_M прокладывают с р-1 выходов коммутатора i-го узла на входы р-1 коммутаторов соответствующих m узлов;

при этом, внутри каждого коммутатора организуют полнокоммутаторные связи от входов X_O к выходам Y_I, Z_I и Y_M, от входов Y_M к выходам Z_I, от входов Y_D к выходам Y_R и Z_M, от входов Y_R к выходам Z_I, от входов Z_M к выходам Y_I и прямые связи от входов X_O к выходам Y_D, а выбор соединений для передачи сетевых пакетов устанавливают посредством коммутатора независимо от других узлов с учетом параметров маршрута в заголовке пакета и наличия конфликтов на линиях групп Y_M и Y_R следующим образом:

параметры кратчайшего маршрута m₁, m₂, m₃ в заголовке пакета, сформированном процессором, при отсутствии конфликтов задают три этапа прокладки прямого пути пакетом, а именно, узел-источник передает пакет по линии X_O(m₁) в следующий узел сети, коммутатор которого передает пакет без буферизации по линии Y_M(m₂) в следующий узел сети, коммутатор которого передает пакет без буферизации по линии Z_I(m₃) в узел-приемник;

если коммутатор обнаруживает конфликт при передаче пакета на линию Y_M(m₂), то он устанавливает соединение для передачи этого пакета на линию Y_D(m₂), причем параметр m₂ берется равным параметру m₁ (то есть номеру линии X_O(m₁), по которой коммутатор получает пакет);

если коммутатор не обнаруживает конфликт при передаче пакета с входа Y_D(m₂) на линию Y_R(m₂^*), то он устанавливает соединение для передачи этого пакета на линию Y_R(m₂^*) с номером m₂^*=m₂-m₁ при m₁≥m₂ или на линию Y_R(m₂^*) с номером m₂^*=m₂-m₁-р при m₁<m₂,

если коммутатор обнаруживает конфликт при передаче пакета с входа Y_D(m₂) на линию Y_R(m₂^*), то он устанавливает соединение для передачи этого пакета на линию Z_M(m₃^#) с номером m₃^#=m₃-1 при m₁≥m₂ или на линию Z_M(m₃^#) с номером m₃^#=m₃ при m₁<m₂;

если коммутатор получает пакет по линии Y_R(m₂^*), то передает его в узел-приемник по линии Z_I(m₃^*) с номером m₃^*=m₃ при m₁≥m₂ или по линии Z_I(m₃^*) с номером m₃^*=m₃+1 при m₁<m₂;

если коммутатор получает пакет по линии Z_M(m₃^#), то передает его в узел-приемник по линии Y_I(m₂^#) с номером m₂^#=m₂-m₁+р при m₁≥m₂ или по линии Y_I(m₂^#) с номером m₂^#=m₂-m₁ при m₁<m₂.

Номера запасных линий m₂^*, m₃^*, m₂^#, m₃^# для передачи пакета в случае конфликтов вычисляют в процессорах узлов и загружают в заголовки пересылаемых пакетов наряду с параметрами кратчайшего маршрута m₁, m₂, m₃, при этом коммутаторы узлов устанавливают соединения с использованием уже вычисленных номеров запасных линий, полученных в заголовках пакетов.

Техническая сущность и принцип действия предложенной сети поясняются чертежами.

На фиг. 1 и фиг. 2 приведены структура и узел НСС сети в виде 2-мерного 3-ичного мультикольца.

На фиг. 3 приведена таблица соединений 2-мерной НСС сети.

На фиг. 4 и фиг. 5 приведены структура и коммутатор НСС сети в виде 3-мерного р-ичного мультикольца.

На фиг. 6 приведена таблица соединений 3-мерной НСС сети.

На фиг.7 приведена схема узла 3-х мерной p-ичной НСС сети.

На фиг. 8 и фиг. 9 приведены графы маршрутизации в 3-мерной p-ичной НСС сети при │Y_D│≥│Y_M│ и │Y_D│<│Y_M│.

На фиг. 10 и фиг. 11 приведены примеры маршрутизация в 3-мерной 3-ичной НСС сети при │Y_D│≥│Y_M│ и │Y_D│<│Y_M│.

На фиг. 12 и фиг. 13 приведены примеры маршрутизации в 3-мерной 4-ичной НСС сети при │Y_D│≥│Y_M│ и │Y_D│<│Y_M│.

На фиг. 14 приведен график частот конфликтов по результатам моделирования 3-мерной p-ичной НСС сети.

Опишем способ организации предложенной системной сети.

Одной из сетей, которая является как неблокируемой так и самомаршрутизируемой является сеть с топологией 2-мерного p-ичного мультикольца (будем называть ее мультикольцо). Оно состоит из 2(р-1) разных симплексных колец с шагами {1, 2, …, р-1}, составляющих измерение X, и с шагами {р, 2р, …, р(р-1)}, составляющих измерение Y, и имеет N=р² узлов. Каждое кольцо состоит из одинаковых дуг, длина которых определяет шаг кольца и задается разностью по modN номеров инцидентных узлов. На фиг. 1 представлено 2-мерное 3-ичное мультикольцо из 9 узлов с шагами {1, 2}и{3, 6}. В нем дуги измерений X,Y представлены сплошными и пунктирными линиями соответственно (два кольца измерения Y с шагами 3 и 6 являются встречными кольцами и на фиг. 1 изображены одним двунаправленным кольцом). Узел сети с топологией 2-мерного p-ичного мультикольца изображен на фиг. 2, он состоит из абонента A_i (процессора) и коммутатора р×р; линии связи, соответствующие дугам измерения X, соединяют выходы абонента узла с входами коммутаторов других узлов, а линии связи, соответствующие дугам измерения Y, соединяют выходы коммутатора узла с входами абонентов других узлов. Схема межсоединений в 2-мерном р-ичном мультикольце задается таблицей инциденций, в которой в ячейках находятся номера инцидентных узлов. Для мультикольца на фиг. 1 схема межсоединений задана в табл. 1 на фиг. 2 (в дальнейшем «сеть с топологией мультикольца» и «мультикольцо» будем использовать как синонимы).

Самомаршрутизация осуществляется с помощью таблицы инциденций по номерам абонента-источника и абонента-приемника. Пусть для примера это будут узлы 2 и 7 соответственно, подчеркнутые в табл. 1. По правой части таблицы находятся номера коммутаторов, из которых есть дуги к приемнику. В примере это коммутаторы 1, 4 и 7, обозначенные двойным подчеркиванием. В левой части таблицы из этих коммутаторов находится тот коммутатор, к которому есть дуга от источника. В примере это коммутатор 4. С другой стороны любой путь длины L₂ в 2-мерном мультикольце представляет собой последовательность не более двух дуг, длины которых задаются как значения разрядов в р-ичной системе счисления L₂=i+jp (0≤i, j≤p-1). Здесь i задает длину дуги X, a j -дуги Y.

Теперь построим сеть в виде трехмерного полного p-личного мультикольца, содержащего N=р³ узлов, как композицию двух неблокируемых двумерных мультиколец.

В трехмерном полном p-ичном мультикольце из каждого узла выходят три вида дуг с длинами {1, 2, …, p-1},{р, 2р, …, р(р-1)} и {р², 2р², …, р²(р-1)} соответственно. Такое мультикольцо состоит из симплексных колец с разными шагами, каждое из которых состоит из дуг одной длины. Длины составляющих дуг задают длины шагов колец. Кольца с длинами шагов {1, 2, …, р-1} задают измерение X (мультикольцо X), кольца с длинами {р, 2р, …, р(р-1)} - измерение Y (мультикольцо Y) и кольца с длинами {р², 2р², …, р²(р-1)} - измерение Z (мультикольцо Z).

На фиг. 4 показан пример 3-мерного 3-ичного мультикольца из 27 узлов. В нем кольца измерения X обозначены сплошными дугами, измерения Y - пунктирными дугами и измерения Z- штриховыми дугами.

На фиг. 5 изображен минимальный коммутатор 3-мерного мультикольца (2р-1)×(3р-1), обеспечивающий передачу данных с р входов измерения X_O на р выходов измерения Y_I и р выходов измерения Z_I, образуя два двумерных мультикольца X_O, Y_I и X_O, Z_I, линии связи в которых заданы таблицей 2 на фиг. 6.

Таким образом, пары измерений X_O, Y_I и X_O, Z_I являются неблокируемыми 2-мерными мультикольцами, в которых любой прямой путь, состоящий не более чем из двух дуг, прокладывается посредством самомаршрутизации только через один коммутатор, как это осуществлялось выше с помощью табл. 1. Коммутатор, поддерживающий эти передачи, представлен фиг. 5.

Для полной связности узлов трехмерного мультикольца в измерение Y введено р-1 линий мультикольца Y_M напрямую соединяющих коммутаторы с шагом измерения Y. Соответственно коммутатор узла (фиг. 5) расширен дополнительными входами и выходами Y_M, а также внутрикоммутаторными связями. Тогда любые два узла трехмерного мультикольца могут быть связаны двухэтапными путями X_O, Y_I и X_O Z_I или трехэтапными X_O, Y_M, Z_I, состоящими из дуги X_O от источника к коммутатору, дуги Y_M между коммутаторами и дуги Z_I от коммутатора к приемнику (двухэтапные пути в таком случае являются частным случаем трехэтапных при Y_M=0). При этом двухэтапные и трехэтапные пути вообще не могут иметь конфликтов, т.к. дуги от источников и к приемникам при перестановке задаются единственным образом, а в середине трехэтапных путей используются дуги, которые отсутствуют в двухэтапных путях.

Однако в такой сети могут возникать конфликты на линиях Y_M.

Для предотвращения всех возможных конфликтов в полученное трехмерное мультикольцо введены в измерение Y параллельно Y_M по р-1 дополнительных дуг Y_D и Y_R, причем Y_R=-Y_M, то есть Y_R является к кольцу Y_M встречным кольцом, а также р-1 дополнительных дуг Z_M между коммутаторами в измерение Z. Узел полученной 3-мерной НСС сети представлен на фиг. 7. Соответствующим образом расширенный коммутатор со всеми его входами и выходами в составе этого узла также изображен на фиг. 7, он имеет 5(р-1)+1 входов и 6(р-1)+2 выходов (линии размечаются длинами дуг им соответствующих). При этом, внутри каждого коммутатора организованы полнокоммутаторные связи от входов X_O к выходам Y_I, Z_I и Y_M, от входов Y_M к выходам Z_I, от входов Y_D к выходам Y_R и Z_M, от входов Y_R к выходам Z_I, от входов Z_M к выходам Y_I и прямые связи от входов X_O к выходам Y_D (на фиг. 7 эти группы связей изображены внутри коммутатора линиями, соединяющими соответствующие группы входов с соответствующими группами выходов).

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

На фиг. 8 и фиг. 9 показаны все варианты самомаршрутизации любого пакета, попавшего в конфликт, в 3-мерной p-ичной НСС сети соответственно при │Y_D│≥│Y_M│ при │Y_D│<│Y_M│. Причем эти варианты не требуют буферизации, что доказывает неблокируемость данной сети.

Путевую информацию будем представлять номерами выходных дуг коммутаторов в каждом узле, которые должны составлять прямой путь. Дуги нумеруются для каждого измерения в порядке возрастания их длин числами от 0 до р-1. Номер 0 задает либо внутриузловую дугу в узле-источнике и в узле-приемнике, либо отсутствие дуги между коммутаторами разных узлов. Таким образом, дуги с длиной m₁ измерениях X задаются как числа m₁ (0≤m₁≤р-1), дуги с длиной m₂p измерения Y задаются как числа m₂ (0≤m₂≤p-1) и дуги с длиной m₃p² измерения Z задаются как числа m₃ (0≤m₃≤р-1).

Для прокладки прямого пути пакет должен содержать как минимум три числа m₁, m₂, m₃, задающих кратчайший путь между узлом-источником и узлом-приемником.

Число m₁ задает дугу X_O(m₁) длиной m₁ от узла-источника s в промежуточный узел а (см. фиг. 8 и 9). При m₁=0 узлы s и а совпадают. Число m₂ задает дугу Y_M(m₂) длиной m₂p от узла а к промежуточному узлу b. При m₂=0 узлы а и b совпадают. Число m₃ задает дугу Z₁(m₃) длиной m₃p² от коммутатора узла b к узлу-приемнику с. Эти числа для каждого кратчайшего пути вычисляются каждым узлом-источником s заранее. Числа m₂^* и m₃^* задают запасные дуги Y_R(m₂^*) и Z_I(m₃^*) на случай, если на дуге Y_M(m₂) возникнет конфликт. Числа m₂^# и m₃^# задают запасные дуги Y_I(m₂^#) и Z_M(m₃^#) на случай, если на дуге Y_R(m₂^*) возникнет конфликт. Эти запасные дуги, наряду с Y_D, и будут использованы коммутаторами узлов сети для передачи пакетов в обход конфликтных дуг на пути к узлу-приемнику с.

Рассмотрим подробнее процедуру передачи конфликтных пакетов по запасным дугам.

При произвольной перестановке из р-1 узлов s по р-1 дугам X_O в узел а поступает р-1 пакетов. Они могут бесконфликтно проследовать по р-1 дугам Y_M в р-1 узлов b. И далее по соответствующим р-1 дугам Z_I в р-1 узлов с (на фиг. 8 и 9 для простоты показана передача одного пакета из узла s в узел с). Однако при определенных перестановках может быть ситуация, при которой на передачу по одной дуге Y_M претендуют несколько пакетов из р-1 узлов s. Такая ситуация считается конфликтом первого типа на этой дуге. Конфликт первого типа возникает, когда пути из разных р-1 узлов-источников s, проходя через узел а, совпадают на одной и той же дуге Y_M, ведущей в узел b, и далее расходятся по разным дугам в разные узлы с. Таких пересечений путей, таким образом, может быть любое количество от 2 до р-1.

Разрешение конфликта для каждого пакета узла-источника s, попавшего в конфликт, осуществляется следующим образом (см. фиг. 8 и 9): из узла а прокладывается путь в узел d по дуге Y_D(m₂=m₁) длиной m₁p, у которой номер дуги m₂ равен номеру m₁ той дуги X_O(m₁), по которой этот пакет пришел в узел а. Дальнейший ход самомаршрутизации зависит от соотношения длин │Y_D│ и │Y_M│ (операция модуля определяет длину линии), а также от наличия конфликта на дуге Y_R.

При │Y_D│≥│Y_M│ (то есть m₁≥m₂) и отсутствии конфликта на дуге Y_R(m₂^*=m₂-m₁) осуществляется по ней возврат из узла d в узел b и далее в узел-приемник с по дуге Z_I(m₃^*=m₃) длиной m₃p². При │Y_D│<│Y_M│ (то есть m₁<m₂) и отсутствии конфликта на дуге Y_R(m₂^*=m₂-m₁-р) с уменьшенной на р² длиной │Y_R(m₂^*)│=(m₂-m₁)р-р² осуществляется по ней возврат из узла d в узел b^* и далее в узел-приемник с по дуге Z_I(m₃^*=m₃+1) длиной m₃p²+р².

Однако на Y_R могут возникнуть конфликты пакетов, полученных по дугам Y_D, эти конфликты назовем конфликтами второго рода. Тогда сообщение из узла-источника s, попав в конфликт на Y_R, при │Y_D│≥│Y_M│ будет передано из узла d «в обход» по дуге Z_M(m₃^#=m₃-1) длиной m₃p²-р² в узел е и далее по дуге Y_I(m₂^#=m₂-m₁+р) длиной (m₂-m₁)р+р² в узел с. А сообщение из узла-источника s, попав в конфликт на Y_R, при │Y_D│<│Y_M│ будет передано из узла d «в обход» по дуге Z_M(m₃^#=m₃) длиной m₃p² в узел е и далее по дуге Y_I(m₂^#=m₂-m₁) длиной (m₂-m₁) р в узел с.

Подведем итог. На фиг. 8 и 9 показаны пути, возникающие при самомаршрутизации пакета в процессе пересылки его из узла s в с (s→c), для любого узла s и с в составе произвольной перестановки пакетов всех узлов.

Пути самомаршрутизации при │Y_D│≥│Y_M│.

Путь при отсутствии конфликтов - sabc: X_O(m₁), Y_M(m₂), Z_I(m₃).

Путь при конфликте на дуге Y_M(m₂≤m₁) - sadbc: X_O(m₁), Y_D(m₂), Y_R(m₂^*=m₂-m₁), Z_I(m₃^*=m₃).

Путь при конфликтах на дугах Y_M(m₂≤m₁) и Y_R(m₂^*) - sadec: X_O(m₁), Y_D(m₁), Z_M(m₃^#=m₃-1), Y_I(m₂^#=m₂-m₁+p).

Пути самомаршрутизации при │Y_D│<│Y_M│

Путь при отсутствии конфликтов - sabc: X_O(m₁), Y_M(m₂), Z_I(m₃).

Путь при конфликте на дуге Y_M(m₂>m₁) - sadb^*c:): X_O(m₁), Y_D(m₁), Y_R(m₂^*=m₂-m₁-р), Z_I(m₃^*=m₃+1).

Путь при конфликтах на дугах Y_M(m₂>m₁) и Y_R(m₂^*) - sadec: X_O(m₁), Y_D(m₁), Z_M(m₃^#=m₃), Y_I(m₂^#=m₂-m₁).

Как видно, параметры маршрута m₂*, m₃*, m₂^#, m₃^# являются производными от параметров кратчайшего пути, заданного числами m₁, m₂, m₃, и вычисляются в двух вариантах в зависимости от соотношения │Y_D│ и │Y_M│ (или m₁ и m₂), то есть все возможные маршруты передачи пакета с учетом конфликтов определяются набором из семи параметров: m₁, m₂, m₃ и m₂^*, m₃^*, m₂^#, m₃^#. Номера запасных линий для бесконфликтной доставки пакета могут быть вычислены процессором и загружены в заголовок пакета наряду с параметрами m₁, m₂, m₃, а могут быть и вычислены коммутатором при установлении соединения, если наделить его этой функцией.

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

Проиллюстрируем неблокируемость и самомаршрутизируемость на примерах конкретных мультиколец.

На фиг. 10 и 11 приведены примеры маршрутизация в 3-мерной 3-ичной НСС сети, приведенной на фиг. 4, соответственно при │Y_D│≥│Y_M│ и │Y_D│<│Y_M│ (номера узлов для записи маршрута берутся с фиг. 4).

На фиг. 10 изображены маршруты s₁→с₂ (2→3→6→24) и s₂→с₁ (1→3→6→15), конфликтующие на дуге 3→6, первый из конфликтующих путей может остаться на дуге 3→6, а второй прокладывается «в обход» в случае одного конфликта по маршруту 1→3→9→6→15, при попадании в конфликт второго типа на дуге 9→6, пакет обходит дугу 9→ 6 по маршруту 1→3→9→9→15.

На фиг. 11 изображены два маршрута s₂→с₂ (27→2→8→26) и s₁→c₁ (1→2→8→17) конфликтующие на дуге 2→8, первый из конфликтующих путей остается на дуге 2→8, а второй прокладывается «в обход» в случае одного конфликта по маршруту 1→2→5→26→17, при попадании в конфликт второго типа на дуге 5→26, пакет обходит дугу 5→26 по маршруту 1→2→5→14→17.

Рассмотрим подробнее причины возникновения конфликтов второго типа и их разрешения на примере 3-мерного 4-ичного мультикольца, содержащего 81 узел (фиг. 12 и 13).

На фиг. 12 изображены маршруты s₃→c₂ (79→1→9→41) и s₂^*→с₁ (3→5→9→25). Первый пакет вступает в конфликт первого типа на дуге Y_M с сообщением из узла s₁ и передается в обход с использованием дуги Y_D и Y_R по маршруту 79→1→13→9→41. Второй пакет вступает в конфликт первого типа на дуге Y_M с пакетом из узла s₁^* и передается в обход с использованием дуги Y_D и Y_R по маршруту 3→5→13→9→25. Однако эти маршруты пересекаются на дуге Y_R(13→9), что и порождает конфликт второго типа. Первый пакет передается в обход по маршруту 79→1→13→29→41, тем разрешая возникший конфликт.

На фиг. 13 изображены маршруты s₂→с₁ (80→1→13→29) и s₃^*→c₂ (2→5→13→45). Первый пакет вступает в конфликт первого типа на дуге Y_M с пакетом из узла s₁ и передается в обход с использованием дуги Y_D и Y_R по маршруту 80→1→9→78→29. Второй пакет вступает в конфликт первого типа на дуге Y_M с пакетом из узла s₁^* и передается в обход с использованием дуги Y_D и Y_R по маршруту 2→5→9→78→45. Однако эти маршруты пересекаются на дуге Y_R(9→78), что и порождает конфликт второго типа. Первый пакет передается в обход по маршруту 80→1→9→25→29, тем разрешая возникший конфликт.

Таким образом, конфликты первого типа, возникшие в узлах а, разрешаются с помощью дополнительного мультикольца Y_D. Возникшие в разных узлах а, они могут иметь разные или одинаковые следующие узлы d. В первом случае они разрешаются, а во втором могут привести к конфликтам второго типа в узлах d, эти конфликты разрешаются другим способом с помощью дополнительного мультикольца Z_M. Других вариантов возникновения конфликтов нет, что позволяет утверждать, что построенное 3-мерное р-ичное мультикольцо с 7(р-1) симплексными кольцами является неблокируемой сетью, для которой предложена процедура локальной динамической самомаршрутизации; это мультикольцо в каждом узле имеет (фиг. 7) выходные дуги X_O от абонентов, входные дуги Y_I, Z_I к абонентам и дуги Y_M, Y_D, Y_R и Z_M между коммутаторами.

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

Приведем алгоритм динамической локальной самомаршрутизации при прокладке прямых путей в 3-мерном р-ичном мультикольце (параметры маршрута m₂^*, m₃^*, m₂^#, m₃^# вычисляются как было описано выше; в конкретной реализации, например, с использованием метода "червоточины" маршруты для всех N узлов НСС сети прокладываются параллельно).

1. Если m₁=0, то путь прокладывается по локальной дуге в узле s от процессора-источника к коммутатору. Переход к п. 3.

Если m₁>0, то путь прокладывается от процессора-источника в узле s по дуге X_O(m₁) к коммутатору узла а. Переход к п. 2.

2. Если m₃=0 и m₂=0, то путь прокладывается по локальной дуге в узле а от коммутатора к процессору-приемнику. Конец алгоритма.

3. Если m₂=0 и m₃≠0, то путь прокладывается по дуге Z_I(m₃) от коммутатора узла а к процессору в узле с. Конец алгоритма.

Если m₂≠0 и m₃=0, то путь прокладывается по дуге Y_I(m₂) от коммутатора узла а к процессору-приемнику в узле с. Конец алгоритма.

Если m₃>0 и m₂>0, то проверяется наличие конфликта на дуге Y_M(m₂).

Если конфликта нет, то путь прокладывается по дуге Y_M(m₂) от коммутатора узла а к коммутатору узла b. Переход к п. 4.

Если на дуге Y_M конфликт имеет место, то путь прокладывается по уникальной для узла дуге Y_D(m₁) от коммутатора узла а к коммутатору узла d. Переход к п. 5.

4. Путь прокладывается по дуге Z_I(m₃) от коммутатора узла b к процессору в узле-приемнике с. Конец алгоритма.

5. Проверяется конфликтность пути по дуге Y_R(m₂^*).

Если конфликта нет, то путь прокладывается по дуге Y_R(m₂^*) к коммутатору узла b m₁≥m₂ или узла b^* при m₁<m₂. Переход к п. 6.

Если же конфликт на дуге Y_R имеет место, то переход к п. 7.

6. Путь прокладывается по Z_I(m₃^*) от коммутатора узла b или узла b^* к процессору в узле-приемнике с. Конец алгоритма.

7. Путь прокладывается по дуге Z_M(m₃^#) от коммутатора узла d к коммутатору узла е. Переход к п. 8.

8. Путь прокладывается по дуге Y_I(m₂^#) от коммутатора узла е к приемнику в узле с. Конец алгоритма.

Была проведена экспериментальная проверка неблокируемости предложенного 3-мерного р-ичного мультикольца. Была создана его имитационная модель, и в ней реализован алгоритм локальной динамической самомаршрутизации. Была проведена частотная проверка конфликтности алгоритма на произвольных перестановках пакетов. Измерялись частоты ƒ₁ и ƒ₂ возникновения перестановок с хотя бы одним конфликтом первого типа и второго типа (после разрешения первого) соответственно. На фиг. 14 приведены их величины для разных значений р.

Конечно, основной целью экспериментов было измерение частоты ƒ₃ возникновения каких-либо конфликтов после разрешения конфликтов первого и второго типов. Эксперименты проводились при каждом р для нескольких миллионов (до десяти) случайных перестановок. Во всех случаях было зафиксировано значение ƒ₃=0 (!). Последнее значение подтверждает с высокой степени достоверности неблокируемость рассмотренного мультикольца. Естественно, что полную достоверность дал бы перебор всех перестановок. Однако он практически нереализуем при р>5 даже на суперкомпьютерах. Поэтому он и не проводился даже при р<5 из-за неполноты достигаемого результата.

В заявке предложена новая структура системной сети в виде 3-мерного полного мультикольца на базе 2-мерных неблокируемых мультиколец с минимальным числом дуг. Предложенная структура обеспечивает возможность прокладки бесконфликтных путей посредством их локальной динамической самомаршрутизации в узлах мультикольца. Что позволяет передавать пакеты данных по прямым путям без задержки на их буферизацию в промежуточных узлах. Построенное мультикольцо имеет семерной набор из (р-1)-ой дуг, которые неравномерно распределены по его измерениям - одинарный набор в измерении X, четверной набор в измерении Y и двойной набор в измерении Z.

Сравним сложности 2-мерного и нового 3-мерного мультиколец при одинаковом числе узлов N₂=N₃. Поскольку N₂=p₂² и N₃=p₃³ то р₂=p₃^3/2. Сложность S₂ 2-мерного мультикольца задается как S₂=N₂p₂²=p₂⁴=р₃⁶. Сложность S₃ 3-мерного мультикольца задается (сложность внутриузлового коммутатора s=8р₃²) как S₃=8N₃p₃²=8р₃⁵. Поэтому S₂>S₃ при р₃>8. Таким образом, при одинаковом числе узлов переход от 2-мерного к 3-мерному мультикольцу не только увеличивает число узлов при любом р, но и уменьшает сравнительную сложность последнего при р>8.

Изобретение относится к построению неблокируемых самомаршрутизируемых системных сетей для многопроцессорных систем. Технический результат заключается в расширении арсенала средств. Неблокируемость на произвольной перестановке пакетов означает возможность их параллельной передачи от источников к приемникам по прямым каналам, что повышает быстродействие системы. При построении сети используется топология трехмерного p-ичного мультикольца, позволяющая строить сеть с большим числом узлов по сравнению с сетями в виде двумерных p-ичных мультиколец. При этом трехмерное мультикольцо представлено композицией двух неблокируемых двумерных мультиколец с добавлением необходимого числа избыточных колец, достаточных для бесконфликтной передачи пакетов на их произвольной перестановке. Мультикольцо имеет семерной набор из (р-1)-й дуг, которые неравномерно распределены по трем его измерениям - одинарный набор в измерении X, четверной набор в измерении Y и двойной набор в измерении Z. Коммутаторы узлов сети в процессе установления соединений для передачи пакетов используют семь параметров маршрута, загружаемых процессорами в заголовки пакетов при их передаче, либо четыре из них могут быть вычислены коммутаторами в процессе установления соединений. 1 з.п. ф-лы, 14 ил.

1. Способ организации системной сети в виде неблокируемого самомаршрутизируемого трехмерного p-ичного мультикольца, характеризующийся тем, что каждый i-й узел из N=p³ узлов, пронумерованных от 1 до N, соединяют 3-мя группами симплексных линий передачи сетевых пакетов, соответствующих 3-м измерениям мультикольца, с m узлами, номера которых вычисляют по формулам i+m, i+mp, i+mp² соответственно в первом, втором и третьем измерениях, значение m равно 0, 1, 2, …, р-1 и задает номер линии в группе (где р - натуральное число), при этом каждый узел включает процессор с 2р входами и р выходами, а также коммутатор с 5(р-1)+1 входами и 6(р-1)+2 выходами, соединяемых семью группами линий, а именно группой линий X_O в первом измерении, группами линий Y_I, Y_M, Y_D, Y_R во втором измерении и группами линий Z_I, Z_M в третьем измерении,

причем р линий группы X_O прокладывают с р выходов процессора i-го узла на входы р коммутаторов соответствующих m узлов,

р линий группы Y_I прокладывают с р выходов коммутатора i-го узла на входы р процессоров соответствующих m узлов,

р линий группы Z_I прокладывают с р выходов коммутатора i-го узла на входы р процессоров соответствующих m узлов,

р-1 линий групп Y_M, Y_D, Y_R, Z_M прокладывают на входы р-1 коммутаторов соответствующих m узлов, номера которых вычисляют при m=1, 2, …, р-1, а именно,

р-1 линий группы Y_M прокладывают с р-1 выходов коммутатора i-го узла на входы р-1 коммутаторов соответствующих m узлов,

р-1 линий группы Y_D прокладывают с р-1 выходов коммутатора i-го узла на входы р-1 коммутаторов соответствующих m узлов,

р-1 линий группы Y_R прокладывают с р-1 выходов коммутатора i-го узла на входы р-1 коммутаторов соответствующих m узлов, причем в данной группе при вычислении номера следующего узла значения m задают с отрицательным знаком, то есть i-mp,

р-1 линий группы Z_M прокладывают с р-1 выходов коммутатора i-го узла на входы р-1 коммутаторов соответствующих m узлов;

при этом внутри каждого коммутатора организуют полнокоммутаторные связи от входов X_O к выходам Y_I, Z_I и Y_M, от входов Y_M к выходам Z_I, от входов Y_D к выходам Y_R и Z_M, от входов Y_R к выходам Z_I, от входов Z_M к выходам Y_I и прямые связи от входов X_O к выходам Y_D, а выбор соединений для передачи сетевых пакетов устанавливают посредством коммутатора независимо от других узлов с учетом параметров маршрута в заголовке пакета и наличия конфликтов на линиях групп Y_M и Y_R следующим образом:

параметры кратчайшего маршрута m₁, m₂, m₃ в заголовке пакета, сформированном процессором, при отсутствии конфликтов задают три этапа прокладки прямого пути пакетом, а именно, узел-источник передает пакет по линии X_O(m₁) в следующий узел сети, коммутатор которого передает пакет без буферизации по линии Y_M(m₂) в следующий узел сети, коммутатор которого передает пакет без буферизации по линии Z_I(m₃) в узел-приемник;

если коммутатор обнаруживает конфликт при передаче пакета на линию Y_M(m₂), то он устанавливает соединение для передачи этого пакета на линию Y_D(m₂), причем параметр m₂ берется равным параметру m₁ (то есть номеру линии X_O(m₁), по которой коммутатор получает пакет);

если коммутатор не обнаруживает конфликт при передаче пакета с входа Y_D(m₂) на линию Y_R(m₂^*), то он устанавливает соединение для передачи этого пакета на линию Y_R(m₂^*) с номером m₂^*=m₂-m₁ при m₁≥m₂ или на линию Y_R(m₂^*) с номером m₂^*=m₂-m₁-р при m₁<m₂;

если коммутатор обнаруживает конфликт при передаче пакета с входа Y_D(m₂) на линию Y_R(m₂^*), то он устанавливает соединение для передачи этого пакета на линию Z_M(m₃^#) с номером m₃^#=m₃-1 при m₁≥m₂ или на линию Z_M(m₃^#) с номером m₃^#=m₃ при m₁<m₂;

если коммутатор получает пакет по линии Y_R(m₂^*), то передает его в узел-приемник по линии Z_I(m₃^*) с номером m₃^*=m₃ при m₁≥m₂ или по линии Z_I(m₃^*) с номером m₃^*=m₃+1 при m₁<m₂;

если коммутатор получает пакет по линии Z_M(m₃^#), то передает его в узел-приемник по линии Y_I(m₂^#) с номером m₂^#=m₂-m₁+р при m₁≥m₂ или по линии Y_I(m₂^#) с номером m₂^#=m₂-m₁ при m₁<m₂.

2. Способ по п. 1, характеризующийся тем, что номера запасных линий m₂^*, m₃^*, m₂^#, m₃^# для передачи пакета в случае конфликтов вычисляют в процессорах узлов и загружают в заголовки пересылаемых пакетов наряду с параметрами кратчайшего маршрута m₁, m₂, m₃, при этом коммутаторы узлов устанавливают соединения с использованием уже вычисленных номеров запасных линий, полученных в заголовках пакетов.