Routing in circulant graphs based on a virtual coordinate system

Abstract

This article explores routing methods in two-dimensional circulant graphs where each vertex is linked to four neighboring ones. The unique symmetries of the circulant graph make it a viable topology for high-performance computing devices, such as networks-on-chip and cluster supercomputers. It was shown that the coordinates of the vertices can be determined as the minimum number of transitions along the generators from the initial vertex. Two virtual coordinate-based routing methods were developed. The first method entails restoring the vertex numbers and finding the difference between them, with the coordinates of the corresponding vertex setting the route. The second method involves calculating the difference between the final and initial vertex coordinates, while minimizing the route based on the proposed algorithm.

Keywords

• сirculant graph
• network-on-chip
• supercomputer cluster
• virtual coordinate-based routing