基于SIMD机器的优化数据传输的并行循环分割

本文提出一个基于分布式局存的ＳＩＭＤ机器的循环分割理论体系以优化运算中所需要的数据传输。该体系使用矩阵表示迭代空间、数据空间和数组存取式。我们引入数据传输概念，并建立一个简单有效的数据传输模型来评估数据在全局内存和局部内存之间的传输开销。最后，对于给定的循环嵌套，我们给出一个循环分割算法以获得优化循环块，使得循环嵌套中所需要的数据传输开销最小，并且大大减少了数据传输和计算的同步开销。实验结果证明了  

利用循环分割和循环展开避免Cache代价

存储系统与处理器之间的速度差距逐渐变大,为此,cache使用了分级机制,但这也带来了额外的存储延迟(cache代价).提出一种利用循环分割和循环展开相结合避免cache代价的PCPLPU(prevent cache penalty by loop partition-unrolling)算法.实验结果表明,PCPLPU算法能够有效避免循环代价,提高程序性能.  

面向MPF的自动并行过程中的迭代划分和数组访问局部性分析

并行编程一般分为数据并行和消息传递两种模式，比较而言，消息传递的应用更为广泛，面向消息传递ＦＯＲＴＲＡＮ（ＭＰＦ）的自动并行工具能很大程度上缓减用户编程的压力，并具有很好的实用价值。迭代划分和局部性分析是自动并行中的重要部分。  

面向SIMD机器的全局自动数据分割

提出了一种面向ＳＩＭＤ机器的全局数据自动分割算法，该算法能处理多个非紧嵌折循环嵌套，并且数组下标存取为循环变量的线性式，首先通过数据与迭代映射抽象了计算中的通信方式，然事提出识别规则模式通信模式的形式比条件，接着建立包含对准信息和相应通信开销的数据迭代图，并在数据迭代图的基础上提出了一个启发式算法来计算较优的数据分布和迭代分布，以优化处理单元之间的通信开销，通过发析多个循环嵌套所涉及的多个数组映和  

嵌套循环到多处理机的映射

给出了将具有变相关的嵌套循环映射到具有分布式存储的多处理机上的两种方法.通过相关向量的分解或由相关向量导入方向向量,可将具有变相关的嵌套循环分解成若干互相没有相关关系的独立部分.由于它们可以被独立地执行,从而可以被映射到各个处理机上并行处理.  

A Computation+Communication Load Balanced Loop Partitioning Method for Distributed Memory Systems

Due to a significant communication overhead of sending and receiving data, the loop partitioning approaches on distributed memory systems must guarantee not just the computation load balance but computation+communication load balance. The previous approaches in loop partitioning have achieved a communication-free, computation load balanced iteration space partitioning solution for a limited subset of DOALL loops. But a large category of DOALL loops inevitably result in communication and the trade-offs between computation and communication must be carefully analyzed for these loops in order to balance out the combined computation time and communication overheads. In this work, we describe a partitioning approach based on the above motivation for the general cases of DOALL loops. Our goal is to achieve a computation+communication load balanced partitioning through static data and iteration space distribution. Our approach first performs partitioning of iteration and data spaces of a loop nest by analyzing communication and parallelism; it then performs architecture-dependent analysis to adjust the granularity of partitions, load balance each partition with respect to total computation+communication, and then performs mapping of partitions onto the available number of processors. This multiphase partitioning method works as follows. First, the code partitioning phase analyzes the references in the body of the DOALL loop nest and determines a set of directions for reducing a larger degree of communication by trading a lesser degree of parallelism. The partitioning is carried out in the iteration space of the loop by cyclically following a set of direction vectors such that the data references are maximally localized and reused, eliminating a larger communication volume than parallelism. We then perform data space partitioning based on a new larger partition owns rule to minimize the communication overhead for a compute intensive partition by localizing its references relatively more than a smaller noncompute intensive partition. A partition interaction graph is then constructed which is used by the architecture-dependent analysis phase to merge the partitions to achieve granularity adjustment, computation+communication load balance, and mapping on the actual number of available processors. Relevant theory and algorithms are developed along with a performance evaluation on the Cray T3D.  

使用代价分析的向量化循环分割技术

为了使循环在编译过程中更充分地被向量化,提出了一种基于代价分析的向量化循环分割技术。标记出了迭代依赖间隔中不存在依赖关系的循环片段,在此基础上建立一个简单有效的代价分析模型来评估这些循环片段向量化和未向量化的CPU时钟周期开销,最后从代价分析结果中确定是否需要将其向量化分割,从而把向量化特性应用到细短的循环片段。实验结果表明了该技术的有效性,对迭代依赖距离大的循环片段优化作用更明显。