More Web Proxy on the site http://driver.im/

article

An o(min(m, n)) parallel deadlock detection algorithm

Authors:

Jaehwan John Lee,

Vincent John Mooney, IIIAuthors Info & Claims

ACM Transactions on Design Automation of Electronic Systems (TODAES), Volume 10, Issue 3

Pages 573 - 586

https://doi.org/10.1145/1080334.1080341

Published: 01 July 2005 Publication History

Abstract

This article presents a novel Parallel Deadlock Detection Algorithm (PDDA) and its hardware implementation, Deadlock Detection Unit (DDU). PDDA uses simple Boolean representations of request, grant, and no activity so that the hardware implementation of PDDA becomes easier and operates faster. We prove the correctness of PDDA and that the DDU has a runtime complexity of O(min(m,n)), where m is the number of resources and n is the number of processes. The DDU reduces deadlock detection time by 99%, (i.e., 100X) or more compared to software implementations of deadlock detection algorithms. An experiment involving a practical situation with an early deadlock condition showed that the time measured from application initialization to deadlock detection was reduced by 46% by employing the DDU as compared to detecting deadlock in software.

References

[1]

AMIS. 2003. AMI Semiconductor. Available at http://www.amis.com/.

[2]

Coffman, E., Elphick, M., and Shoshani, A. 1971. System deadlocks. ACM Comput. Sur. 3, 67--78.

Digital Library

[3]

Coudert, O., Madre, J., and Fraisse, H. 1993. A new viewpoint on two-level logic minimization. In Proceedings of the 30th ACM Design Automation Conference. 625--630.

Digital Library

[4]

De Micheli, G. 1994. Synthesis and Optimization of Digital Circuits. McGraw-Hill, New York, NY.

Digital Library

[5]

DVT solutions. 2004. DVT solutions. Available at http://www.xilinx.com/esp/dvt/cdv/dvt_solutions/ip/dsp/.

[6]

Hennessy, J. and Patterson, D. 1996. Computer architecture---A Quantitative Approach. Morgan Kaufmann, San Francisco, CA.

Digital Library

[7]

Holt, R. 1972. Some deadlock properties of computer systems. ACM Comput. Sur. 4, 3 (Sept.), 179--196.

Digital Library

[8]

ITRS. 2004. The International Technology Roadmap for Semiconductors 2004. Available at http://public.itrs.net/.

[9]

Kim, J. and Koh, K. 1991. An o(1) time deadlock detection scheme in single unit and single request multiprocess system. In IEEE TENCON '91. 219--223.

[10]

Lee, J. 2004. Hardware/software deadlock avoidance for multiprocessor multiresource system-on-a-chip. Ph.D. thesis, School of ECE, Georgia Institute of Technology, Atlanta, GA.

Digital Library

[11]

Leibfried, T. 1989. A deadlock detection and recovery algorithm using the formalism of a directed graph matrix. Operat. Syst. Rev. 23, 2 (April), 45--55.

Digital Library

[12]

Maekawa, M., Oldhoeft, A., and Oldehoeft, R. 1987. Chapter 4 of Operating Systems---Advanced Concepts. Benjamin/Cummings Publishing Company, New York, NY.

Digital Library

[13]

McCluskey, E. 1959. Minimization of boolean functions. Bell Syst. Techn. J. 35, 1417--1444.

[14]

MG. 2004a. Mentor Graphics, Hardware/Software Co-Verification: Seamless. Available at http://www.mentor.com/seamless/.

[15]

MG. 2004b. Xray® Debugger. Available at http://www.mentor.com/xray/.

[16]

Morgan, S. 2000. Jini to the rescue. IEEE Spectrum 37, 4 (April), 44--49.

Digital Library

[17]

Shiu, P., Tan, Y., and Mooney, V. 2001. A novel parallel deadlock detection algorithm and architecture. In the 9th ACM International Workshop on Hardware/Software Co-Design. 73--78.

Digital Library

[18]

Shoshani, A. and Coffman, E. 1970. Detection, prevention and recovery from deadlocks in multiprocess, multiple resource systems. In 4th Annual Princeton Conference on Information Sciences and Systems.

[19]

