Multicast algorithms for hypercube multi processors

Depending on different switching technologies, the multicast communication problem has been formulated as thr er different graph theoretical problems: the Steiner tree problem, the multicast tree problem. and the multicast pa th problem. Our efforts in this paper are to reduce the communication traff ic of multicast in hypercube multiprocessors. We propose three heuristic al gorithms for the three problem models. Our multicast path algorithm is dist ributed, our Steiner tree algorithm is centralized, and our multicast tree algorithm is hybrid. Compared with the previous results by simulation, each of our heuristic algorithms improves the communication traffic in the corr esponding multicast problem model. (C) 2001 Academic Press.