Previous [1] [2] [3] [4] [5] [6] [7] [8]

Journal of Inforamtion Science and Engineering, Vol.11 No.2, pp.249-274 (June 1995)
Embeddings and Communication Algorithms in
Faulty Hypercubes

Jin-Kun Wang
System Development Center
Chung Shan Institute of Science and Technology
P.O.Box 90008-16-17
Lung-Tan, Tao-Yuan, Taiwan, R.O.C.

A study of hypercube algorithms reveals that in many cases the parallel computations that require local communication are achieved by topologies such as linear arrays and 2-D meshes, and that the computations which require global data communication are accomplished by hypercube interconnection. When one or more nodes and /or links of a hypercube fail, it is still possible to communicate and embed such topologies for most distributions of faulty processors and/or links. Most algorithms proposed for reconfiguration find hypercubes of lower dimension, which reduces the number of processors utilized by at least a half, unless hardware redundancy is incorporated. In this paper, embedding and global data communication schemes, such as global sum, global broadcast and global exchange, are developed for faulty hypercubes and studied in the context of algorithms. The algorithms proposed increase processor utilization by assuming that each node of a hypercube has a direct-connect hardware (DCH), and that the links and the DCH's are fault-free. The schemes are also applicable to incomplete hypercubes resulting from the allocation of subcubes to different users.

Keywords: linear array embedding, 2-D mesh embedding, global data communication, hypercube topology, parallel algorithms

Received November 10, 1993; revised December 9, 1994.
Communicated by Chuan-lin Wu.