Avoiding request–request type message-dependent deadlocks in networks-on-chips

• The first theoretical work on the request–request type message dependent deadlock.
• We prove that using virtual channels could avoid such type of deadlock.
• We prove that finding the minimum number of virtual channels is NP-complete.
• We propose an integer linear programming based algorithm to solve this problem.
• Our work achieved the lowest latency, compared against two existing methods.

When an application is running on a network-on-chip (NoC)-based multiprocessor system-on-chip (MPSoC), two types of deadlocks may occur: (i) the routing-dependent deadlocks, and (ii) the message-dependent deadlocks. The former type of deadlocks can be avoided by removing any cyclic paths on the application’s channel dependency graph. The message-dependent deadlocks, caused by mutual dependency of different control and/or data messages, on the other hand, are very complicated to deal with. In this paper, we focus our study on the request–request type message-dependent deadlocks which may appear in a peer-to-peer streaming system. This type of deadlocks can have devastating effects on applications using streaming protocols that often demands real-time processing over continuous data streams. We show that request–request type of deadlocks can be avoided by proper inclusion of virtual channels (VCs) for the links along the selected routing path. These VCs are not bounded to a particular communication path. Instead, they can be shared among multiple existing communication flows. In this paper, we have formally proved a sufficient condition that determines the minimum number of VCs actually needed for each link of a communication flow such that, request–request type message-dependent deadlocks can be completely avoided. Following this sufficient condition, we propose a path selection and minimum VC allocation (PSMV) algorithm to help determine the minimum number of non-uniform VCs for each link. The PSMV algorithm consists of two major steps. In the first step, we attempt to minimize the maximum number of VCs among all the links. This problem is NP-complete in nature, and it is solved using the proposed mixed integral linear programming (MILP)-based algorithm. In the second step, based on the solution suggested in the first step, the minimum number of VCs for each link is finally determined. The PSMV algorithm can literally be integrated with any existing application mapping algorithm to provide deadlock-free mapping results. One such deadlock-free mapping algorithm is suggested in this paper. Our experiments also show that, compared to an existing flow control based deadlock avoidance method (CTC) and a deadlock recovery method (DR), increase of buffers size in PSMV is within 5% compared to a baseline network configuration. The message latency of PSMV is the lowest among all three designs.