DRAIN: Deadlock Removal for Arbitrary Irregular Networks
DRAIN: Deadlock Removal for Arbitrary Irregular Networks
复制标题
DOI：
10.1109/hpca47549.2020.00044
复制
发表时间：
2020-02
期刊：
影响因子：
--
通讯作者：
Mayank Parasar;Hossein Farrokhbakht;Natalie D. Enright Jerger;Paul V. Gratz;T. Krishna;Joshua San Miguel
中科院分区：
文献类型：
--
作者：
Mayank Parasar;Hossein Farrokhbakht;Natalie D. Enright Jerger;Paul V. Gratz;T. Krishna;Joshua San Miguel
在计算机系统设计中，正确性是首要考虑的问题。对于多处理器来说，主要的正确性问题是网络及其一致性协议的无死锁操作；此外，面对不断增加的故障，我们必须保证网络的持续正确性。为避免死锁而设计是昂贵的。以前的解决方案要么牺牲性能或功率效率来主动避免死锁，要么强加高硬件复杂性来在死锁发生时被动地解决死锁。然而，导致死锁的事件的精确汇合是非常罕见的，因此应该花费最少的资源和时间来确保不发生死锁。为此，我们提出了DRAIN，这是一种消除潜在死锁而无需显式检测或避免死锁的非主动方法。我们只是让死锁发生，并周期性地消耗（即强制移动）网络中可能涉及循环依赖的数据包。由于死锁很少发生，因此可以不频繁地以低成本执行排水。与以前的解决方案不同，DRAIN不仅消除了路由级别的死锁，还消除了协议级别的死锁，而不需要昂贵的虚拟网络。DRAIN极大地简化了不规则拓扑和容易出现磨损相关故障的网络的死锁自由度。我们的评估表明，在存在故障的情况下，与主动死锁自由方案相比，平均而言，DRAIN可以节省26.73%的数据包延迟，而与被动方案相比，可以节省77.6%的功率。
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.