SWAP: Synchronized Weaving of Adjacent Packets for Network Deadlock Resolution
Lists
Only you see this
Abstract
An interconnection network forms the communication backbone in both on-chip and off-chip systems. In networks, congestion causes packets to be blocked. Indefinite blocking can occur if cyclic dependencies exist, leading to deadlock. All modern networks devote resources to either avoid deadlock by eliminating cyclic dependences or to detect and recover from it.Conventional buffered flow control does not allow a blocked packet to move forward unless the buffer at the next hop is guaranteed to be free. We introduce SWAP, a novel mechanism for enabling a blocked packet to perform an in-place swap with a buffered packet at the next hop. We prove that in-place swaps are sufficient to break any deadlock and are agnostic to the underlying topology or routing algorithm. This makes SWAP applicable across homogeneous or heterogeneous on-chip and off-chip topologies. We present a lightweight implementation of SWAP that reuses conventional router resources with minor additions to enable these swaps. The additional path diversity provided by SWAP provides 20-80% higher throughput with synthetic traffic patterns across regular and irregular topologies compared to baseline escape VC based solutions, and consumes 2-8× lower network energy compared to deflection and global-synchronization based solutions.
BibTeX
@inproceedings{parasar2019swap,
author = {Mayank Parasar and Natalie D. Enright Jerger and Paul V. Gratz and Joshua San Miguel and Tushar Krishna},
title = {{SWAP: Synchronized Weaving of Adjacent Packets for Network Deadlock Resolution}},
booktitle = {MICRO},
year = {2019},
doi = {10.1145/3352460.3358255},
}Loading related content...