A parallel multi-unit resource deadlock detection algorithm with O(log₂(min(<i>m</i>, <i>n</i>))) overall run-time complexity

作     者：Xiao, Xiang Lee, Jaehwan John 

作者机构：IUPUI Purdue Sch Engn & Technol ECE Dept Indianapolis IN 46202 USA 

出 版 物：《JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING》 (并行与分布式计算杂志)

年 卷 期：2011年第71卷第7期

页      面：938-954页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：Division of Computing and Communication Foundations Direct For Computer & Info Scie & Enginr Funding Source: National Science Foundation 

主　　题：Deadlock detection Deadlock detection in hardware Multi-unit resource systems Chip multiprocessor Graph traversing Reachability computation Parallel algorithm Digital logic design RTOS Real-time embedded systems 

摘      要：Current MPSoCs typically consist of less than a dozen processing units. Future MPSoCs are likely to integrate many more. With this trend, dozens of applications can be running on an MPSoC concurrently and application deadlock on MPSoCs will become a severe problem. To address the application deadlock problem in current and future MPSoCs, this article proposes a parallel multi-unit resource deadlock detection algorithm, incorporating four contributions: (1) a classification of resource events that enables each category of events to be handled efficiently, (2) a parallel node hopping mechanism that explores the entire graph exponentially in parallel to obtain information about reachable processes of every resource, (3) an innovative hardware implementation of the node hopping mechanism using bit-wise computations, and (4) proofs of correctness and run-time complexity of the proposed algorithm. Based on information about reachable processes as well as sink nodes in the graph, the proposed algorithm detects deadlock in O(1) run-time. Compared with the worst case run-time of any previous algorithm, which employs a single scheme to handle all resource events, ours is considerably reduced to O(log(2)(min(m, n))) when implemented in hardware, where m and n are the number of processes and resources, respectively. (C) 2011 Elsevier Inc. All rights reserved.