Результат интеллектуальной деятельности: СПОСОБ ПОСТРОЕНИЯ НЕБЛОКИРУЕМОГО САМОМАРШРУТИЗИРУЕМОГО РАСШИРЕННОГО КОММУТАТОРА

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

Необходимость объединения коммутаторов в сеть, или построение расширенного коммутатора, объясняется большим (существенно превышающим количество входов выпускаемых интегральных схем) количеством абонентов, участвующих в обмене информацией в многопроцессорных системах. Известны, например, сборки неблокируемых самомаршрутизируемых коммутаторов с топологией двумерного обобщенного гиперкуба (Scott S.. Abts D., Kirn J., and Dally W. The black widow high-radix Clos network // Proc. 33^rd Intern. Symp. Comp. Arch. (ISCA'2006). 2006. // http://cva.stanford.edu/people/jikl2/isca06.pdf.), с топологией мультикольца (Подлазов B.C. Условия неблокируемости мультикольцевых коммутаторов и обобщенных гиперкубов на произвольных перестановках. // Автоматика и телемеханика. 2001. №8. - С.118-126), с топологией неполных уравновешенных блок-схем (УБС) (Подлазов B.C., Соколов В.В. Схемотехника однокаскадных коммутаторов большой размерности // Датчики и системы. 2006. №9. С.12-17). Структурные схемы этих коммутаторов представлены на фиг.1-3. Все они состоят из входного каскада демультиплексоров (на схеме представлены нижним рядом треугольников), хребтового каскада коммутаторов (на схеме представлены рядом прямоугольников) и выходного каскада мультиплексоров (на схеме представлены верхним рядом треугольников) и отличаются видом соединения каскадов. Перечень связей между устройствами каскадов задается таблицей соединения T_b.

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

Известен способ технически неограниченного расширения числа входов сети коммутаторов, предложенный Клозом, когда в качестве базовых коммутаторов могут быть использованы также и сети коммутаторов. Кроме того, коммутатор, построенный таким иерархическим способом, проще одноуровневого коммутатора с таким же количеством входов (Бенеш В.Е. Математические основы теории телефонных сообщений. // М.: Связь. 1968. С.83-150., Богданов А.В. и др. Архитектуры и топологии многопроцессорных вычислительных систем. // М.: Интернет-университет информационных технологий - ИНТУИТ.ру. 2004. Лекции №9, №10).

Коммутатор Клоза, фиг.4, может быть построен в качестве альтернативы для прямоугольного коммутатора с (r×m) входами и (r×m) выходами. Он формируется из трех каскадов коммутаторов: r коммутаторов (m×m) во входном каскаде, r коммутаторов (m×m) в выходном и m промежуточных коммутаторов (r×r). Таблица соединения каскадов описывается следующим образом:

- j-й выход i-ого коммутатора входного каскада соединен с i-ым входом j-ого промежуточного коммутатора;

- j-й вход k-ого коммутатора выходного каскада соединен с k-ым выходом j-ого промежуточного коммутатора.

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

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

Возможность построения коммутаторов неблокируемых самомаршрутизируемых коммутаторов разной топологии весьма важна, так как кроме основного эффекта неблокируемости и самомаршрутизируемости они обладают дополнительными функциональными возможностями. Имея различную топологию, каждый из приведенных выше коммутаторов имеет преимущественную область применения: коммутаторы с топологией двумерного обобщенного гиперкуба, фиг.5, при размещении сборки коммутаторов на плате; коммутаторы с топологией мультикольца, фиг.6, при сборке распределенных коммутаторов, например, в стойке в условиях ограничения места на прокладку кабелей; а коммутаторы с топологией УБС требуют минимальной площади для разводки соединений при размещении коммутатора на кристалле СБИС. При сборке коммутаторов последнего типа имеется также возможность задавать количество параллельных маршрутов для каждой пары абонентов.

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

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

Технический результат достигается тем, что предложен новый способ построения неблокируемого самомаршрутизируемого расширенного коммутатора R×R из неблокируемых самомаршрутизируемых базовых коммутаторов K×K (K<R), заключающийся в том, что к хребтовому каскаду, состоящему из N базовых коммутаторов, добавляют входной и выходной каскады коммутаторов, подсоединяемых к хребтовому каскаду в соответствии с определенной таблицей соединений, отличающийся тем, что в качестве входного и выходного каскадов используют соответственно R демультиплексоров 1×m и R мультиплексоров m×1; подсоединение демультиплексоров и мультиплексоров к хребтовому каскаду производят с использованием выбранной для построения расширенного коммутатора базовой таблицы соединения T_b неблокируемого самомаршрутизируемого коммутатора N_b×N_b, задающей подсоединение входного каскада N_b демультиплексоров 1×m_b к входам каскада M_b коммутаторов k_b×k_b и выходов этого каскада к выходным каскадам N_b мультиплексоров m_b×1, и с соблюдением условий KN=Rm, K=hk_b, R=hN_b, N=M_b, m=m_b; подсоединение демультиплексоров и мультиплексоров к хребтовому каскаду производят следующим образом: первые k_b входов (выходов) всех N базовых коммутаторов подсоединяют к первым N_b из R демультиплексоров (мультиплексоров) точно в соответствии с T_b, следующие k_b входов (выходов) всех N малых коммутаторов подсоединяют к следующим N_b из R демультиплексоров (мультиплексоров) в соответствии с T_b, в которой все номера демультиплексоров и мультиплексоров увеличены на N_b и так далее, увеличивая для очередной группы k_b входов (выходов) всех N базовых коммутаторов номера демультиплексоров (мультиплексоров) на N_b в откорректированной на предыдущем шаге таблице T_b, пока не будет разведена последняя h-ая группа k_b входов (выходов) всех N малых коммутаторов на последние N_b из R демультиплексоров (мультиплексоров). Для построения неблокируемого самомаршрутизируемого расширенного коммутатора R×R с топологией неполных уравновешенных блок-схем (УБС), в котором значение N_b=m_b(m_b-1)/σ+1 и M_b=N_bm_b/k_b, из неблокируемых самомаршрутизируемых базовых коммутаторов K×K (К<R) используют базовую таблицу соединений T_b, полученную из таблицы, описывающей неполную уравновешенную блок-схему B(N, M, m, k, σ) (Холл М. Комбинаторика // Главы 10-12. Мир, М., 1970, 424 С.), заменой М блоков блок-схемы на M_b коммутаторов k_b×k_b и N элементов блок-схемы на N_b демультиплексоров 1×m_b входного каскада и N_b мультиплексоров m_b×1 выходного каскада. Для построения неблокируемого самомаршрутизируемого расширенного коммутатора R×R с топологией мультикольца, в котором значение N_b=M_b=m², k_b=m_b из неблокируемых самомаршрутизируемых малых коммутаторов K×K (K<R) используют базовую таблицу соединений T_b для однотактного мультикольца, полученную следующим образом: каждый из N_b узлов однотактного мультикольца состоит из демультиплексора 1×m_b, коммутатора k_b×k_b и мультиплексора m_b×1; для каждого узла один выход демультиплексора соединен с входом коммутатора того же узла, остальные выходы разведены по входам коммутаторов остальных узлов соответственно топологии однотактного мультикольца, один вход мультиплексора соединен с выходом коммутатора того же узла, остальные входы соединены с выходами коммутаторов остальных узлов соответственно топологии однотактного мультикольца. Для построения неблокируемого самомаршрутизируемого расширенного коммутатора R×R с топологией обобщенного гиперкуба, в котором значение N_b=M_b=m², k_b=m_b из неблокируемых самомаршрутизируемых малых коммутаторов K×K (K<R) используют базовую таблицу соединений T_b для однотактного обобщенного гиперкуба, полученную следующим образом: все с одинаковыми номерами входы коммутаторов k_b×k_b каждой строки решетки коммутаторов m_b×m_b разведены на демультиплексор с тем же номером из k_b демультиплексоров 1×m_b, все с одинаковыми номерами выходы коммутаторов k_b×k_b каждого столбца матрицы коммутаторов m_b×m_b разведены на мультиплексор с тем же номером из k_b мультиплексоров m_b×1. Для построения неблокируемого самомаршрутизируемого расширенного коммутатора с топологией УБС с R дуплексными входами из неблокируемых самомаршрутизируемых базовых коммутаторов с К дуплексными входами (K<R) используют хребтовый каскад из N коммутаторов с К дуплексными входами и R дуплексных демультиплексоров-мультиплексоров 1×m; подсоединение демультиплексоров-мультиплексоров к хребтовому каскаду производится с использованием выбранной для построения большого коммутатора базовой таблицы соединения T_b неблокируемого самомаршрутизируемого коммутатора с топологией УБС с N_b дуплексными входами, задающей подсоединение входного каскада N_b дуплексных демультиплексоров-мультиплексоров 1×m_b к входам каскада N_b коммутаторов с k_b дуплексными входами. При использовании базовых коммутаторов, обеспечивающих прием только своих пакетов, во входном каскаде вместо демультиплексоров используют простые умощнители сигнала, а в случае применения построенного коммутатора только для перестановочной коммутации вместо мультиплексоров в выходном каскаде используют схемы ИЛИ. При многошаговом (неограниченном) расширении входов коммутатора на каждом шаге расширения используют в качестве базового коммутатора расширенный коммутатор, полученный на предыдущем шаге, при этом для расширения топологических возможностей построенного коммутатора на каждом новом шаге расширения применяют необходимую базовую таблицу соединения.

На фиг.1 приведена структура неблокируемого самомаршрутизируемого коммутатора с топологией двумерного обобщенного гиперкуба.

На фиг.2 приведена структура неблокируемого самомаршрутизируемого коммутатора с топологией однотактного мультикольца.

На фиг.3 приведена структура неблокируемого самомаршрутизируемого коммутатора с топологией неполных уравновешенных блок-схем.

На фиг.4 приведена структура коммутатора Клоза.

На фиг.5 и 6 приведены топологические схемы двумерного обобщенного гиперкуба и мультикольца.

На фиг.7 приведена структура неблокируемого самомаршрутизируемого дуплексного коммутатора с топологией неполных уравновешенных блок-схем.

На фиг.8 приведена схема коммутатора 8×8, иллюстрирующая этапы построения коммутаторов предлагаемым способом.

В таблицах 1-5 приведены примеры таблиц соединений, используемых при построении коммутаторов предлагаемым способом.

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

Таблица соединений T_b для коммутатора с топологией УБС, изображенного на фиг.3, представлена в табл.1.

В строках таблиц T_b номера коммутаторов, в столбцах левой и правой части таблицы соответственно входы и выходы коммутаторов, а в каждой клетке левой и правой части таблицы вписаны соответственно номера абонентов-источников и номера абонентов-приемников, подсоединенных через соответствующие демультиплексоры и мультиплексоры. Базовые таблицы определяют топологию коммутаторов N_b×N_b, собранных на M_b коммутаторах k_b×k_b с N_b демультиплексорами 1×m_b и N_b мультиплексорами m_b×1. В случае использования элементов с дуплексными входами таблица T_b вырождается в таблицу, в которой левая и правая часть совпадают, а в клетках вписаны номера дуплексных абонентов, подсоединенных через соответствущие двунаправленные демультиплексоры-мультиплексоры. Пример такой таблицы приведен в табл.2, а соответствующая структура коммутатора с двунаправленными связями, соответствующая неполной уравновешенной блок-схеме (УБС) B (7, 7, 3, 3, 1) (Холл М. Комбинаторика // Главы 10-12. Мир, М., 1970, 424 С.) представлена на фиг.7. Как видно, такой коммутатор имеет два каскада, при этом первый каскад осуществляет передачу данных как от абонентов к коммутаторам хребтового каскада, так и обратно.

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

Фактически процесс соединения каскадов, описанный в Формуле, производится по таблице соединений расширенного коммутатора, состоящей из h скорректированных базовых таблиц T_b, покрывающих M_b коммутаторов K×K. Величина h определяется из отношения K/k_b, где k_b - количество входов коммутатора, описанного базовой таблицей. В j-ой копии T_b (2≤j≤h) номера подсоединенных абонентов увеличиваются по сравнению с 1-ой копией на (j-1)N без изменения мест их подсоединения. Поэтому полученный расширенный коммутатор R×R объединяет R=hN_b абонентов, что в N_b/k_b больше, чем в исходном К×К. При этом соблюдаются следующие условия: KN=Rm, K=hk_b, R=hN_b, N=M_b, m=m_b.

В табл.3 в качестве примера приведена таблица соединений расширенного коммутатора c R×R=21×21, собранного из 7 полных коммутаторов 9×9 (N=7, K×K=9×9), образующих хребтовый каскад, с помощью базовой таблицы T_b дуплексного коммутатора с топологией УБС B(N, M, m, k, σ)=B(7,7,3,3,1), приведенной выше в табл.2. Параметры базовой таблицы N_b=M_b=7, k_b=m_b=3. В табл.3 цветом выделены три копии базовой таблицы, h=3. Заданные выше условия соблюдаются.

Рассмотрим пример двухшагового наращивания входов коммутатора с топологией УБС, построенного из дуплексных коммутаторов k_b×k_b=2×2 и дуплексных демультиплексоров-мультиплексоров 1×3 (m_b=3). Схема построенного дуплексного коммутатора R×R=8×8 с топологией УБС представлена на фиг.8. Исходные коммутаторы 2×2 на схеме изображены в виде прямоугольников, а демультиплексоры-мультиплексоры 1×3 изображены в виде треугольников.

Используем для построения базовую таблицу T_b, соответствующую блок-схеме B (4, 6, 3, 2, 1), приведеную в табл.4.

После первого шага применения предложенного способа, то есть однократного (h=1) применения T_b, получаем коммутатор 4×4 с топологией УБС, обведенный на фиг.8 штриховой линией. Этот коммутатор состоит из шести пронумерованных коммутаторов 2×2 и четырех демультиплексоров-мультиплексоров 1×3, в нумерации которых вторая цифра указывает номер шага, его входы пронумерованы от 1 до 4.

На втором шаге, взяв шесть, полученных на первом шаге, коммутаторов 4×4 в качестве хребтового каскада (на схеме они обозначены К1_2-К6_2, вторая цифра указывает номер шага) и используя ту же базовую таблицу, получаем расширенный коммутатор 8×8, схема соединения которого представлена в табл.5. Дуплексные порты этого коммутатора пронумерованы от 1 до 8.

Таблица соединений полученного коммутатор имеет в основе две копии (h=2) базовой таблицы. Для наглядности на фиг.8 две группы демультиплексоров-мультиплексоров 1×3, используемые на втором шаге, разнесены, чтобы проиллюстрировать два этапа разводки двух копий базовой таблицы согласно предлагаемому способу построения расширенного коммутатора при N_b=4 и h=2.

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

При такой маршрутизации входной демультиплексор на выходе из абонента должен направлять кадр в необходимый коммутатор. При этом демультиплексор может сам выбирать этот коммутатор по номеру выходного канала, заданному в кадре, или выбор кадра будет осуществляться в том коммутаторе, которому он предназначен. Во втором случае демультиплексор может быть заменен на простой умощнитель сигнала. При реализации перестановочных задач коммутации, когда каждый входной абонент подсоединяется только к одному выходному абоненту и пары вход-выход не имеют общих абонентов, выходной мультиплексор можно заменить на элемент ИЛИ. Если задача неперестановочная и на один выходной абонент претендуют несколько входных, то мультиплексор должен выполнять функцию множественного доступа в единственный выходной канал. Схемы, выполняющие эту функцию, могут иметь минимальную глубину (Подлазов B.C., Соколов В.В. Схемотехника однокаскадных коммутаторов большой размерности // Датчики и системы. 2006. №9. С.12-17).

Приведем еще один технический пример использования предложенного способа для расширения числа портов в известных многокаскадных сетях Клоза. Пусть, например, имеется самый большой доступный полный коммутатор на 64 порта. При традиционном расширении получим сеть Клоза на 2048 портов (Guide to myrinet-2000 switches and switch networks // http://www.myti.com/myrinet/m3switch/guide/). Используя таблицу соединения с топологией УБС при m=3, расширим коммутатор на 64 порта предложенным способом до однокаскадного коммутатора на 148 портов. Для этого потребуется плата с 7 коммутаторами. В результате число портов 3-каскадной сети Клоза, построенной из этих расширенных коммутаторов, увеличится с 2048 до 10952 портов и потребуется 314 таких плат. На втором шаге расширения, используя ту же таблицу соединения с топологией УБС при m=3, расширим коммутатор на 148 портов предложенным способом до однокаскадного коммутатора на 344 портов. Для этого потребуется модуль с 7 платами. В результате число портов 3-каскадной сети Клоза, построенной из этих модулей, увеличится до 59168 портов и потребуется 730 таких модулей. На третьем шаге расширения, используя ту же таблицу соединения с топологией УБС при m=3, расширим коммутатор на 344 порта предложенным способом до однокаскадного коммутатора на 952 портов. Для этого потребуется стойка с 7 модулями. В результате число портов 3-х каскадной сети Клоза, построенной из этих модулей, увеличится до 453152 портов и потребуется 2020 таких стоек.

Предложенный способ объединения коммутаторов в сеть или наращивания портов коммутатора обладает следующими преимуществами:

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

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

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

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