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

CPA-CSA：开发并行降低运行时复杂性的面向硬件的死锁算法，并提供其他领域的证明和扩展

• 批准号: 0811448
• 负责人: John Lee
• 金额: $ 10万
• 依托单位: Indiana University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2008
• 资助国家: 美国
• 起止时间: 2008-09-01 至 2011-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0811448&HistoricalAwards=false
• 关键词: CPA; CSA; Development; Parallel; Reduced

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.

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