MCAR: Non-local adaptive Network-on-Chip routing with message propagation of congestion information

Congestion occurs frequently in Networks-on-Chip (NoC) when the packet demands exceed the capacity of network resources. Non-local adaptive routing algorithms utilize the congestion information of both local and distant links to decide the output link selection, which can greatly improve the network performance. The existing non-local adaptive routing algorithms have two mechanisms to propagate the congestion information of distant links. One of mechanism is to increase additional wires/clusters. The other mechanism is to embed the propagated information in packet headers. This paper proposes a new non-local adaptive routing algorithm called MCAR. In MCAR, two special kinds of messages are used to propagate the congestion information of distant links across the network without introducing additional wires/clusters and leading to a better timeliness of congestion information. Moreover, MCAR efficiently utilizes the propagated information to decide the output link selection. Experimental results on both synthetic traffic patterns and application traces show that MCAR achieves better saturation throughput (5.84% on average) and smaller power consumption (7.58% on average) than a state-of-the-art adaptive routing algorithm.