On Deadlock Problem of On-Chip Buses Supporting Out-of-Order Transactions

Modern on-chip communication protocols such as advanced eXtensible interface and open core protocol support advanced transactions to improve communication efficiency. Out-of-order transactions that allow responses to be returned in an order different from their request order play an important role in this improvement. However, a deadlock situation may occur if these transactions are not properly manipulated. In this paper, we address the deadlock problem in an on-chip bus system supporting out-of-order transactions. We present a graphic model that can well represent the status of a bus system and show that a cycle exists in the graph if and only if the bus system is in an unsafe state that may lead to a bus deadlock. Based on this model, we propose a novel bus design technique that can efficiently resolve the bus deadlock problem. Experimental results show that buses with the proposed technique can be up to 3.3 times faster than those with the currently available techniques.