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

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

Sukhov A., Romanov A., Глушак Е. В.

The article discusses routing methods in two-dimensional circulant graphs (each vertex is connected to four neighboring ones). The unique group of symmetries of the circulant graph makes it possible to use it as a topology for high performance computing devices, including networks-on-chip and cluster supercomputers. It is shown that the minimum number of transitions along the generators from the initial vertex can be used as the coordinates of the vertices. Two virtual coordinate-based routing methods have been developed. The first involves restoring the vertex numbers and finding the difference between them, the coordinates of the corresponding vertex set the route. The second method consists in finding the difference between the coordinates of the final and initial vertex and minimizing the route based on the proposed algorithm.

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