Fault-tolerant processor interconnection networks
Fault-tolerant processor interconnection networks
复制标题
容错处理器互连网络
DOI：
10.1002/scj.4690170803
复制
发表时间：
1986
期刊：
影响因子：
--
通讯作者：
Keiji Okada
中科院分区：
文献类型：
--
作者：
M. Imase;T. Soneoka;Keiji Okada
作为多处理器互连网络的合适拓扑结构，De Bruijn 图已经被提出，并且对其容错性进行了大量研究。 De Bruijn 图是一种有向图，具有最大度 d（可以连接到一个处理器的最大链路数）、直径 k（两个处理器之间的最大转发器数）和节点数 dk（处理器数）。 Kautz 图是最大度为 d、直径为 k、节点数为 dk + dk-1 的有向图。两者都具有最大度数 d 的图中最小的直径。本文证明： (1) 如果删除 De Bruijn 图中的 d -2 个节点（如果 d -2 个处理器故障），则其直径变为 d + 1，仅比原始直径大 1。 (2)考茨图中如果去掉d -3 个节点，则其直径变为k + 1，如果去掉d -1 个节点，则直径为k + 2或更小，最多比原始直径大2。 (3)在d度限制下，(1)和(2)的值最多比下界大1。 (4)容易实现容错路由算法。该算法比任何现有算法都要好，因为它的路径较短。
As suitable topology for interconnection networks of multiprocessors, De Bruijn graphs have been proposed and a number of investigations have been conducted on their fault tolerance. A De Bruijn graph is a directed graph with maximum degree d (the maximum number of links that can be connected to one processor), diameter k (maximum number of repeaters between two processors) and number of nodes dk (number of processors). A Kautz graph is a directed graph with maximum degree d, diameter k and number of nodes dk + dk-1. Both have the smallest diameter among the graphs with maximum degree d. This paper proves the following: (1) If d -2 nodes in a De Bruijn graph are removed (if d -2 processors are faulty), its diameter becomes d + 1, which is only 1 larger than the original diameter. (2) If d -3 nodes in a Kautz graph are removed, its diameter becomes k + 1 and if d -1 nodes are removed, the diameter is k + 2 or less, which is at most 2 larger than the original diameter. (3) The values of (1) and (2) are at most 1 larger than the lower bound under the limitation of degree d, (4) A fault-tolerant routing algorithm can be realized easily. This algorithm is better than any existing algorithm because of its short routes.