Deadlock-Free Multicast Routing Algorithm for Wormhole-Switched Mesh Networks-on-Chip

Abstract

An important service in distributed systems, as multi-processors, is the ability to transmit multicast messages. Cache coherence protocols and parallel algorithms are examples of applications requiring multicast messages. To transmit a multicast message to n targets, in networks-on-chip without multicast service, the source router must transmit n identical messages. Few works in the literature describe multicasting in NoCs. The goal of this work is to implement a deadlock free routing algorithm for wormhole-switched mesh NoCs, enabling to transmit simultaneous multicast messages. The dual-path multicast algorithm, used in multicomputers, is adapted to NoCs in this work. The dual-path multicast algorithm is implemented for circuit and packet switching. The evaluation comprises: (i) comparison between the algorithms; (ii) NoC performance as a function of the percentage of injected multicast messages; (iii) performance gains obtained with the dual-path algorithm when compared to the transmission of single unicast messages.