VVQ: Virtualizing Virtual Channel for Cost-Efficient Protocol Deadlock Avoidance

Deadlock freedom is a critical component of interconnection networks in large-scale systems. In particular, protocol or high-level deadlock can occur from dependency based on network endpoints. Virtual channels (VCs) are commonly used to avoid such protocol deadlocks in large-scale systems; however, the cost of VCs is high in large-scale networks because of the deep input buffers and VCs need to be replicated. In this work, we propose to virtualize virtual channels to create Virtualizing Virtual Queues (VVQ) buffer architecture. VVQ is based on the observation that a FIFO buffer organization is sufficient when protocol deadlocks do not occur. However, when potential protocol deadlock can occur through blocking, VVQ takes a proactive approach to allow packets from different traffic classes to "jump" the queue and ensure protocol deadlock does not occur. Our proposal shows how a ghost pointer can be leveraged to enable such buffer organization without introducing complex buffer management such as dynamic buffer organizations. Our evaluations show VVQ can match the performance of the baseline VC buffer organization with only half of the total buffer storage.