Efficient multiple multicasting in hypercubes

Given k sets of processors (k > 1), G₁, G₂,..., G_k, each with a unique source, multiple multicasting requires to send message from each source to all the processors in its set. This problem can be solved by calling a (unique) multicasting algorithm k times, each for one set of processors, which requires a total time of O(knN) in a hypercube of N = 2ⁿ processors with existing hypercube multicasting algorithms. This paper proposes an efficient algorithm of time complexity O(nN) for solving this problem in the hypercube when Σ^k _i=1 |G_i| = O(N). The algorithm is designed with the heuristics to minimize the maximum number of hops, amount of traffic and degree of message multiplexing. Experimental results show that the algorithm has a good performance and produces satisfactory multicasting layout.