Multicast in hypercube multiprocessors
Youran Lan, Abdol‐Hossein Esfahanian, Lionel Ming-shuan Ni · Rare & Special e-Zone (The Hong Kong University of Science and Technology) · 1994
Existing hypercube multiprocessors only support one-to-one interprocessor communication. However, multicast (one-to-many) communication is needed for executing many data-parallel algorithms. An optimal multicast algorithm should be able to minimize both the traffic generated and the time required to deliver a message. By modeling this problem as a graph-theoretical problem, the authors conjecture that the finding of an optimal solution is NP-hard. A heuristic greedy multicast algorithm which guarantees a minimized message delivery time is proposed. Routing of multicast messages is done in a distributed manner. Simulation results show that the greedy algorithm is very close to an optimal solution.