устройство и способ иерархической маршрутизации в многопроцессорных системах с ячеистой структурой

Формула изобретения

1. Способ иерархической маршрутизации пакета, содержащий этапы, на которых:

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

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

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

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

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

2. Способ по п.1, в котором множество прямоугольных областей содержит множество смежных прямоугольных областей.

3. Способ по п.1, в котором первый сегмент из множества сегментов обеспечивает изоляцию ресурсов от второго сегмента из множества сегментов.

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

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

6. Способ по п.1, дополнительно содержащий этап, на котором присваивают пакету идентификатор области назначения пакета и идентификатор узла назначения пакета внутри области.

7. Способ по п.6, дополнительно содержащий этапы, на которых:

присваивают узлу идентификатор области узла и идентификатор внутри области; и

сравнивают идентификатор области назначения пакета с идентификатором области узла для определения, достиг ли пакет области назначения.

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

9. Способ по п.1, дополнительно содержащий этапы, на которых:

проверяют идентификатор узла назначения пакета внутри области и идентификатор области назначения пакета;

сравнивают идентификатор области назначения пакета с идентификатором области узла для определения, достиг ли пакет области назначения;

в случае если пакет достиг области назначения, сравнивают идентификатор узла назначения пакета внутри области с идентификатором узла внутри области для определения, достиг ли пакет узла назначения.

10. Способ по п.1, в котором этап обеспечения маршрута по области содержит этап, на котором обеспечивают маршрут по области от исходного узла области внутри области назначения к узлу назначения области внутри области назначения.

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

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

13. Устройство иерархической маршрутизации пакета, содержащее:

ячеистую сеть, включающую в себя множество узлов;

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

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

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

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

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

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

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

19. Способ иерархической маршрутизации пакета, содержащий этапы, на которых:

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

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

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

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

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

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

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

Описание изобретения к патенту

Область техники, к которой относится изобретение

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

Уровень техники

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

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

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

Краткое описание чертежей

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

на фиг.1 показана примерная блок-схема устройства по одному варианту осуществления;

на фиг.2 представлена иллюстрация примеров непрямоугольных сегментов вместе с прямоугольными сегментами для одного варианта осуществления;

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

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

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

Подробное описание изобретения

На фиг.1 показан пример блок-схемы системы или устройства 100 в соответствии с одним вариантом осуществления. Устройство 100 может включать в себя ячеистую сеть 110, включающую в себя множество узлов. Каждый узел может представлять собой, например, связующий маршрутизатор, и узел может также включать в себя необязательный вычислительный элемент, такой как процессор. Устройство 100 может также включать в себя контроллер 140, подсоединенный к ячеистой сети 110, причем контроллер 140 имеет модуль 145 инициализации маршрутизации. Некоторые или все функции контроллера 140 и модуля 145 инициализации маршрутизации могут быть распределены между узлами ячеистой сети 110. Например, каждый узел может включать в себя модуль 147 локальной маршрутизации и управления. Контроллер 140 может быть выполнен с возможностью инициализации алгоритма маршрутизации для каждого из сегментов в зависимости от требований изоляции ресурсов сегмента. Модуль 145 инициализации маршрутизации может быть выполнен с возможностью разбиения ячеистой сети 110 на множество сегментов 120 и 130, каждый из которых включает в себя хотя бы один узел. Например, один сегмент 120 может включать в себя узлы 1, 2, 3, 11, 12 и 13. Модуль 145 инициализации маршрутизации может разделять первый сегмент 120 на множество прямоугольных областей 122, 124 и 126, где область 122 может включать в себя узел 11, область 124 может включать в себя узлы 1 и 12, а область 126 может включать в себя узлы 2, 3 и 13. Модули 147 локальной маршрутизации, расположенные в каждом узле, или модуль 145 инициализации маршрутизации могут определять маршрут по сегменту из исходной области 124 к области 126 назначения из множества прямоугольных областей 120. Модуль 145 инициализации маршрутизации или модули 147 локальной маршрутизации могут обеспечить маршрут по области из исходного узла 2 области в одной из множества прямоугольных областей до узла 3 назначения области в одной из множества прямоугольных областей. Модули 147 локальной маршрутизации или модуль 145 инициализации маршрутизации могут направлять пакет из исходного узла 1 внутри исходной области 124 в узел 3 назначения в области 126 назначения, используя маршрут по сегменту и маршрут по области.

Модуль 145 инициализации маршрутизации может разделить ячеистую сеть 110 для обеспечения возможности использования непрямоугольных сегментов, одновременно обеспечивая изоляцию ресурсов между, по меньшей мере, двумя сегментами 120 и 130. Модуль 145 инициализации маршрутизации может обеспечить маршрут по области путем обеспечения маршрута по области из исходного узла внутри каждой из множества прямоугольных областей 122, 124 и 126 к узлу назначения внутри каждой из множества прямоугольных областей 122, 124 и 126.

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

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

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

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

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

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

