SWAP: Synchronized Weaving of Adjacent Packets for Network Deadlock Resolution
SWAP: Synchronized Weaving of Adjacent Packets for Network Deadlock Resolution
复制标题
DOI：
10.1145/3352460.3358255
复制
发表时间：
2019-10
期刊：
影响因子：
--
通讯作者：
Mayank Parasar;Natalie D. Enright Jerger;Paul V. Gratz;Joshua San Miguel;T. Krishna
中科院分区：
文献类型：
--
作者：
Mayank Parasar;Natalie D. Enright Jerger;Paul V. Gratz;Joshua San Miguel;T. Krishna
互连网络构成片上和片外系统的通信骨干。在网络中，拥塞导致报文被阻塞。如果存在循环依赖关系，则可能发生不确定的阻塞，从而导致死锁。所有现代网络都投入资源，通过消除循环依赖来避免死锁，或者检测死锁并从中恢复。传统的缓冲流控制不允许阻塞的数据包向前移动，除非保证下一跳的缓冲区是空闲的。我们介绍SWAP，这是一种新的机制，可以使阻塞的数据包与下一跳的缓冲数据包进行就地交换。我们证明就地交换足以打破任何死锁，并且与底层拓扑或路由算法无关。这使得SWAP适用于同构或异构的片内和片外拓扑。我们提出了SWAP的一个轻量级实现，它重用传统的路由器资源，并添加了少量内容来启用这些交换。与基于基线escape VC的解决方案相比，SWAP提供的额外路径分集在规则和不规则拓扑的综合流量模式下提供了20-80%的高吞吐量，与基于偏转和全局同步的解决方案相比，SWAP消耗的网络能量降低了2-8倍。
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.