基于Define-Use分析的冗余通信消除算法

针对并行代码自动生成过程中产生的大量冗余通信代码,提出基于Define-Use分析的冗余通信消除算法。将中间代码的每一个过程划分为不同的块,同时收集各块中对数组变量的定义和引用信息。以块为节点,按控制流关系构造控制流图。以控制流图为基础,根据块间各数组变量的Define-Use关系,确定需要通信的位置,从而消除冗余通信代码,达到优化通信的目的。测试结果表明,该算法可有效提高并行程序的执行效率。     

消除冗余通信的暴露集求解算法

针对分布存储结构计算机系统在并行编译过程中存在的问题,提出一种消除冗余通信的暴露集求解算法,分另4采用数组数据流分析和自干扰分析技术对嵌套循环中的流依赖和输入依赖进行分析,从而得到暴露集空间。仿真实验结果表明,将该算法所得结果作为后端生成数据分布通信代码的依据,可有效消除冗余通信,提高系统整体性能。     

优化的数组数据流分析技术的实现

精确的数组数据流分析是并行编译技术中的重要步骤。用终写树算法表示精确的数组数据流分析仅针对一对读写引用。该文研究并在工程上实现了终写树交叉算法,以分析多个写引用与公共读引用之间的精确数据依赖关系,减少了冗余信息并使精确数组数据流分析技术得到一定程度的优化。     

基于Define-Use图的MPI通信求解算法

针对分布存储计算机系统并行编译过程中,为维持数据一致性而产生冗余通信的问题,提出一种优化的通信求解算法。该算法基于依赖关系分析和过程间数据流分析,通过遍历Define-Use图,获得更精确的通信数据,消除过程调用时产生的冗余通信。实验结果表 明,将算法所得结果作为后端生成MPI通信代码的依据,可以有效减少通信量,加速比接近手工MPI并行程序。     

并行编译中对维内通信的通信优化

代码生成作为并行编译器的后端,其生成代码的优劣直接影响着并行程序的执行效率。并行分解的维内存在偏移会产生维内通信,传统算法生成的维内通信代码不够精确,会产生冗余通信。提出了通过合并数组变量生成通信链,并按照通信链生成通信代码的维内通信优化算法来消除此类冗余,对传统算法进行了改进和优化。测试结果表明该算法对维内通信的优化效果明显。     

自动并行化中不规则循环的通信代码生成

不规则计算在大规模并行应用中广泛存在。在面向分布存储结构的自动并行化过程中,较难在编译时为不规则循环生成并行代码。并行代码中的通信代码对程序运行结果的正确性以及加速效果有着严重的影响。通过分析程序的数组重分布图,使用部分冗余的通信方式来维持不规则数组访问的生产者消费者关系,可以在编译时为一类常见的不规则循环自动生成有效的通信代码。该方法使用计算分解和数组引用的访问表达式求解不规则数组在各处理器的本地定义集作为通信的数据集,分析针对此类不规则循环划分的通信策略,继而生成相应的通信代码。实验测试的结果取得了预期的加速效果,验证了方法的有效性。     

基于主导值的计算和数据自动划分算法

计算和数据自动划分是并行化编译中一种自动分配计算和数据到各个处理机的优化技术,划分的结果直接影响程序并行的性能。数组是划分处理的主要对象之一,一些数组分布后的收益不高,但带来的并行约束却能对其它数组的划分产生干扰,导致大量数据重分布通信的产生。现有的划分算法中没有约定数组分布的优先次序,因此无法限制这些数组并行约束的传播,降低了优化编译器后端自动生成并行代码的性能。提出了一种基于主导值的计算和数据自动划分算法:将划分过程中数组对程序并行性的影响量化为主导值,并依据主导值的大小约定数组分布的优先次序,限制干扰数组并行约束的传播速度,提高划分结果的合理性。实验结果表明,算法能够获得良好的划分效果。     

MPI通信代码自动生成算法

对于高性能并行计算机而言，如何由给出的计算、数据划分信息及精确数组数据流分析信息自动生成并行化代码是实现串行程序并行化的一个重要问题。根据Saman P.Amarasinghe和Lam的定理，实现了一种并行化识别工具中MPI（Message Passing Interface）并行化代码自动生成技术的算法，并对该算法的性能进行分析。     

基于线性变换的计算与数据动态分解方法

