SEEC: stochastic escape express channel

Allocating a free buffer before moving to the next router is a fundamental tenet for packet movement in NoCs. Often, to solve head of line blocking and avoid deadlock, NoCs are provisioned with significant buffer resources in the form of virtual channels (VC) which consume area and power. We introduce stochastic escape express channels (SEEC) to enhance performance and avoid deadlock with dramatically fewer buffers than state-of-the-art NoCs. The network interfaces in SEEC periodically send special tokens called seekers to find packets destined for them and upgrade them to use a novel flow control called Free-Flow (FF). FF-packets traverse the network minimally from link to link, bypassing routers (bufferlessly) to the destination. As a result, FF-packets bypass regions of congestion in the NoC without needing more buffers. Furthermore, any deadlock that a FF-packet was originally involved in is guaranteed to break, without requiring turn restrictions or extra VCs. We also present an extension called multi-SEEC (mSEEC) that enables multiple simultaneous non-intersecting FF-packet traversals to enhance throughput further. We implement and evaluate SEEC and mSEEC on a mesh over a range of synthetic workloads and real applications and observe 34--40% reduction in average packet latency for real applications and 10--50% average improvement in throughput for synthetic traffic over the state-of-the-art at 1/6th the area/power budget.