RUI: A Novel Dependence Analyzer for Parallelizing Compilers

在过去的十年中，高性能大规模并行架构的开发取得了很大的进展。为了开发用于顺序程序自动并行化的快速重构编译器，需要有效的数据依赖分析技术以获得准确的数据依赖信息。目前提出的数据依赖性分析技术分为两类，一类是高效近似检验，另一类是精确指数检验。然而，所提出的研究将试图表明，精确的数据依赖信息可以在实践中有效地计算出来。GCD测试和Banerjee不等式是最广泛用于检测循环巢内数组引用对之间的数据依赖性的两个测试。这些测试是近似的，因为它们是数据依赖的必要条件，但不是充分条件，因此，它们可能引入限制并行化的人为依赖。它们的主要优点是计算成本低。最近的一项研究为GCD和Banerjee试验的准确性提供了必要和充分的条件。这项研究还导致了I（区间）检验的发展，这是一种改进的依赖分析检验。I测试比GCD和Banerjee测试的组合更准确，并且能够在实践中提供准确的数据依赖信息，不像经典测试，而不需要额外的计算成本。原来的工作只考虑具有恒定循环极限的循环的情况。但在科学应用中，内环极限可能是外环迭代变量的线性函数（这些迭代空间称为梯形区域）。本课题开发了一种高效、准确的依赖性分析仪。这项研究有四个目标。第一个目标是推导出GCD和Banerjee测试在一般梯形区域的准确性的条件，并对这些条件在实践中发生的频率进行实证研究。第二个目标是将I测试扩展到一般的梯形区域，并在一组基准代码上评估其性能优势。第三个目标是将I测试与所有其他测试（如Omega测试、Power测试等）进行分析和实证比较。对所有数据依赖性分析测试的分析和实验评估对于确定在实践中应该执行哪些测试至关重要。第四个也是主要的目标是整合上述研究工作，并开发一个改进的依赖分析器，作为parase -2并行编译器的一部分。预期本研究的完成将提高对数据依赖性分析的理解，证明所提出技术的有效性和实际重要性，并显著提高并行编译器的技术水平。通过提供高效和精确的依赖分析技术，可以在实践中执行许多针对高性能计算机体系结构的编译器优化。＊＊＊

Psarris 9528330 In the past decade much progress has been made in developing high performance large scale parallel architectures. The development of fast restructuring compilers for the automatic parallelization of sequential programs requires efficient data dependence analysis techniques in order to obtain exact data dependence information. The proposed techniques in data dependence analysis fall into two categories, either efficient and approximate tests or exact and exponential. The proposed research will attempt to show, though, that exact data dependence information can be computed efficiently in practice. The GCD test and the Banerjee inequality are the two tests most widely used to detect data dependencies between pairs of array references inside loop nests. These tests are approximate in the sense that they are necessary but not sufficient conditions for data dependence and, therefore, they may introduce artificial dependences which limit parallelization. Their major advantages is their low computation cost. A recent study provided necessary and sufficient conditions for the accuracy of the GCD and Banerjee tests. This study has also led to the development of the I (Interval) test, an improved dependence analysis test. The I Test is more accurate than a combination of the GCD and Banerjee tests and is able to provide exact data dependence information in practice, unlike the classic tests, at no additional computation cost. The original work considered only the case of loops with constant loop limits. In scientific applications though, inner loop limits may be linear functions of the outer loop iteration variables (these iteration spaces are termed trapezoidal regions). This project develops an efficient and accurate dependence analyzer. The research has four objectives. The first objective is to derive conditions for the accuracy of the GCD and Banerjee tests in general trapezoidal regions and perform an empi rical study of how often these conditions occur in practice. The second objective is to extend the I test to the general trapezoidal regions and to assess its performance benefits on a suite of benchmark codes. The third objective is an analytical and empirical comparison of the I test with all the other tests, such as the Omega test, Power test, etc. An analytical and experimental evaluation of all the data dependence analysis test's is essential to determining which tests should be performed in practice. The fourth and principal objective is to integrate the above research work and develop an improved dependence analyzer as a part of the Paraphrase-2 parallelizing compiler. It is expected that the completion of the proposed research will improve the understanding of data dependence analysis, demonstrate the effectiveness and practical importance of the proposed techniques, and significantly improve the state of the art in parallelizing compilers. By providing efficient and exact dependence analysis techniques a number of compiler optimizations for high performance computer architectures can be performed in practice. ***