Efficient multiple multicasting in hypercubes

✍ Scribed by Hong Shen

• Book ID: 104426235
• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 488 KB
• Volume: 43
• Category: Article
• ISSN: 1383-7621
• DOI: 10.1016/s1383-7621(97)00016-7

✦ Synopsis

Given k sets of processors (k> 1). G,, G, ,..., G,, 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 Cf= , ] G, 1 = 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.