The Container Problem in a Torus-connected Cycles Network

AbstractIn the last few years, parallel processing systems have been studied very actively, and, given the huge number of computing nodes now involved in modern supercomputers, many topologies have been proposed to efficiently connect all these CPUs. A torus and its variants are such topologies popular as interconnection networks of massively parallel systems. Torus-connected cycles (TCC) have been introduced recently, building on the interesting properties or tori and enabling nodes clustering. In this paper, we present an algorithm that solves the container problem in a TCC. This problem consists in finding mutually node-disjoint paths between any pair of nodes. In a T CC(k, n), the proposed algorithm finds paths of lengths at most [k/2]n2 + ([k/2] + 4)n − 3 in O(n3 + kn2) time. Lastly, an empirical evaluation is conducted to inspect the practical behaviour of this algorithm