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


Journal of Information Science and Engineering, Vol. 20 No. 4, pp. 707-732 (July 2004)

Distributed Fault-Tolerant Embedding of
Several Topologies in Hypercubes

Shih-Chang Wang, Yuh-Rong Leu and Sy-Yen Kuo+
Department of Electrical Engineering
National Taiwan University
Taipei, 106 Taiwan

Embedding is of great importance in the applications of parallel computing. Every parallel application has its intrinsic communication pattern. The communication pattern graph is mapped onto the topology of multiprocessor structures so that the corresponding application can be executed. To increase the reliability of parallel applications, fault-tolerant embedding is necessary. In this paper, we propose a distributed approach, based on the faulty link model, for embedding several topologies into hypercubes with faulty links and/or faulty nodes. The topologies include the ring, the torus, the binomial tree, and a hybrid topology which is a combination of rings and binomial trees. The approach exploits the recursive property of the hypercube, and the proposed algorithms all have of only O(n) parallel steps. Since the distribution of faulty links is arbitrary, an embedded graph with no faulty link may not exist. Therefore, we adopt a 2-phase fault-tolerance strategy to attack this problem. In the first phase, a near-perfect embedding is found, and in the second phase, existing fault-tolerant point-to-point communication schemes are employed. Based on the 2-phase strategy, applications with associated communication pattern graphs with the ring, torus, binomial tree, or hybrid topology can be executed on hypercube multiprocessors with faulty links. For faulty nodes, a technique called UDD (Uniform Data Distribution) is proposed. Therefore, with the UDD and the proposed algorithms, both faulty links and faulty nodes can be tolerated.

Keywords: fault-tolerant embedding, hypercube, ring, torus, binomial tree

Full Text () Retrieve PDF document (200407_07.pdf)

Received April 29, 2002; revised June 23, 2003; accepted August 14, 2003.
Communicated by Gen-Huey Chen.
* This research was supported by the National Science Council, Taiwan, under grant NSC 90-2213-E-002-113.