На фиг.2 показаны примеры прямоугольных и непрямоугольных сегментов 210, 220, 230 и 240 в соответствии с одним вариантом осуществления. Непрямоугольные сегменты может потребоваться рассматривать в случае внутренней или внешней фрагментации, вызванной строго прямоугольным выделением как в статических, так и динамических сценариях сегментации. Фрагментация может быть чрезвычайно высокой, если предполагается большой разброс в размерах сегментов. Стратегия выделения сегментов может быть менее строгой, если разрешено использование непрямоугольных сегментов, несмотря на предпочтительное использование прямоугольных. Когда предпочтительно использовать прямоугольные сегменты, выделение непрямоугольных сегментов может быть результатом остатков выделения одного или более прямоугольных сегментов. Примеры таких сегментов могут иметь форму букв C, U, E, H, L, T и т.п., как показано в элементах 210, 220, 230 и 240.

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

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

На фиг.3 примерно проиллюстрирован процесс 300 иерархической маршрутизации О-образного сегмента в соответствии с одним вариантом осуществления. Ограниченный непрямоугольный сегмент может быть образован из соединенных областей, таких как прямоугольные компоненты. Например, О-образный сегмент 310 может быть представлен как четыре прямоугольника 320, расположенных в виде кольца, где каждый из прямоугольников 30, 31, 32 и 33 граничит с двумя другими. Несколько таких компоновок соединенных прямоугольных компонентов и метки для них могут представлять любой заданный непрямоугольный сегмент. Такое размещение прямоугольных компонентов может быть задано для каждого непрямоугольного сегмента, для которого требуется построить алгоритм маршрутизации. В качестве дополнительного примера, О-образный сегмент 310 можно представить восемью прямоугольниками 325, организованными в кольцо, где каждый из прямоугольников 41-48 граничит с двумя другими. При размещении в виде показанных восьми прямоугольников передачу пакета требуется выполнять только в одном направлении, горизонтальном или вертикальном, в каждой из областей на пути к области назначения.

При иерархической маршрутизации для построения алгоритма маршрутизации конкретного непрямоугольного сегмента, каждый прямоугольный компонент 30, 31, 32 и 33 может рассматриваться как "суперузел". Суперузлы смежных прямоугольных компонентов могут быть соединены "суперребром". Данный непрямоугольный сегмент теперь может быть представлен соединенным суперграфом 330. Связующее дерево 340 может быть создано из суперграфа 330.

Принцип иерархической маршрутизации между парой из исходного узла и узла назначения может быть выполнен за два этапа. На первом этапе маршрут может быть выбран по пути от исходного суперузла к суперузлу назначения, используя маршрутизацию ВВЕРХ-ВНИЗ в связующем дереве суперграфа. Когда суперузел назначения будет достигнут, маршрутизация к узлу назначения происходит внутри прямоугольника того же компонента и может использовать любой исключающий тупики алгоритм маршрутизации по сетке. Для недопущения тупиков два этапа иерархической маршрутизации могут выполняться в отдельных виртуальных сетях. Каждый из этапов может быть независимо защищен от тупиков. Более того, этапы могут быть выполнены в строгой последовательности, когда на первом этапе, например, используют маршрутизацию вверх-вниз, а на втором этапе используют маршрутизацию внутри прямоугольного компонента назначения. Таким образом, алгоритмы маршрутизации, разработанные с использованием подхода иерархической маршрутизации, позволяют исключить тупики, потому что каждый из этапов исключает тупики, а маршрутизация выполнятся в отдельных сетях. Алгоритм может быть выражен следующим псевдокодом:

Обобщенная аппаратная реализация иерархической маршрутизации может быть возможна при наличии полных таблиц маршрутизации в каждом маршрутизаторе и одного дополнительного виртуального канала на каждый класс сообщений. В случае маршрутизатора, оптимизированного для покоординатной маршрутизации (DOR) или XY-маршрутизации, иерархическая маршрутизация может быть выполнена следующим образом. Каждый идентификатор узла может быть разделен на два независимых компонента: идентификатор области узла, например ID ячейки/прямоугольника, и идентификатор внутри области, такой как ID внутри ячейки или внутри прямоугольника. ID прямоугольников могут быть специфичными для сегментов. Идентификатор внутри прямоугольника может быть сделан таким же, как и глобальный ID узел, и, таким образом, как только сообщение достигнет своего прямоугольного компонента назначения, оно может использовать базовые данные DOR маршрутизации для получения маршрута к узлу назначения. Это позволяет поддерживать изоляцию ресурсов, используя как принятый по умолчанию алгоритм маршрутизации DOR для прямоугольных сегментов, так и иерархическую маршрутизацию для ограниченных непрямоугольных сегментов, где узел фактически расширен так, что он имеет ID прямоугольника. Может быть использован дополнительный бит, указывающий, следует ли использовать для маршрутизации принятую по умолчанию маршрутизацию или иерархическую маршрутизацию. Могут быть использованы частичные таблицы маршрутизации, а не полные. Размер таблиц частичной маршрутизации может быть равен максимальному количеству прямоугольных компонентов, поддерживаемых в ячеистой схеме взаимных соединений. Маршрутизаторы внутри непрямоугольного сегмента могут быть соответствующим образом запрограммированы, используя алгоритм иерархической маршрутизации для этого сегмента.

