DocumentCode :
1186089
Title :
A True O(1) Parallel Deadlock Detection Algorithm for Single-Unit Resource Systems and Its Hardware Implementation
Author :
Xiao, Xiang ; Lee, Jaehwan John
Author_Institution :
Dept. of Electr. & Comput. Eng., Indiana Univ.-Purdue Univ. Indianapolis, Indianapolis, IN, USA
Volume :
21
Issue :
1
fYear :
2010
Firstpage :
4
Lastpage :
19
Abstract :
Due to rapid technology advance, multiprocessor system-on-chips (MPSoCs) are likely to become commodity computing platforms for embedded applications. In the future, it is possible that an MPSoC is equipped with a large number of processing elements as well as on-chip resources. The management of these faces many challenges, among which deadlock is one of the most crucial issues. This paper presents a novel hardware-oriented deadlock detection algorithm suitable for current and future MPSoCs. Unlike previously published methods whose runtime complexities are often affected by the number of processing elements and resources in the system, the proposed algorithm leverages specialized hardware to guarantee O(1) overall runtime complexity. Such complexity is achieved by: 1) classifying resource allocation events; 2) for each type of events, using hardware to perform a set of specific detection and/or preparation operations that only takes constant runtime; and 3) updating necessary information for multiple resources in parallel in hardware. We implement the algorithm in Verilog HDL and demonstrate through simulation that each algorithm invocation takes at most four clock cycles.
Keywords :
concurrency control; hardware description languages; microprocessor chips; resource allocation; system-on-chip; Verilog HDL; commodity computing platforms; embedded applications; hardware-oriented deadlock detection algorithm; multiprocessor system-on-chips; resource allocation events classification; runtime complexity; single-unit resource systems; true O(1) parallel deadlock detection algorithm; Deadlock detection in hardware; resource allocation graph; single-unit resource systems; system-on-chips.;
fLanguage :
English
Journal_Title :
Parallel and Distributed Systems, IEEE Transactions on
Publisher :
ieee
ISSN :
1045-9219
Type :
jour
DOI :
10.1109/TPDS.2009.38
Filename :
4798157
Link To Document :
بازگشت