Conditional forwarding: simple flow control to increase adaptivity for fully adaptive routing algorithms

摘要

Fully adaptive routing algorithm has been widely used by modern commercial supercomputers due to its high path diversity. However, fully adaptive routing algorithm is prone to deadlock especially when wormhole switching with non-atomic virtual channel (VC) allocation is employed. Non-atomic VC allocation means that a VC can be immediately allocated once the tail flit of last packet arrives. Duato's theory gives a general methodology for deadlock-free fully adaptive routing design by dividing VCs into escape and adaptive ones, and prohibiting packets from using adaptive VCs after using escape VCs. However, this prohibition usually induces adaptivity loss and performance degradation. To address these issues, we extend Duato's theory and propose conditional forwarding flow control (CFFC): for packet residing in escape VC and requesting adaptive VC, it can be forwarded if the requested adaptive VC has enough free buffers to hold the whole packet. By allowing packets to regain adaptivity, CFFC enables the design of a fully adaptive routing algorithm with high routing adaptivity. By supporting non-atomic VC allocation, CFFC maintains efficient VC utilization. We prove that CFFC will not introduce deadlock if the routing algorithm is deadlock-free using non-atomic VC allocation, i.e. the routing subfunction applied in escape VCs is connected and deadlock-free. Simulation results show that our proposed method exhibits higher VC utilization and performs averagely 14.8% better than existing fully adaptive routing algorithms.