过程繁衍及其实现方法

过程的处理在并行化编译工具中是十分关键的问题，过程嵌入和跨过程信息传播是常用的解决方法．近年来，兼有前二者优点的新技术：过程繁衍（Ｃｌｏｎｉｎｇ），逐渐受到人们的重视．而以往的研究中，过程繁衍仅局限于常数值的传播．本文提出了在过程繁衍中进行符号等式约束信息传播的方法，该方法可以增强系统中全局的符号分析（ＳｙｍｂｏｌｉｃＡｎａｌｙｓｉｓ）能力，并可与一些新技术（如Ｏｍｅｇａ测试）互相配合，从而提高并行化系统的能力．该方法在作者开发的并行化编译工具ＡＦＴ中得到了实现．对于ＰｅｒｆｅｃｔＢｅｎｃｈｍａｒｋ的测试  

实用数据依赖分析方法

数据依赖分析是检测程序循环级并行的基本步骤，基于数组下标对分类，本文提出了一个实用，有效的数据依赖分析方案。现有的依赖测试算法，都有循环正规化的假设，由于它存在某些弊端，我们抛弃这一假设，允许循环增量是任意整表达式，为此，本文对有关依赖的定义做了适当修改，并重新推导了某些重要结论，为处理循环增量为变量或表达式的情形，给出了弱形式下的ＧＣＤ和Ｂａｎｅｒｊｅｅ测试，该方案已在ＰＯＲＴ中实现。  

自动向量化中基于数据依赖分析的循环分布算法

循环分布是开发向量化程序的一个有效的方法。但是由于程序中的数据相关性，当前的自动向量化编译器实现完全的循环分布非常困难。因此，当前的自动向量化编译器一般采用简单的循环分布方法。以数据依赖关系分析为基础，从有无依赖环的角度分析了程序中语句的向量化能力，提出了基于语句向量化识别的循环分布算法，并在自动向量化中加以实现。通过此方法，可以充分地分析语句或依赖环的向量化能力，最终采用循环分布，将可向量化的语句与不可向量化的语句分布在不同的循环中。该方法可以处理当前的自动向量化编译器无法向量化的循环，对一些语句间有依赖关系的循环可达到较好的效果。  

面向SLP 的多重循环向量化

如今,越来越多的处理器集成了SIMD(single instruction multiple data)扩展,现有的编译器大多也实现了自动向量化的功能,但是一般都只针对最内层循环进行向量化,对于多重循环缺少一种通用、易行的向量化方法.为此,提出了一种面向SLP(superword level parallelism)的多重循环向量化方法,从外至内依次对各个循环层次进行分析,收集各层循环对应的一些影响向量化效果的属性值,主要包括能否对该循环进行直接循环展开和压紧、有多少数组引用相对于该循环索引连续以及该循环所包含的区域等,然后根据这些属性值决定在哪些循环层次进行直接循环展开和压紧,最后通过SLP对循环中的语句进行向量化.实验结果表明,该算法相对于内层循环向量化和简单的外层循环向量化平均加速比提升了2.13和1.41,对于一些常用的核心循环可以得到高达5.3的加速比.  

分支嵌套循环的自动并行化研究

GCC编译器是一种受广大研究者青睐的开源优化编译器,但它仅仅能够对完美嵌套循环进行依赖分析。为了更好地挖掘嵌套循环粗粒度的并行,深入研究了GCC5.1数据依赖分析过程,提出了一种能够处理分支嵌套循环的依赖测试方法。首先识别出分支嵌套循环,然后分析数组下标与分支嵌套循环外层索引变量的关系,最后计算出外层循环索引变量的距离向量,并通过检测距离向量判断循环是否存在依赖。实验结果表明,该方法能够正确、有效地分析出分支嵌套循环的依赖关系。  

面向MPP Fortran的程序自动并行化

ＭＰＰ Ｆｏｒｔｒａｎ是Ｃｒａｙ公司为分布存储、全局编址的Ｃｒａｙ Ｔ３Ｄ ＭＰＰ系统推出的一种数据并行语言。本文首先介绍了ＭＰＰ Ｆｏｒｔｒａｎ的主要特点，然后以该语言为例，对面向ＭＰＰ系统程序自动并行化的基本内容以及关键技术进行了分析和探讨。  

并行化技术与工具

程序并行化工具由它能有效地解决了多种并行机结构间的代码可移植性和大大地减轻用户使用并行机的困难，已成为当今并行处理领域的一个热门研究课题。相信随着对并行机系统越来越广泛的使用。它还将会得到不断的发展和完善。本文着重介绍了并行化关键技术和工具系统的研究历史与现状，并就这一研究课题今后的发展趋势提出一些看法。  

用于含过程调用DO循环的循环嵌入方法

循环是程序中蕴含并行性最为丰富的一种结构，因此成为并行化编译最主要的对象．但循环内的过程调用严重妨碍了循环的数据相关性分析，使得循环语句潜在的大量并行性得不到开发．本文提出的循环嵌入方法使部分含过程调用循环语句的并行化成为可能，对部分用其它过程间分析技术也能开发其并行性的这一类循环语句采用循环嵌入方法，并行化开销低，并且分析更精确．采用循环嵌入方法还可降低程序由于多次过程调用带来的调度开销．这一方法在作者开发的自动并行化编译系统AFT（automaticPortrantransformer）中得到了实现，对Spec92测试程序包的试验结果表明了本文提出的方法是行之有效的．  

The extension of the I test

The I test is an efficient and precise data dependence method to ascertain whether integer solutions exist for one-dimensional arrays with constant bounds. For one-dimensional arrays with variable limits, the I test assumes that there may exist integer solutions. In this paper, we extend the I test. The extended I test can be applied towards determining whether integer solutions exist for one-dimensional arrays with variable limits, improving the applicable range of the I test. Experiments with benchmark cited from EISPACK, LINPACK, Parallel loops, etc. showed that among 1189 pairs of one-dimensional arrays tested, 183 had their data dependence analysis amended by the extended I test. That is, the extended I test increases the success rate of the I test by approximately 15.4%. Comparing with the Power test and the Omega test, the extended I test has higher accuracy than the Power test and shares the same accuracy with the Omega test for these 1189 pairs of arrays, but has much better efficiency over these two well-known tests.  

Data Dependence Analysis of Assembly Code

Determination of data dependences is a task typically performed with high-level language source code in today's optimizing and parallelizing compilers. Very little work has been done in the field of data dependence analysis on assembly language code, but this area will be of growing importance, e.g., for increasing instruction-level parallelism. A central element of a data dependence analysis in this case is a method for memory reference disambiguation which decides whether two memory operations may access (or definitely access) the same memory location. In this paper we describe a new approach for the determination of data dependences in assembly code. Our method is based on a sophisticated algorithm for symbolic value propagation, and it can derive value-based dependences between memory operations instead of just address-based dependences. We have integrated our method into the Salto system for assembly language optimization. Experimental results show that our approach greatly improves the precision of the dependence analysis in many cases.