Resolving Deadlocks for Pipelined Stream Applications on network-on-chips

Document Type

Conference Proceeding

Publication Date


Publication Title

2010 3rd IEEE International Conference on Computer Science and Information Technology, ICCSIT 2010


Institute of Electrical and Electronics Engineers

First page number:


Last page number:



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