Whole Packet Forwarding: Efficient Design of Fully Adaptive Routing Algorithms for Networks-on-Chip
Routing algorithms for Networks-on-Chip (NoCs) typically only have a small number of Virtual Channels (VCs) at their disposal. Limited VCs pose several challenges to the design of fully adaptive routing algorithms. First, fully adaptive routing algorithms based on previous deadlock-avoidance theories require a conservative VC re-allocation scheme: a VC can only be re-allocated when it is empty, which limits performance. The authors propose a novel VC reallocation scheme, Whole Packet Forwarding (WPF), which allows a non-empty VC to be re-allocated. WPF leverages the observation that the majority of packets in NoCs are short. They prove that WPF does not induce deadlock if the routing algorithm is deadlock-free using conservative VC re-allocation.