On the Torus Pairwise Disjoint-Path Routing Problem
Antoine Bossard, Keiichi Kaneko · 2018
Modern supercomputers are massively parallel systems: they include hundreds of thousands of processors. Processor connection is realised by the interconnection network of the system. In recent years, the torus topology has proven very popular as interconnection network: the Fujitsu K, IBM Blue Gene/L, IBM Blue Gene/P and Cray Titan supercomputers are examples of devices relying on this topology. In this paper, we address the fundamental problem of pairwise disjoint-path routing in a torus network. This problem is about selecting mutually node disjoint paths between given node pairs. Solving this problem has very important implications such as increased system dependability and more efficient data transfers. The correctness and complexities of the proposed routing algorithm to solve this problem are formally established. In an n-dimensional k-ary torus (n2c3).