A. Bossard, K. Kaneko, and S. Peng (Japan)
metacube, hierarchical hypercube, interconnection network, polynomial algorithm, disjoint-path routing
The metacube interconnection network targeting large par allel computers has been introduced a few years ago. Keep ing its diameter short, similar to that of the hypercube, this network has a degree much lower than that of a hy percube of the same size. For example, with only 6 links per node, the corresponding metacube is able to connect more than one hundred of millions of nodes. We in troduce in this paper a routing algorithm for finding in a metacube MC(k, m) disjoint paths between one source node and a maximum of m + k destination nodes. We show that for any source node s, and any destination nodes D = {d1, . . . , dn}, n ≤ m + k, we can find n dis joint paths from s to di (1 ≤ i ≤ n) of maximal length (m2k + n)(k + 1) + k + 4 in O(nm2k (log n + k)) time complexity.
Important Links:
Go Back
