Resolving deadlocks for pipelined stream applications on network-on-chips

Document Type

Conference Proceeding


When a stream application that demands real-time processing over continuous data streams 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. In this paper, we focus on the request-request type message-dependent deadlocks, the most devastating deadlocks in stream applications, and show that this type of deadlocks can be avoided by a proper inclusion of virtual channels (VCs). We first prove a sufficient condition that determines the minimum number of VCs needed to completely avoid request-request type message-dependent deadlocks. We then show that the problem of finding the minimum number of such VCs for a given application is NP-complete, and subsequently, a mixed integral linear programming (MILP)-based algorithm, referred as Min_VC algorithm, is introduced to solve this problem. This Min_VC algorithm can literally be integrated with any existing application mapping algorithm to provide deadlock-free mapping results. The experiments results shown that for typical stream applications, such as multimedia applications, the number of VCs needed to avoid deadlocks is fairly modest, typically just 1 or 2 depending on applications. That is, with a modest price paid in terms of area and power, stream applications can run in an NoC-based system completely free of deadlock concerns, which is necessary to deliver the quality of service (QoS) guarantee required by these applications.


Coordinate measuring machines; Optimization; System recovery


Controls and Control Theory | Electrical and Computer Engineering | Electrical and Electronics | Systems and Communications


Conference held: Chengdu, China, 9-11 July 2010


Use Find in Your Library, contact the author, or interlibrary loan to garner a copy of the item. Publisher policy does not allow archiving the final published version. If a post-print (author's peer-reviewed manuscript) is allowed and available, or publisher policy changes, the item will be deposited.

UNLV article access

Search your library