A FAULT-TOLERANT TREE COMMUNICATION SCHEME FOR HYPERCUBE SYSTEMS

The tree communication scheme was shown to be very efficient for globa l operations on data residing in the processors of a hypercube with ti me complexity of O(log(2)N), where N is the number of processors. This communication scheme is very useful for many parallel algorithms on h ypercube multiprocessors. If a problem can be divided into independent subproblems, each subproblem can first be solved by one of the proces sors. Then, the tree communication scheme is invoked to merge the subr esults into the final results. All the algorithms for problems with th is property can benefit from the tree communication scheme. We propose a more general and efficient tree communication scheme in this paper. In addition, we also propose fault-tolerant algorithms for the tree c ommunication scheme, by exploiting the unique properties of the tree c ommunication scheme. The computation and communication slowdown is sma ll (< 2) under the effect of multiple link and/or node failures.