MULTICAST IN HYPERCUBE MULTIPROCESSORS

An efficient interprocessor communication mechanism is essential to the performance of hypercube multiprocessors. All existing hypercube multiprocessors basically support one-to-one interprocessor communication only. However, multicast (one-to-many) communication is highly demanded in executing many data parallel algorithms. A multicast algorithm should attempt to inform each destination in a minimum number of time steps while generating a least amount of traffic. In this paper, we first propose a graph theoretical model, the Optimal Multicast Tree (OMT), for interprocessor communication in distributed-memory multiprocessors. The problem of finding an OMT is conjectured to be NP-hard even for hypercube multiprocessors. A heuristic Greedy multicast algorithm which guarantees a minimized message delivery time is proposed. Simulation results show that the performance of the Greedy algorithm is very close to the optimal solution. Routing of multicast messages is done in a distributed manner. The hardware design of a VLSI router which supports all types of communications is briefly discussed. © 1990.