System Development Center
Chung Shan Institute of Science and Technology
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.