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

	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).