Two New Multicast Algorithms in 3D Mesh and Torus Networks

Performance of a multicomputer largely depends on that of the underlying network communications such as multicast, which is essential for processors in multicomputer to exchange data and messages. Two major parameters used to evaluate multicast routing are the time it takes to deliver the message to all destinations and the traffic which refers to the total number of links involved. Direct network especially mesh connected is the most popular network topology used in multicomputer because its scalability. It has been proved that, in mesh network, it is NP-hard to find the multicast routing which is optimal on both time and traffic. In this paper, we proposed two efficient multicast algorithms designed for store and-forward switched mesh-connected multicomputers, called DIAG and DDS. Both algorithms are tree-based shortest path multicast algorithms with total complexity of O(KN) or less. Performance evaluations of these algorithms for 3D mesh and torus is presented at the end of the paper.