A fault-tolerant tree communication scheme for hypercube systems

Author

Leu, Yuhl-Rong ; Kuo, Sy-Yen

Author_Institution

Dept. of Electr. Eng., Nat. Taiwan Univ., Taipei, Taiwan

Volume

45

Issue

6

fYear

1996

fDate

6/1/1996 12:00:00 AM

Firstpage

641

Lastpage

650

Abstract

The tree communication scheme was shown to be very efficient for global operations on data residing in the processors of a hypercube with time complexity of O(log₂N), where N is the number of processors. This communication scheme is very useful for many parallel algorithms on hypercube multiprocessors. If a problem can be divided into independent subproblems, each subproblem can first be solved by one of the processors. Then, the tree communication scheme is invoked to merge the subresults into the final results. All the algorithms for problems with this 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 communication scheme, by exploiting the unique properties of the tree communication scheme. The computation and communication slowdown is small (<2) under the effect of multiple link and/or node failures

Keywords

computational complexity; fault tolerant computing; hypercube networks; parallel algorithms; fault-tolerant algorithms; fault-tolerant tree communication scheme; hypercube systems; parallel algorithms; time complexity; tree communication scheme; Application software; Broadcasting; Communication system control; Control systems; Fault tolerance; Fault tolerant systems; Hypercubes; Military computing; Parallel algorithms; Power system reliability;

fLanguage

English

Journal_Title

Computers, IEEE Transactions on

Publisher

ieee

ISSN

0018-9340

Type

jour

DOI

10.1109/12.506421

Filename

506421