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

技术趋势表明，未来的多处理器片上系统将集成数十个处理器内核和数十个片上资源。为了利用这种系统中固有的并行性，可以在不同的处理器内核上并发地运行多个作业，每个作业都使用丰富的片上资源。因此，处理器内核和资源之间的大量交互可能导致死锁，这将是此类系统面临的最关键问题。在这种系统中检测和解决死锁的软件方法需要更长的时间，甚至可能无法及时调用。本研究研究了一种新技术，为这些系统配备一种硬件机制，可以非常快速地检测死锁，以便操作系统可以在最短的时间内做出反应。这种方法背后的中心思想是将一种形式的复杂性（例如，图形）转换为另一种形式的复杂性（例如，矩阵），然后可以在硬件中并行化。该项目开发了各种并行的面向硬件的死锁检测算法及其变体，这些算法不仅更快，而且还将显著降低运行时的复杂性，从线性下降到常数。此外，该项目还提供了这些算法的正确性和运行时复杂性的证明。这些证明对于在实际应用中广泛采用是必不可少的。该研究对提高医疗机器人、汽车、航空电子等实时系统的可靠性具有重要意义。最后，本项目将设计的数据结构和算法扩展到利用相应的面向图的数据结构（如Floyd-Warshall算法）的各种其他领域的潜在算法；b树、t树、r树及其变体的操作；数字逻辑优化；和Petri-net模型。

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.