On the Torus Pairwise Disjoint-Path Routing Problem

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 (n <; k, k ≥ 5), the proposed algorithm connects c (≤ n) node pairs with mutually node disjoint paths of lengths at most 2k(c - 1) + n [k / 2], and the worst-case time complexity of the algorithm is O (nk
²
c
³
).