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

@

Journal of Information Science and Engineering, Vol. 30 No. 4, pp. 1087-1093 (July 2014)


Time Optimal Node-to-Set Disjoint Paths Routing in Hypercubes


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(k3 + kn) time. We describe in this paper a smart improvement to this algorithm to reduce its time complexity from O(k3 + kn to O(kn)O(kn) which is time optimal.

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

Full Text () Retrieve PDF document (201407_09.pdf)

Received May 8, 2012; accepted November 15, 2012.
Communicated by Hee Kap Ahn.