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.

Correctness is a first-order concern in the design of computer systems. For multiprocessors, a primary correctness concern is the deadlock-free operation of the network and its coherence protocol; furthermore, we must guarantee the continued correctness of the network in the face of increasing faults. Designing for deadlock freedom is expensive. Prior solutions either sacrifice performance or power efficiency to proactively avoid deadlocks or impose high hardware complexity to reactively resolve deadlocks as they occur. However, the precise confluence of events that lead to deadlocks is so rare that minimal resources and time should be spent to ensure deadlock freedom. To that end, we propose DRAIN, a subactive approach to remove potential deadlocks without needing to explicitly detect or avoid them. We simply let deadlocks happen and periodically drain (i.e., force the movement of) packets in the network that may be involved in a cyclic dependency. As deadlocks are a rare occurrence, draining can be performed infrequently and at low cost. Unlike prior solutions, DRAIN eliminates not only routing-level but also protocol-level deadlocks without the need for expensive virtual networks. DRAIN dramatically simplifies deadlock freedom for irregular topologies and networks that are prone to wear-related faults. Our evaluations show that on an average, DRAIN can save 26.73% packet latency compared to proactive deadlock-freedom schemes in the presence of faults while saving 77.6% power compared to reactive schemes.

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.

Every interconnection network must ensure, for its functional correctness, that it is deadlock free. A routing deadlock occurs when there is a cyclic dependency of packets when acquiring the buffers of the routers. Prior solutions have provisioned an extra set of escape buffers to resolve deadlocks, or restrict the path that a packet can take in the network by disallowing certain turns. This either pays higher power/area overhead or impacts performance. In this work, we demonstrate that (i) keeping one virtual-channel in the entire network (called 'Bindu') empty, and (ii) forcing it to move through all input ports of every router in the network via a pre-defined path, can guarantee deadlock-freedom. We show that our scheme (a) is topology agnostic (we evaluate it on multiple topologies, both regular and irregular), (b) does not impose any turn restrictions on packets, (c) does not require an extra set of escape buffers, and (d) is free from the complex circuitry for detecting and recovering from deadlocks. We report 15% average improvement in throughput for synthetic traffic and 7% average reduction in runtime for real applications over state-of-the-art deadlock freedom schemes.

Hardware caches balance fast lookup, high hit rates, energy efficiency, and simplicity of implementation. For L1 caches however, achieving this balance is difficult because of constraints imposed by virtual memory. L1 caches are usually virtually-indexed and physically tagged (VIPT), but this means that they must be highly associative to achieve good capacity. Unfortunately, excessive associativity compromises performance by degrading access times without significantly boosting hit rates, and increases access energy. We propose SEESAW to overcome this problem. SEESAW leverages the increasing ubiquity of superpages1- since super-pages have more page offset bits, they can accommodate VIPT caches with more sets than what is traditionally possible with only base page sizes. SEESAW dynamically reduces the number of ways that are looked up based on the page size, improving performance and energy. SEESAW requires modest hardware and no OS or application changes.

Deadlocks are a bane for network designers, be it a Network on Chip (NoC) in a multi-core or a large scale HPC/datacenter network. A routing deadlock occurs when there is a cyclic dependence between the buffers of network routers. Most modern systems avoid deadlocks by placing routing restrictions or adding extra virtual channels, in turn hurting performance and adding overhead respectively. In this work, we demonstrate that instead of placing such restrictions, we can, in fact, design routers to themselves guarantee deadlock-freedom, by (i) ensuring that every router always has at least one bubble (i.e., free buffer slot) at any input port, and (ii) this bubble pro-actively moves between input ports. We call this a Brownian Bubble Router (BBR). A BBR guarantees forward progress in any network topology, without requiring any routing restrictions or additional virtual channels. With our BBR design we provide 4× better throughput over state of art deadlock recovery schemes and 40% better throughput over traditional deadlock avoidance schemes in a 8×8 Mesh at negligible area and power overheads.