Fault-tolerant Routing in Metacube
Fault-tolerant Routing in Metacube
复制标题
Metacube 中的容错路由
DOI：
--
复制
发表时间：
2002
期刊：
影响因子：
--
通讯作者：
Wanming Chu
中科院分区：
文献类型：
--
作者：
Yamin Li;S. Peng;Wanming Chu
最近提出了一种新的用于超大型并行计算机的低度互连网络元立方体（MC）。MC网络具有类似于超立方体的短直径。然而，MC网络的度远低于相同大小的超立方体。MC网络可以连接超过一亿个节点，每个节点最多有6条链路。MC网络具有两级立方体结构。一个MC（k，m）网络连接2 m2 k +k个节点，每个节点有m+ k条链路，有两个参数k和m，其中k是高级立方体（类）的维数，m是低级立方体（簇）的维数。本文给出了MC网络中一个有效的容错路由算法。MC（k，m）网络中的容错路由问题是通过MC网络中的一种特殊结构--多通道立方体来解决的。为了构造多通道立方体中每个节点对的k条不相交路径，引入了一种称为签名的创新技术。
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 2 m2 k +k nodes with m+ k links per node has two parameters, k and m, where k is the dimension of the high-level cubes (classes) and m is the dimension of the low-level cubes (clusters). In this paper, we give an efficient algorithm for fault-tolerant routing in MC networks. The fault-tolerant routing problem in MC(k, m) is solved through a special structure in an MC network, called multi-channel cube. In order to construct k disjoint paths for each node pair in a multi-channel cube, an innovative technique, called signature, is introduced.