Efficient multicast routing algorithms for mesh-connected multicomputers

Multicast is a collective communication method in which a message is sent from a source to an arbitrary number of distinct destinations. Multicomputers refer to massively parallel computers that consist of thousands of processors built to handle computation intensive applications. Mesh is a kind of network topology widely used in multicomputers. Performance of multicomputers largely depends on that of the underlying network communications such as multicast, which is essential for processors 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. Research indicated that these two parameters are normally not independent, but contradict each other. It has been proved that traffic optimal multicast problems such as Optimal Multicast Path/Tree in mesh-connected network are NP-complete. Hence, it is NP-hard to find multicast routing which is optimal on both time and traffic. In this thesis, we proposed three efficient multicast routing algorithms for mesh-connected multicomputers: DIAG, DDS and XY-path, all of which have a small complexity of O(KN) or less. The DIAG and DDS are two tree-based shortest path multicast routing algorithms designed for store-and-forward switched mesh network, which obtained near optimal time and reduced traffic significantly over its predecessor VH algorithm. XY-path is a dual-path-based multicast routing algorithm intended for wormhole routed 2D mesh network, which reduced the time and traffic significantly over LIN's Hamiltonian path-based algorithm. Performance evaluations of these algorithms resulted from simulations are given at the end of the thesis