A Fault-Tolerant Tree Communication Scheme for Hypercube Systems

Yuh-Rong Leu and Sy-Yen Kuo

IEEE TRANSACTIONS ON COMPUTERS. VOL 45, NO 6, JUNE pp643-650 1996

Abstract

The communication scheme is very useful for many parallel algorithms on hypercube multiprocessors and benefit in the problem which be divided into independent subproblems, if each subproblem first be solved by one of the processors, the tree communication scheme merge the subresults into the final results. In this paper, We propose a more general and efficient tree communication scheme and fault-tolerant algorithms.

In various application, high reliability is often required, so fault tolerance is a important property of modern computer systems. Fault tolerance gives computer systems robustness and resistance against physical physical failures and operational faults.

We first assume that only link failures exist in the hypercube system and find fault-tolerant algorithms . Then, applied those algorithms to node failures. The approach has two phases. In the first phase, we devise an algorithm that can find a communication tree with as few faulty links as possible. The second run-time phase, the data messages are routed dynamically according to the link fault pattern in the communication tree. One of the advantages of our approach is that the tree communication scheme can still work even when a fault-tree does not exist.

2 Generalized Tree Communication Scheme

Fig.1 shows a feasible communication tree for a 4D hypercube. There are four communication stages. The labeling of nodes is on the binary reflective Gray codes. The arrow lines represent the directions of data flow.

Fig.3 We show two different communication trees for a 3D hypercude. The receiver of the last stage is defined as the sink. A communication can be determined by selecting a node as the sink and a dimension for the messages to traverse.

l Some definitions for the tree communication scheme.

The nodes sending data are active nodes, those receiving data are passive nodes, and the nodes doing nothing are idle.

l The rule check what a node at a certain stage depend on a node’s binary label

Theorem 1. There are n-i-1 nodes in ANi(v), where v is a node in Ai

ie. The number of active neighbors of an active node at stage I is n-i-1

3 FAULT-TOLEARNT TREE COMMUNICATION

SCHEME

A node can check if the links to its neighbors are faulty by sending test messages to its neighbors. Because each node has n neighbors, each node keeps an n-bit word FAULT to record the fault information.

A node is first selected to be the sink and the dimension order is then determined according to the fault pattern. This algorithm is shown.

We choose a node without any adjacent link failure as the sink.

We choose dimension j with minimal COST(j) as dj

We find out how many links adjacent to node u are faulty by counting the number of 1s in FAULT(u)

Fig 11 shows the relationship between sets USED_N, ~USED_D and neib(USED_N,~USED_D)

Theorem 4 The complexity of Algorithm FIND_TREE is O(N), where N is the number of nodes.

Run-Time Fault Tolerance of the Tree Communication Scheme is second step. Fig13 shows the algorithm FTTC(Fault-Tolerant Tree Communication)

Theorem 6 Algorithm FTTC is deadlock-free

4 Conclusions

We design those algorithm to detect link failures in a hypercube computer, to find a good communication tree in the presence of link failures, and to reroute messages in run-time. It also applies to node failures. The presented two-level fault-tolerance approach can enhance the reliability considerably with little performance degradation both in computation and communication.

Created by: NAN HSING CHANG

Date: June 9,1997