На фиг.4 показана примерная блок-схема 400 последовательности операций, иллюстрирующая последовательность операций иерархической маршрутизации в соответствии с одним из вариантов осуществления. Блок 410 является началом блок-схемы 400 последовательности операций. В блоке 420 блок-схема 400 последовательности операций может разделить ячеистую сеть узлов на множество сегментов, где каждый из сегментов содержит хотя бы один узел. Первый сегмент из множества сегментов может обеспечивать изоляцию ресурсов от второго сегмента из множества сегментов. Разделение ячеистой сети позволяет использовать непрямоугольные сегменты с одновременной возможностью изоляции ресурсов между любыми двумя сегментами.

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

В блоке 450 блок-схемы 400 последовательности операций можно обеспечить маршрут по области из исходного узла внутри одной из множества прямоугольных областей до узла назначения внутри той же области. Обеспечение маршрута по области может включать в себя обеспечение маршрута от исходного узла области внутри каждой из прямоугольных областей до узла назначения области внутри той же прямоугольной области. Обеспечение маршрута может так же включать в себя обеспечение маршрута по области от исходного узла внутри области назначения до узла назначения внутри области назначения. В блоке 460 блок-схемы 400 последовательности операций можно направить пакет из исходного узла внутри исходной области до узла назначения внутри области назначения, используя маршрут по сегменту и маршрут по области. Маршрутизация пакета может применять защиту от тупиков, направляя пакет из исходного узла внутри исходной области до узла назначения внутри области назначения, используя сначала исключающий тупики маршрут по сегменту, а потом исключающий тупики маршрут по области. В блоке 470 блок-схема 400 последовательности операций может заканчиваться.

На фиг.5 показана примерная блок-схема 500 последовательности операций порядка работы последовательности иерархической маршрутизации в соответствии с другой реализацией. В блоке 510 блок-схема начинается. В блоке 520 блок-схемы 500 последовательности операций можно присвоить пакету идентификатор области назначения пакета и идентификатор узла назначения пакета внутри области. В блоке 530 блок-схемы 500 последовательности операций узлу можно присвоить как идентификатор области узла, так и идентификатор внутри области. В блоке 540 блок-схемы 500 последовательности операций можно направить пакет между ячейками к следующему узлу на пути пакета к узлу назначения. В блоке 550 блок-схемы 500 последовательности операций можно проверить идентификаторы пакета и узла. В блоке 560 блок-схемы 500 последовательности операций можно сравнить идентификатор области назначения пакета с идентификатором области узла для определения, не равны ли они и не достиг ли пакет области назначения. Если идентификатор области назначения пакета и идентификатор узла назначения не равны, блок-схема 500 последовательности операций может направить пакет к следующему узлу в блоке 540.

Если идентификатор области назначения пакета равен идентификатору области узла назначения, то в блоке 565 блок-схемы 500 последовательности операций можно направить пакет внутри сетки к следующему узлу внутри области назначения. В блоке 570 блок-схемы 500 последовательности операций можно проверить идентификаторы пакета и узла. В блоке 575 блок-схемы 500 последовательности операций можно сравнить идентификатор узла назначения пакета внутри области с идентификатором узла внутри области для определения, не равны ли они и не достиг ли пакет узла назначения внутри области назначения. Если они не равны, блок-схема 500 последовательности операций может продолжить маршрутизацию пакета к следующему узлу в блоке 565. Если они равны, в блоке 580 блок-схемы 500 последовательности операций можно принять решение, что пункт назначения достигнут. В блоке 585 блок-схема 500 последовательности операций может закончиться.

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

Настоящее изобретение может также обеспечить алгоритм маршрутизации как методику корректного направления пакетов данных/сообщений от отправляющего узла во взаимосвязанной сети до узла назначения. Оно может относиться к алгоритму маршрутизации в двумерной сетке (2D-сетке) и в многомерной взаимосвязанной сети.

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

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

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

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

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

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