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

Document Type

Conference Proceeding

Publication Date

7-9-2010

Publication Title

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

Publisher

Institute of Electrical and Electronics Engineers

First page number:

93

Last page number:

97

Abstract

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.

Keywords

Coordinate measuring machines; Optimization; System recovery

Disciplines

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

Language

English

Comments

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

Permissions

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

Share

COinS