CPA-CSA: Development of Parallel Reduced Run-Time Complexity Hardware-Oriented Deadlock Algorithms with Proofs and Extensions to Other Areas

Indiana University, Bloomington IN

Investigators

Abstract

Technology trends show that future multiprocessor system-on-chips will integrate tens of processor cores and tens of on-chip resources. To exploit inherent parallelism in such systems, multiple jobs can be run concurrently on different processor cores, each using the abundant on-chip resources. As a result, considerable interactions among processor cores and resources may result in deadlocks and would be the most critical issue faced by such systems. Software approaches to detect and resolve deadlock in such systems take longer time and may even fail to be timely invoked. This research investigates a novel technique to inherently equip these systems with a hardware mechanism that can detect deadlocks very fast so that an OS can react in minimal time. The central idea behind this methodology is to transform one form of complexity (e.g., graph) into another form of complexity (e.g., matrix) that can then be parallelized in hardware. This project develops various parallel hardware-oriented deadlock detection algorithms and their variations, which will be not only faster but will also dramatically reduce the run-time complexity from at most linear down to constant. Moreover, the project also provides proofs of correctness and run-time complexity of these algorithms. These proofs are essential for wide spread adoption in practical applications. The research is of significant value to the reliability of many real-time systems such as medical robots, automobiles and avionics. Finally, this project extends devised data structures and algorithms to potential algorithms in various other areas that utilize corresponding graph oriented data structures such as the Floyd-Warshall algorithm; the manipulation of B-tree, T-tree, R-tree and their variations; digital logic optimization; and Petri-net models.