When multiple applications run concurrently on a many-core platform, RCA considers the status of nodes belonging to other applications, which couples the behaviors of different applications, and negatively affects the application performance. Similarly to the NoP design, a dedicated congestion information network is leveraged. proposed the regional congestion awareness (RCA) design to select the output port on the basis of the status of all routers along the same column or row. The NoP design leverages a sideband network to deliver congestion status for two-hop-away routers. selected the output port on the basis of the status of routers next to neighboring routers. The neighbors-on-path (NoP) design proposed by Ascia et al. uses dedicated wires to convey neighboring router status, and then forwards packets to either the X or the Y dimension according to the congestion status. Hu and Marculescu proposed the DyAD design, which adaptively applies deterministic or adaptive routing according to the network loads.Īvoiding network congestion requires routing algorithms to be efficiently aware of network status. Lookahead routing calculates at most two available output ports one hop ahead, and then the preselection scheme selects the appropriate port one cycle before the arrival of the packet. proposed a fully adaptive routing algorithm which utilizes lookahead routing and the port preselection scheme for low latency.

The fully adaptive routing allows the packet to use all minimal paths between the source and destination nodes thus, it supports higher path diversity than partially adaptive and deterministic routing. further proved that the escape VCs in Duato's theory can apply aggressive VC reallocation without inducing deadlock, which can further improve the performance.Īchieving high performance requires the routing algorithm to provide high path diversity and to avoid network congestion. proved the deadlock-free property of the WPF scheme, which was also verified by Verbeek and Schmaltz with the decision procedure method. proposed the whole packet forwarding (WPF) flow control scheme, which extends Duato's theory to allow multiple packets to be stored in one VC. Our group conducts research to address the limitation of Duato's theory. Since most NoC packets are short, this requirement strongly limits the performance. Duato's theory requires each VC to hold at most one packet for wormhole fully adaptive routing. This theory has been widely used for about 20 years in several industrial products, including the Cray T3E and IBM Blue Gene series. Duato's theory was a great breakthrough it allows the cyclic channel dependency for high routing flexibility. This theory can be used to design deterministic or partially adaptive routing algorithms.ĭuato introduced the concept of the routing subfunction, and indicated that a routing subfunction with an acyclic channel dependency graph is the sufficient condition for deadlock-free fully adaptive routing. Dally and Seitz proposed the seminal deadlock avoidance theory, which declares that an acyclic channel dependency graph is the sufficient condition for deadlock freedom. Designing the routing algorithm based on some deadlock avoidance theories is the general way to guarantee deadlock freedom. Guaranteeing deadlock freedom and achieving high performance are two primary objectives for unicast routing designs. In Networks-On-Chip, 2015 1.4.2 Research on unicast routing

Deadlock computer science