RUI: A Novel Dependence Analyzer for Parallelizing Compilers

RUI：用于并行编译器的新型依赖性分析器

• 批准号: 9528330
• 负责人: Kleanthis Psarris
• 金额: $ 6.5万
• 依托单位: University of Texas at San Antonio
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1996
• 资助国家: 美国
• 起止时间: 1996-06-01 至 2000-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9528330&HistoricalAwards=false
• 关键词: RUI; Novel; Dependence; Analyzer; Parallelizing

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. ***

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