An efficient deadlock-free multicast routing algorithm for mesh-based networks-on-chip

Multicast communication has been commonly used in multiprocessor systems. Current multicast routing methods such as tree-based and path-based approaches may suffer from the problem of multicast deadlocks or long routing delay. In this work we propose a hybrid multicast routing algorithm that combines the advantages of both path-based and tree-based methods. The proposed algorithm together with a router design that requires no additional virtual channel can achieve deadlock-free multicast routing. Very high routing efficiency is achieved by the proposed algorithm due to an adaptive routing strategy according to the traffic load. Experimental results show that the saturation point (in terms of injection ratio) of our algorithm is significantly higher than those of the state-of-the-art tree-and path-based multicast routing algorithms, while at the saturation points of these two algorithms, our algorithm has a routing latency that is 21% and 43% smaller than those of the tree-and the path-based algorithms, respectively.