Efficient Deadlock Avoidance by Considering Stalling, Message Dependencies, and Topology
- 6 October 2025
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Computer Architecture Letters
- Vol. 24 (2) , 305-308
Abstract
Traditional schemes for avoiding deadlocks compose techniques for both protocol deadlocks (virtual networks) and network deadlocks (virtual channels). Recent work has shown how to use fewer virtual networks by analyzing protocol stalls instead of just considering the longest chain of causally dependent messages. We identify a shortcoming in this work, which can lead to deadlocks, and show that combining stall analysis with analyses of message dependencies and topology can avoid deadlocks while using fewer buffers than the conventional approach.Keywords
Funding Information
- NSF (CCF-200-2737, CCF-252-5271)
This publication has 9 references indexed in Scilit:
- Determining the Minimum Number of Virtual Networks for Different Coherence Protocols2024
- Pitstop: Enabling a Virtual Network Free Network-on-Chip2021
- DRAIN: Deadlock Removal for Arbitrary Irregular Networks2020
- SWAP2019
- Synchronized Progress in Interconnection Networks (SPIN): A New Theory for Deadlock Freedom2018
- Leaving One Slot Empty: Flit Bubble Flow Control for Torus Cache-Coherent NoCsIEEE Transactions on Computers, 2013
- Bubble coloring2013
- The Turn Model for Adaptive Routing2005
- Deadlock-Free Message Routing in Multiprocessor Interconnection NetworksIEEE Transactions on Computers, 1987