STUDY OF DEADLOCK-FREE WORMHOLE MULTICAST ROUTING STRATEGIES

Abstract

Performance study of deadlock-free wormhole multicast routing schemes in 2-D mesh multicomputers is a main focus of this dissertation. The issue of deadlocks due to dependencies on communication channels and buffers has been addressed in many previously proposed wormhole multicast algorithms. Deadlocks due to dependencies on consumption channels also a fundamental issue in the design of multicast algorithms for wormhole networks. These new channel dependencies produced by multicast messages are studied. These deadlocks can be resolved by providing multiple classes of consumption channels and restricting the use of consumption channels by multicast messages. The upper bounds for the number of consumption channels required to avoid deadlocks are determined by the routing strategy and network topology. Performance comparison of five multicast routing strategies viz. Individual multicasting, dual-path, multi-path, column-path, and e-mcast for 2-D mesh multicomputers are studied. All of the algorithms are shown to be deadlock-free. The simulation results shows that for multicast traffic, dual-path and multi-path offer lower message latencies while the column-path and e-mcast offer higher throughputs only at higher message latencies. Another result of study is that the commonly implemented simplistic scheme of sending one copy of a multicast message to each of, its destinations (Individual multicasting) exhibits good performance provided the number of destinations is small.