A Hybrid Multicast Routing Approach with Enhanced Methods for Mesh-Based Networks-on-Chip

摘要

Multicast communication can greatly enhance the performance of Networks-on-Chip. Currently most multicast routing algorithms are either tree-based or path-based. The former has low latency but needs to solve multicast deadlocks through additional hardware resources. The latter can avoid deadlocks easily but may require long routing paths. In this paper we propose a hybrid multicast routing approach that combines the advantages of both path- and tree-based methods. The proposed approach ensures deadlock-free multicast routing without requiring additional virtual channels or large buffers to hold large packets. High routing performance is achieved using an adaptive routing strategy considering the traffic load in nearby routers. Two techniques, namely node balancing and path balancing, are further developed to enhance this hybrid routing algorithm. Extensive experiments with different buffer sizes, packet sizes and numbers of destinations per packet under random and Rent's rule traffic at various traffic injection rates have been conducted. The results show that the average latency of our approach is lower than previous multicast routing algorithms in most cases, and the saturation points of our approach are always at much higher injection rates.