在并行优化编译器的并行识别过程中,许多串行代码无法找到全局一致的分解结果,数据重分布无可避免,有必要寻找一种有效的方法求解计算和数据的动态分解。该文研究了单个嵌套循环计算与数据分解算法以及分解结果表示方法,提出一种在多个嵌套循环间求解数据线性一致分布的动态分解算法,结合程序的结构分析和程序的控制流信息,用于通用串行代码的并行分解过程,可以同时给出串行代码的计算划分和数据分布结果。     

基于线性不等式消元实现的通信优化

若自动生成的并行化代码中包含过多的冗余代码,将导致代码膨胀,同时增加不必要的时间开销。该文通过对计算划分不等式和依赖关系不等式进行傅立叶消元,消除并行化代码中的冗余通信部分,实现通信优化。测试结果表明,与通信优化前的代码相比,消除后的并行代码量减少了10%~30%,处理器数目相同的情况下加速比平均达到1.12。     

一种基于代表元的划分算法

划分是把程序中不同的计算和数据分配到并行处理系统的不同处理机来充分利用并行系统的计算资源、提高程序处理速度的一种优化技术.划分的效果对程序在并行系统上的执行效率将产生至关重要的影响,因此划分问题一直是并行领域研究的一个热点.但是应用程序的一些特性,如非紧密嵌套循环、一条语句对非只读数组的多次引用间存在重叠、不同语句对同一数组不同步长的引用,给有效解决划分问题设置了极大的障碍.已有的划分算法无法对具有这些特征的程序进行自动划分.虽然在对具有这些特征的程序进行手工优化过程中,存在一些直观上的划分策略,但这些策略无法应用到编译器中来指导编译器完成对程序的自动划分.文中根据这类程序的特点,提出了一种基于代表元的划分算法.该算法通过使用程序中对划分计算产生实际影响的数组引用作为代表元素构造各种划分的限制条件,完成程序的划分.同时通过寻找最大一致性数据划分方向有效减少了程序划分过程中的数据重组织通信.该算法已经在AFT2004中实现,并对应用程序获得了很好的效果.     

分布存储系统中优化通信的冗余计算分割

针对并行循环套序列，提出一种冗余计算分割的通信优化方法，根据数据流分析，文中给出用以确定每个循环套的冗余计算量的一般方法，并在此基础上提出冗余计算分割的实现和判定，针对规则依赖的程序，该文还提出了一个高效的冗余计算分割的实现方法，该技术已经在一个并行编译器中实现，试验结果表明，它比传统的通信优化技术有明显的优越性。     

程序并行化中数据收集代码自动生成算法研究

着重论述了串行程序并行化过程中的数据收集部分代码的自动生成。提出利用等价类的方法获取数据的最后写关系，并建立包括计算划分、循环迭代和数据最后写关系的不等式限制系统，最后利用FME消元法对不等式限制系统进行消元处理，最终实现数据收集代码的自动生成。     

基于多核阵列体系结构的嵌套循环并行优化

多核处理器已广泛应用于高性能计算领域,如何有效地将传统串行程序转换为并行代码并减少程序中嵌套循环所占用时间仍是该领域的挑战性问题。本文首先基于多面体模型对嵌套循环进行依赖特征分析并实现瓦片分割,据此自动生成粗粒度并行代码。针对多核阵列处理器的结构特点,采用遗传算法生成通信优化的瓦片任务序列,在此基础上建立了有效的任务调度模型。最后将上述方法应用于LU分解,结果表明该方法与传统调度算法相比,在增加数据局部性、实现负载平衡方面具有更好效果。     

一类非规则并行应用问题的通信集生成算法

非规则计算是大规模并行应用中普遍存在和影响效率的关键问题.在基于分布式内存的数据并行范例中,如何针对非规则数组引用,有效地生成本地内存访问序列和通信集,是并行编译生成SPMD结点程序所必须解决的重要问题.文中针对两重嵌套循环中,下一层循环边界是上一层循环变量的线性或非线性函数,数组下标是两层循环变量的非线性函数这样一类包含非规则数组引用的并行应用问题,提出了一种在编译时生成通信集的代数算法.并且针对cyclic(k)数据分布和线性对齐模板,借助整数格概念,给出了编译时全局地址和本地地址之间的转换方法.文中还给出了相应的经过通信优化的SPMD结点程序.最后通过实例验证了算法的正确性.该算法的意义在于避免了传统Inspector/Executor非规则计算模型中的Inspector阶段,从而节省了运行时Inspector阶段通过穷举下标生成通信集的巨大开销.