Y. Li, S. Peng, and W. Chu (Japan)
Interconnection networks, hypercube, disjoint paths, faulttolerance
A new interconnection network with low-degree for very large parallel computers called metacube (MC) has been introduced recently. The MC network has short diameter similar to that of the hypercube. However, the degree of an MC network is much lower than that of a hypercube of the same size. More than one hundred of millions of nodes can be connected by an MC network with up to 6 links per node. The MC network has 2-level cube structure. An MC(k,m) network that connects p = 2m2k+k nodes with m+k links per node has two parameters, k and m, where k is the dimension of the high-level cubes (class-cubes) and m is the dimension of the low-level cubes (clusters). In this paper, we describe an efficient algorithm for finding disjoint paths in MC networks. We show that, for any two distinct nodes u and v in an MC(k,m), k +m disjoint paths from u to v can be found in O(log2 p) time. The length of the paths is at most H(s,t) + 2k + m + 5, where H(s,t) is the Hamming distance between s and t. The result implies that a fault-free path between any two nonfaulty nodes can be found in an MC(k,m) with up to m+k -1 faulty nodes.
Important Links:
Go Back
