Avoiding request–request type message-dependent deadlocks in networks-on-chips | |
Wang xiaohang; Liu peng; Yang mei; Jiang yingtao | |
刊名 | PARALLEL COMPUTING
![]() |
2013 | |
英文摘要 | 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 |
收录类别 | SCI |
原文出处 | http://www.sciencedirect.com/science/article/pii/S0167819113000689 |
语种 | 英语 |
内容类型 | 期刊论文 |
源URL | [http://ir.siat.ac.cn:8080/handle/172644/5292] ![]() |
专题 | 深圳先进技术研究院_南沙所 |
作者单位 | PARALLEL COMPUTING |
推荐引用方式 GB/T 7714 | Wang xiaohang,Liu peng,Yang mei,et al. Avoiding request–request type message-dependent deadlocks in networks-on-chips[J]. PARALLEL COMPUTING,2013. |
APA | Wang xiaohang,Liu peng,Yang mei,&Jiang yingtao.(2013).Avoiding request–request type message-dependent deadlocks in networks-on-chips.PARALLEL COMPUTING. |
MLA | Wang xiaohang,et al."Avoiding request–request type message-dependent deadlocks in networks-on-chips".PARALLEL COMPUTING (2013). |
个性服务 |
查看访问统计 |
相关权益政策 |
暂无数据 |
收藏/分享 |
除非特别说明,本系统中所有内容都受版权保护,并保留所有权利。
修改评论