Collaborative Research: Flow-Sensitive Program Analysis for Speculative Parallelization

芯片多处理器（CMP）的兴起在单个芯片上具有数十到数百个处理单元，有望显著提高桌面系统的性能，与昨天的超级计算机的性能相媲美。超级计算应用程序通常利用应用程序的计算任务中存在的高度并行性，这允许多个处理单元同时解决问题以快速获得解决方案。然而，常见的软件应用程序不是为专门的超级计算机架构编写的，并且缺乏足够的并行性的显式暴露以自动从CMP获得加速。因此，成功地利用CMP需要应用程序开发人员重新考虑设计、编码和调试。原生支持并行概念的编程语言和程序注释将越来越成功，顺序代码可以更容易地转换为并行代码的编程语言也是如此。本研究探讨了几种成功的方法的组合和增强，以自动暴露更多的并行程序代码。首先，研究者将流敏感的循环变量检测和优化与递归（CR）代数链以及基于区间理论的NLVI（非线性变量区间）测试相结合。这旨在减少误报的数量，从而禁止具有数组依赖性的循环的并行化。其次，基于CR代数、NLVI测试和公理语义理论，提出了一种新的运行时依赖分析算法，增强了循环的推测并行化技术。第三，将引入一组程序注释来支持推测并行化。这有利于源到源编译器和程序员，他们可以利用这些注释，通过运用特定于应用程序的知识从循环中提取更多的并行性。

The rise of chip multiprocessors (CMP) featuring tens to hundreds of processing units on a single chip promises to significantly boost the performance of desktop systems, rivaling the performance of yesterday's supercomputers. Supercomputing applications typically exploit a high degree of parallelism present in the application's computational tasks, which allows multiple processing units to work on solving the problem simultaneously to obtain a solution fast. However, common software applications are not written for specialized supercomputer architectures and lack sufficient explicit exposure of parallelism to gain speedups from CMPs automatically. Therefore, a successful exploitation of CMPs requires a rethinking of design, coding, and debugging by application developers. Programming languages and program annotations that natively support parallel concepts will be increasingly more successful, as well as programming languages in which sequential code can be more easily converted into parallel code. This research investigates the combination and enhancements of several successful approaches to expose more parallelism in program code automatically. Firstly, the investigators will merge flow- sensitive loop-variant variable detection and optimization with the chains of recurrences (CR) algebra together with the NLVI (nonlinear variable interval) test that is based on interval theory. This aims to reduce the number of false positives prohibiting parallelization of loops with array dependences. Secondly, techniques for speculative parallelization of loops will be enhanced with a new run-time dependence analysis algorithm based on the CR algebra, NLVI test, and the theory of axiomatic semantics. Thirdly, a set of program annotations will be introduced to support speculative parallelization. This benefits source-to-source compilers and programmers who can leverage these annotations to extract more parallelism from loops by exercising application-specific knowledge.