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

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