A Multicast Path Algorithm on Hypercube Interconnection Networks

Multicast communication is one of the general patterns of collective communication in multiprocessors. On hypercube network, the optimal multicast path problem is NP-hard and all existing multicast path algorithms are heuristic. Aiming to reduce the communication traffic, we propose a new heuristic multicast path algorithm which consists of a preprocessing algorithm and a message routing algorithm. By simulation experiments, our multicast path algorithm has significant improvements in comparison to the existing algorithms.