Balanced generalized hypercubes: Optimal communication algorithms

In this paper three communication algorithms are proposed for two types of generalized hypercube multiprocessor. The algorithms are intended to Solve three intensive communication problems: complete broadcast, single-node sca tter and total exchange. The algorithms achieve both the time and transmiss ion complexity bounds for the three problems on the balanced generalized hy percube (BGHC). The BGHC is a w(d)-node network with w nodes along each of the d dimensions. These communication algorithms are performed based on a b alanced spanning tree, called a compatible tree, which can be used to solve any of the tree problems. Several theoretical results related to the compa tible tree and then the sufficient and necessary condition for concurrent t ransmissions are presented. The concurrent condition ensures the maximum us e of network bandwidth so that the optimal bounds are achieved. It is shown that the proposed scheduling algorithms achieve the optimal bounds for any w and d.