Previous | [ 1] | [ 2] | [ 3] | [ 4] | [ 5] | [ 6] | [ 7] | [ 8] | [ 9] | [ 10] | [ 11] | [ 12] | [ 13] | [ 14] | [ 15] | [ 16] | [ 17] | [ 18] | [ 19] |

¡@

ANTOINE BOSSARD AND KEIICHI KANEKO

*
Graduate School of Engineering
Tokyo University of Agriculture and Technology
Tokyo, 184-8588 Japan
*

Due to their simplicity, hypercubes are a popular topology for the interconnection
network of massively parallel systems. One critical issue when dealing with such parallel
systems is routing: data transmission is at the center of any operation or computation.
Additionally, as the number of processors inside modern supercomputers is huge, and
continuously growing, fault tolerance ought to be addressed. Hence, for a routing algorithm
to generating node-disjoint paths is of high interest as it maximises the probability
of establishing a fault-free path in a faulty environment. Also importantly, generating
disjoint paths allows for time-efficient data transmission; transfers are able to be realised
in parallel as two paths are ensured to share no common resource. In an n-dimensional
hypercube, given a source node and *k* (*k* < = *n*) destination nodes, Rabin described an algorithm
finding *k* node-disjoint paths between the source node and the destination nodes of
optimal lengths (at most *n* + 1) in *O*(*k*^{3} + *kn*) time. We describe in this paper a smart improvement
to this algorithm to reduce its time complexity from *O*(*k*^{3} + *kn* to *O*(*kn*)O(kn) which
is time optimal.

*
Keywords:
*
algorithms, time complexity, analysis, interconnection networks, parallel processing

Retrieve PDF document (**201407_09.pdf**)

Received May 8, 2012; accepted November 15, 2012.

Communicated by Hee Kap Ahn.