Collaborative Research: Flow-Sensitive Program Analysis for Speculative Parallelization

在一块芯片上具有数十到数百个处理单元的芯片多处理器(CMP)的兴起，有望显著提高桌面系统的性能，与昨天的超级计算机的性能相媲美。超级计算应用程序通常利用应用程序计算任务中存在的高度并行性，这允许多个处理单元同时解决问题，以快速获得解决方案。然而，常见的软件应用程序不是为专门的超级计算机体系结构编写的，并且缺乏足够的显式并行性来自动从CMPS获得加速比。因此，成功利用CMPS需要应用程序开发人员重新考虑设计、编码和调试。本来支持并行概念的编程语言和程序注释将越来越成功，以及可以更容易地将顺序代码转换为并行代码的编程语言。这项研究调查了几种成功的方法的组合和增强，以自动暴露程序代码中的更多并行性。首先，研究人员将把流敏感循环变量检测和优化与递归链(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.