A Novel O (1) Parallel Deadlock Detection Algorithm and Architecture for Multi-unit Resource Systems

摘要

This paper introduces a novel O (1) parallel deadlock detection approach for multi-unit resource System-on-a-Chips (SoCs), inspired by Kim's method in O (1) detection as well as Shiu's method in parallel processing. Our contributions are (i) the first O (1) hardware deadlock detection and (ii) O (min (m, n)) preparation, both for multi-unit resource systems, where m and n are the number of processes and resources, respectively. O (min (m, n)), previously O (m×n), is achieved by performing all the searches for sink nodes for each and every resource in parallel in hardware over a matrix representing resource allocations as well as other auxiliary matrices. Our experiments demonstrate that deadlock detection always takes two clock cycles.