Collaborative Research: Flow-Sensitive Program Analysis for Speculative Parallelization

芯片多处理器（CMP）的兴起，在单个芯片上拥有数十到数百个处理单元，有望显著提高桌面系统的性能，与昨天的超级计算机的性能相媲美。超级计算应用程序通常利用应用程序计算任务中存在的高度并行性，这允许多个处理单元同时解决问题，以快速获得解决方案。然而，普通的软件应用程序不是为专门的超级计算机体系结构编写的，并且缺乏足够的显式并行性来自动从cmp中获得加速。因此，成功地利用cmp需要应用程序开发人员对设计、编码和调试进行重新思考。原生支持并行概念的编程语言和程序注释将越来越成功，其中顺序代码可以更容易地转换为并行代码的编程语言也将越来越成功。本研究探讨了几种成功的方法的组合和增强，以自动地在程序代码中显示更多的并行性。首先，研究人员将流敏感环变变量检测与优化与递归链（CR）代数以及基于区间理论的非线性变量区间检验相结合。这样做的目的是减少误报的数量，从而禁止对具有数组依赖的循环进行并行化。其次，基于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.