Optimal communication primitives on the generalized hypercube network

E cient interprocessor communication is crucial to increasing the performance of parallel computers. In this paper, a special framework is developed on the generalized hypercube, a network that is currently receiving considerable attention. Using this framework as the basic tool, a number of spanning graphs with special properties to t various communication needs, are constructed on the network. The importance of these spanning graphs is demonstrated with the development of optimal algorithms for four fundamen-tal communication problems, namely, the single node and multinode broadcasting and the single node and multinode scattering, on the generalized hypercube network. Broadcasting is the distribution of the same group of messages from a source processor to all other processors, and scattering is the distribution of distinct groups of messages from a source processor to each other processor. We consider broadcasting and scattering from a single processor of the network (single node broadcasting and scattering) and simultaneously from all processors of the network (multinode broadcasting and scattering). For the multinode broadcasting and scattering algorithms a special technique is developed on the generalized hypercube so that messages origi-nating at individual nodes are interleaved in such a manner that no two messages contend for the same edge at any given time. The communication problems are studied under the all-port communication assumption