On Shortest Path Routing in Torus-Connected Cycles

Today, supercomputers are mainly based on interconnection networks that are high-performance topologies, used for connecting hundreds of thousands of nodes. Modern supercomputers are often based on torus interconnection networks because network scalability and topology simplicity are critical topological properties. Torus-connected cycles (TCC) is a topology that realizes the combination of a torus and rings. A TCC is an undirected graph of parameters the network dimension and arity, and distinguishes nodes by processor IDs and cluster IDs. In this paper, we first propose a shortest-path routing algorithm in a TCC of any dimension and arity. Then, we experimentally conduct comparative analysis and verifications of the proposed algorithm against conventional approach algorithms that were implemented to confirm that the selected paths are shorter (and shortest) and also the optimality of processing times. In addition, we quantitatively evaluate maximum shortest path lengths as obtained from the proposed routing algorithm. It is shown from the experimental results that, with respect to the proposed algorithm, the selected paths are almost always shortest and that processing times are competitive.