Sun, D., Blough, D., and Mooney, V. 2002. Atalanta: a new multiprocessor RTOS kernel for system-on-a-chip applications. Tech. Rep. GIT-CC-02-19, College of Computing, Georgia Institute of Technology, Atlanta, GA.

[20]

Synopsys. 2004a. Design Compiler. Available at http://www.synopsys.com/products/logic/logic. html.

[21]

Synopsys. 2004b. VCS#8482; Verilog Simulator. Available at http://www.synopsys.com/products/simulation/simulation.html.

[22]

Xilinx. 2004. Xilinx. Available at http://www.xilinx.com/.

Cited By

Xiao XLee J(2008)A Novel O(1) Deadlock Detection Methodology for Multiunit Resource Systems and Its Hardware Implementation for System-on-ChipIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2008.5619:12(1657-1670)Online publication date: 1-Dec-2008
https://dl.acm.org/doi/10.1109/TPDS.2008.56
Xiao XLee J(2007)A Novel Parallel Deadlock Detection Algorithm and Hardware for Multiprocessor System-on-a-ChipIEEE Computer Architecture Letters10.1109/L-CA.2007.116:2(41-44)Online publication date: 1-Jul-2007
https://dl.acm.org/doi/10.1109/L-CA.2007.11
Xiao XLee J(2007)A novel O(1) parallel deadlock detection algorithm and architecture for multi-unit resource systems2007 25th International Conference on Computer Design10.1109/ICCD.2007.4601942(480-487)Online publication date: Oct-2007
https://doi.org/10.1109/ICCD.2007.4601942

Index Terms

An o(min(m, n)) parallel deadlock detection algorithm
1. Software and its engineering
  1. Software organization and properties
    1. Contextual software domains
      1. Operating systems
        Process management
        Deadlocks

Recommendations

A novel parallel deadlock detection algorithm and architecture
CODES '01: Proceedings of the ninth international symposium on Hardware/software codesign

A novel deadlock detection algorithm and its hardware implementation are presented in this paper. The hardware deadlock detection algorithm has a run time complexity of Ο_hw (min(m,n)), where m and n are the number of processors and resources, ...
A Priority Based Distributed Deadlock Detection Algorithm

Deadlock handling is an important component of transaction management in a database system. In this paper, we contribute to the development of techniques for transaction management by presenting an algorithm for detecting deadlocks in a distributed ...
Multithreaded test synthesis for deadlock detection
OOPSLA '14

Designing and implementing thread-safe multithreaded libraries can be a daunting task as developers of these libraries need to ensure that their implementations are free from concurrency bugs, including deadlocks. The usual practice involves employing ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Design Automation of Electronic Systems

ACM Transactions on Design Automation of Electronic Systems Volume 10, Issue 3

July 2005

156 pages

ISSN:1084-4309

EISSN:1557-7309

DOI:10.1145/1080334

Issue’s Table of Contents

Copyright © 2005 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Journal Family

ACM Journals for the Design of Smart and Connected Systems

Publication History

Published: 01 July 2005

Published in TODAES Volume 10, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tag

Deadlock detection

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
820
Total Downloads

Downloads (Last 12 months)6
Downloads (Last 6 weeks)0

Reflects downloads up to 28 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Xiao XLee J(2008)A Novel O(1) Deadlock Detection Methodology for Multiunit Resource Systems and Its Hardware Implementation for System-on-ChipIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2008.5619:12(1657-1670)Online publication date: 1-Dec-2008
https://dl.acm.org/doi/10.1109/TPDS.2008.56
Xiao XLee J(2007)A Novel Parallel Deadlock Detection Algorithm and Hardware for Multiprocessor System-on-a-ChipIEEE Computer Architecture Letters10.1109/L-CA.2007.116:2(41-44)Online publication date: 1-Jul-2007
https://dl.acm.org/doi/10.1109/L-CA.2007.11
Xiao XLee J(2007)A novel O(1) parallel deadlock detection algorithm and architecture for multi-unit resource systems2007 25th International Conference on Computer Design10.1109/ICCD.2007.4601942(480-487)Online publication date: Oct-2007
https://doi.org/10.1109/ICCD.2007.4601942

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents