Previous [ 1 ] [ 2 ] [ 3 ] [ 4 ] [ 5 ] [ 6 ] [ 7 ] [ 8 ] [ 9 ] [ 10 ] [ 11 ]


Journal of Information Science and Engineering, Vol. 20 No. 1, pp. 39-55 (January 2004)

Constructing Fault-Tolerant Communication Trees in Hypercubes*

Po-Jen Chuang, Shih-Yuan Chen and Juei-Tang Chen
Department of Electrical Engineering
Tamkang University
Tamshui, 251 Taiwan

A communication tree is a binomial tree embedded in a hypercube, whose communication direction is from its leaves to its root. If a problem to be solved is first divided into independent subproblems, then each subproblem can be solved by one of the hypercube processors, and all the subresults can be merged into the final results through tree communication. This paper uses two random search techniques, the genetic algorithm (GA) and simulated annealing (SA), to construct fault-tolerant communication trees with the minimum data transmission time. Experimental evaluation shows that, with reasonably low search time, the proposed GA and SA approaches are able to find more desirable communication trees (i.e., trees with less data transmission time) than the minimal cost approach can. A distributed approach which applies parallel search to communication subtrees in disjoint subcubes is also provided to reduce the search time of the proposed approaches.

Keywords: fault-tolerant communication trees, hypercubes, genetic algorithms, simulated annealing, data transmission time, search time, maximal fault-free subcubes

Full Text () Retrieve PDF document (200401_04.pdf)

Received January 31, 2003; accepted July 4, 2003.
Communicated by Shiuh-Pyng Shieh.
* A preliminary version of this paper has been presented at the 2002 International Computer Symposium, 2002.