A MULTICAST ALGORITHM FOR HYPERCUBE MULTIPROCESSORS

Abstract

Efficient interprocessor communication is a key to the future success of large-scale multicomputers. Multicast communication, highly demanded in many scientific parallel algorithms, usually needs a large amount of communication traffic In this paper, our efforts are to alleviate the communication traffic of multicast in hypercubes. An optimal multicast algorithm in hypercubes should send a message from the source node to each of its destination nodes with a minimum number of hops while generating the least amount of total traffic Unfortunately, the problem to find optimal multicast communication in hypercubes is NP-complete. Therefore, we propose a heuristic multicast algorithm with time complexity O(nN) in n-dimensional hypercubes, where N= 2n, This algorithm is based on the virtual-circuited mode with centralized control. Our algorithm guarantees that each of the destination nodes can receive the source message through a shortest path from the source node. Compared with other heuristic algorithm, by simulation, our algorithm is shown to reduce communication traffic in multicast communication.