Маршрутизация в циркулянтных графах на основе виртуальной координатной системы

Ученые записки Казанского университета. Серия: Физико-математические науки. 2023. Т. 165. № 3. С. 282–293.

Сухов А. М., Романов А. Ю., Глушак Е. В.

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

Ключевые слова: supercomputer clusters, сеть на кристалле, network-on-chip, суперкомпьютерный кластер, циркулянтный граф, сirculant graph, virtual coordinate-based routing, маршрутизация на основе виртуальной координатной системы