复杂非紧密嵌套循环变换在并行编译中的应用

在并行编译中,循环变换是开发程序并行度的主要方法,但存在复杂控制流的非紧密嵌套循环往往无法得到有效的并行化。文章结合分析Benchmark和实现自动并行化系统AFT中复杂非紧密嵌套循环变换的经验,给出复杂非紧密嵌套循环变换的特点及其在并行编译中的应用。     

一种面向异构众核处理器的并行编译框架

异构众核处理器是面向高性能计算领域处理器发展的重要趋势,但其更为复杂的体系结构使得编程难的问题更加突出.针对这一问题,基于开源编译器Open64,提出了一种面向异构众核处理器的并行编译框架,将程序自动转换为异构并行程序.该框架主要包括4个模块：任务划分模块用来识别适合进行加速计算的程序段,实现了嵌套循环的多维并行识别方法;数据布局模块完成数据在主存和SPM之间的布局,实现了数组边界分析和指针范围分析;传输优化模块实现了数据传输合并、传输外提、打包传输、数组转置等多种数据传输优化方法;收益评估模块在构建代价模型的基础上实现了一种动静结合的收益评估方法.并且,基于SW26010处理器,对该编译框架进行了实现,测试结果表明,该编译框架能够实现一些程序以面向异构众核结构的并行变换,且获得较好的加速效果.     

基于嵌套循环分类的并行识别技术

传统的分布存储并行编译系统大多是在共享存储并行编译系统的基础上开发的.共享存储并行编译系统的并行识别技术适合OpenMP代码生成,实现方式是将所有嵌套循环都按照相同的识别方法进行处理,用于分布存储并行编译系统必然会导致无法高效发掘程序的并行性.分布存储并行编译系统应根据嵌套循环结构的特点进行分类处理,提出适合MPI代码生成的并行识别技术.为解决上述问题,根据嵌套循环的结构和MPI并行程序的特点,提出了一种新的嵌套循环分类方法,并针对不同的嵌套循环分别提出了相应的并行识别技术.实验结果表明,与采用传统并行识别技术的分布存储并行编译系统相比,按照所提方法对嵌套循环进行分类,采用相应并行识别技术的编译系统能够更高效地识别基准程序中的并行循环,自动生成的MPI并行代码其性能加速比提高了20%以上.     

基于重排序变换和循环分布的通信优化算法

针对现有通信优化算法无法使MPI自动并行化编译器生成加速比理想的消息传递程序问题,提出了一种基于重排序变换和循环分布的通信优化算法。该算法根据给出的过程间副作用集合和基于mpi_wait/mpi_irecv移动的重排序变换规则,有序地采用重排序变换和循环分布,尽可能安全地扩大点到点非阻塞通信中通信与计算的重叠窗口,使MPI自动并行化编译器生成具有更多计算重叠通信的消息传递代码。实验结果表明,该算法能够隐藏更多的点到点非阻塞通信开销,并且明显提升消息传递程序的加速比。     

面向Stencil计算的自动混合精度优化

混合精度在深度学习和精度调整与优化方面取得了许多进展,广泛研究表明,面向Stencil计算的混合精度优化也是一个很有挑战性的方向.同时,多面体模型在自动并行化领域取得的一系列研究成果表明,该模型为循环嵌套提供很好的数学抽象,可以在其基础上进行一系列的循环变换.基于多面体编译技术设计并实现了一个面向Stencil计算的自动混合精度优化器,通过在中间表示层进行迭代空间划分、数据流分析和调度树转换,首次实现了源到源的面向Stencil计算的混合精度优化代码自动生成.实验表明,经过自动混合精度优化之后的代码,在减少精度冗余的基础上能够充分发挥其并行潜力,提升程序性能.以高精度计算为基准,在x86平台上最大加速比是1.76,几何平均加速比是1.15;在新一代国产申威平台上最大加速比是1.64,几何平均加速比是1.20.     

面向申威异构架构的并行代码自动生成

异构架构逐渐成为高性能计算领域的主流架构,但相较于同构多核架构,其硬件结构及存储层次更为复杂,程序编写更为困难.先进的优化编译器可以协助程序开发人员实现更为高效的代码,降低程序开发复杂度.多面体编译模型通过抽象分析将程序抽象成空间多面体表示形式,能够将多种循环变换与硬件映射相结合,并面向特定体系结构生成相应的代码.设计实现了一个面向国产申威异构架构的并行代码自动生成系统,采用“源-源”编译模式,基于多面体编译模型实现.系统针对申威异构架构特点将程序计算过程进行硬件部署,同时实现数据传输与内存空间的自动管理.实验基于Polybench测试集中线性代数相关用例进行测试.结果表明,利用代码自动生成系统生成的异构并行代码能够在申威异构平台上正确运行,并能够有效发挥申威异构平台的性能,基于申威异构平台利用64线程加速计算的平均加速比达到了539.16倍.     

多面体模型下的循环置换与自动调优

针对常用多面体编译器Pluto默认循环调度和分块大小性能欠佳的问题，提出了一种为其调度计算多种合法置换，根据置换和分块大小构成的配置空间为循环程序自动调优的方法。通过对定义循环融合的标量维度的处理，实现了非完美嵌套循环块间和块内的同时置换。构建了4种机器学习驱动的自动调优策略，为循环程序在指定问题规模下寻找优化的置换序和分块大小组合。默认分块大小下，扩展后的Pluto编译器并行环境下生成的最佳置换相较于Pluto的默认调度取得了最高4.02和几何平均2.12的加速比。通过进一步搜索更优的置换序和分块大小组合，最好的自动调优策略在并行环境下相较于Pluto的默认优化取得了最高5.48和几何平均2.86的加速比。此外，指定问题规模下，自动调优得到的最佳配置和学习模型应用于相似问题规模时，相较于Pluto的默认优化也取得了不同程度的性能提升。     

MPI自动并行化编译系统中消息传递代码生成算法

传统MPI自动并行化编译系统从数据重分布的角度,生成面向分布式存储系统的消息传递程序,但是大量数据重分布通信的额外开销导致其加速比低。为了解决此问题,在基于Open64的MPI自动并行化编译系统后端,提出了一种消息传递代码生成算法。该算法以统一数据分布为中心,根据给定的并行化循环集和通信数组集,通过修改WHIRL表示的串行代码语法结构树,生成更精确的消息传递代码。实验结果表明,该算法能够较大程度地降低消息传递程序的通信开销,并且明显提升其加速比。     

基于模糊聚类的推测多线程划分算法

推测多线程(Speculative Multithreading,SpMT)技术是一种实现非规则程序自动并行化的有效途径.然而,如何有效评估由诸如控制、数据依赖等因素导致的多种并行开销并实现最优线程划分一直是制约加速比性能提升的关键问题.基于启发式规则的传统划分方法虽然可以取得一定的加速效果,但由于启发式规则只能对多种并行开销进行定性评估,因而导致只能得到经验上较优的线程划分.针对传统划分方法的局限性,文中首次提出并实现了一种基于模糊聚类的线程划分方法.在该方法中,作者首先提出一种评估模型来定量评估各种并行开销,然后通过深入分析各种并行开销来确定最佳的线程解搜索空间,最终利用聚类方法实现有效线程解空间搜索以求取更优的线程划分.基于Olden程序集的测试结果表明,文中提出的线程划分方法可以有效地对非规则程序进行划分,其平均加速比可达到1.85.     

面向DSWP并行的OpenMP任务调度机制的扩展与实现

多核处理器能够提升多线程程序的性能,但早已存在的诸多单线程程序无法从中获益,程序员也习惯于编写单线程程序.自动并行化技术是将单线程程序移植到多核上的重要手段,但是当循环中存在无法确定的数据依赖或复杂的控制流时,传统的自动并行化技术无法取得良好效果.Ottoni等人针对传统自动并行失败的循环提出了Decoupled Software Pipelining(DSWP)算法用以实现指令级的细粒度并行,但其需要对处理器体系结构的深入了解以及对核间通信队列和专用指令的硬件支持,并行性能和应用广泛性受到限制.基于OpenMP应用编程接口实现的DSWP并行不依赖于硬件上对核间通信队列和专用指令的支持,且不受平台的限制,但现有的OpenMP任务调度机制无法满足DSWP并行中对任务调度的需求.对现有的OpenMP任务调度机制进行扩展,增加了任务与线程绑定的属性,保证了基于OpenMP的DSWP并行程序的正确执行.在GCC的OpenMP运行库libgomp中扩展了任务绑定属性子句的功能,扩展后的GCC作为OpenMP DSWP程序的基础编译器,为自动并行提供支持.通过对基准测试集NPB3.3.1的测试表明,传统自动并行失败的循环,经OpenMP DSWP自动并行后在双核处理器上平均加速比达到1.23以上;使用添加了OpenMP DSWP算法的Open64编译器生成的并行程序,与仅使用传统自动并行方法的Intel 编译器和Open64编译器所得程序相比,平均加速比分别高出22％和26％.     

面向神威高性能多核处理器的并行编译优化方法

在神威高性能多核服务器上,自动并行化编译系统为识别和申明程序中的并行性,产生的OpenMP程序没有经过充分的优化,其采用简单的fork-join模型,存在大量的并行循环嵌套,导致运行效率低。为提升自动并行化编译系统产生的OpenMP程序的运行效率,提出一种并行域重构优化技术。并行域重构技术通过合并程序中的并行域和扩展嵌套循环中的并行域范围,减少OpenMP程序的并行域数目,降低线程组频繁创建和合并等控制开销,将简单fork-join模型的OpenMP程序转换为性能更为高效的单程序多数据模型的OpenMP程序。实验结果表明,在新一代神威高性能多核服务器SW1621平台上,并行域重构技术在NPB3.3-OMP测试集和SPEC OMP2012测试集上的运行效率分别提高了10.77%和7.94%的,可有效提升自动并行化编译系统OpenMP程序的执行效率。     

一种面向众核处理器的嵌套循环多维并行识别方法*

现有并行识别方法用于众核处理器时存在一定不足,当选择的循环并行维迭代数较少时可能导致严重地负载不均衡。针对这一问题,提出了一种面向众核处理器的多维并行识别方法,在现有并行识别方法无法做到较好的负载均衡时,选择嵌套循环的多个维进行并行,将多个并行维的迭代空间合并后再做任务划分,减少负载不均衡对程序并行效率的影响。此方法已在课题组开发的自动并行化系统中进行了实现,实际应用过程中能够提升一些应用程序在众核处理器上并行执行的效率。     

An Object-Oriented Framework for Loop Parallelization

Generation of efficient parallel code is a major goal of a well-designed and developed parallelizing compiler. Another important goal is portability of both compiler system and the resulting output source codes. The various choices of current and future parallel computer architectures as well as the cost of developing a parallelizing compiler make portability a very important design goal. Since the design of parallelizing compilers is considerably move complex than designing conventional compilers, it is very important to achieve both efficiency and portability. To meet this dual goal, we have investigated the application of object oriented design to parallelizing compilers. Our parallelizing compiler design is based on abstractions of intermediate representations of loops and their class definitions. In this paper, we address the problem of loop parallelization and propose a framework where the loop parallelization process is divided into three phases and the optimization of loops is performed via a cyclic application of these three phases. The class of each phase is hierarchically derived from intermediate representations of loops. This facilitates the portability of the resulting parallelizing compilers. Furthermore, one of the phases uses a reservation table of hardware resources in order to obtain optimized parallel programs for given hardware resources. The validation of the proposed framework is given through the application of the object oriented design on an example program which is then parallelized efficiently.     

EFFECTIVE PARALLELIZATION TECHNIQUES FOR LOOP NESTS WITH NON-UNIFORM DEPENDENCES

The parallelism of loop nests with non-uniform dependences is difficult to extract and ineffectively explored by the existing parallelization schemes. In this paper, we propose new efficient techniques in extracting parallelism of loop nests with non-uniform dependences using their irregularity. By this way, current highly parallel multiprocessor systems such as multithreaded and clustering multiprocessor systems can be fully utilized. These four mechanisms are (a) parallelization part splitting, (b) partial parallelization decomposition, (c) irregular loop interchange and (d) growing pattern detection. They explore parallelisms of special parallel patterns for nested loops with non-uniform dependences. The loop transformations used in uniform loops are also applied in non-uniform dependence loops after legality tests. We apply the results of classical convex theory and detect special parallel patterns of dependence vectors. We also proposed an algorithm that combines above mechanisms to enhance parallelism. We demonstrate that our technique gives much better speedup and extracts more parallelism than the existing techniques. Thus, we are encouraged by these apparent enhancements to pursue further development.     

The BonaFide C Analyzer: automatic loop-level characterization and coverage measurement

The advent of multicore technologies has increased the interest in parallelization techniques for existing sequential applications. These techniques include the need of detecting loops that are good candidates for parallelization, and classifying all variables of these loops according to their use, a task surprisingly hard to be carried out manually. In this paper, we introduce the BonaFide C Analyzer, an XML-based framework that combines static analysis of source code with profiling information to generate complete reports regarding all loops in a C application, including loop coverage, loop suitability for parallelization, a classification of all variables inside loops based on their accesses, and other hurdles that restrict the parallelization. This information allows to analyze how particular language constructs are used in real-world applications, and helps the programmer to parallelize the code. To show the features of the framework, we present the results of an in-depth loop characterization of C applications that are part of the SPEC CPU2006 benchmark suite. Our study shows that 47.72 % of loops present in the applications analyzed are potentially parallelizable with existent parallel programming models such as OpenMP, while an additional 37.7 % of loops could be run in parallel with the help of runtime speculative parallelization techniques.     

测试任一嵌套DO循环置换合法性的阻碍矩阵算法

对程序进行并行变换是提高程序并行性的有效手段，许多并行变换都要寻找一种最优的循不置换，在寻找过程中，如果对每一个被考察的置换都重新进行相关性测试，那么整个寻找过程将极费时间，本文给出了一个测试嵌套循环任一置换的阻碍矩阵测试算法，它将测试一循环置换的合成法性转化为测试一组向前置换的合法性，并且仅需要嵌套循循环做一遍相关性测试，利用该算法可以简便迅速检查任一循环置换的合法性，从而使许多并行变换变得实际可     

面向对象语言并行化中的调用局部化优化

该文提出了一种将调用局部化技术应用于并行环境下面向对象语言的方法，文中详细讨论了该技术的适用条件以及如何通过该方法减少循环中的远程过程调用开销，该优化技术产首先将循环分离成多个包含有远程调用的循环，再将分离后的循环分离给循环中对象所在的处理器，最后，化简迭代空间，并且用消息传递来传输数据，这种优化对象分布和循环并行化之后进行，将函数调用局部化于处理器，通过这种优化，可以进一步挖掘循环中的任务并行性，降低计算复杂度，减少函数调用开销，尤其适合面向对象语言中对循环里小函数的优化，该技术已经在作者设计的Java自动并行化编译器JAPS－Ⅱ中实现，在实验中，利用这种优化技术得到了超线性性加速比。     

基于LLVM中间表示的数据依赖并行计算方法

底层虚拟机（LLVM）是一个广泛使用的编译框架,其中间表示（IR）中包含有丰富的程序分析信息,众多以LLVM为平台的相关工作均以IR为基础开展。数据依赖关系在错误检测、定位及程序调试等领域有着重要应用,基于IR的数据依赖关系计算多采用串行迭代方式,但在应对较大规模IR文件时可扩展性不够理想。对此进行了数据依赖关系计算中指令读写的可并行性挖掘,结合图形处理器并行计算优势,提出一种基于LLVM IR的数据依赖关系并行计算方法DRPC。以IR为输入,采用CPU-GPU双端协同方式实现程序数据依赖关系的高效计算。实验结果表明,针对基准程序集SPEC,DRPC分别在直接及传递数据依赖关系计算上最高获得了3.48×和4.91×的加速比。     

选择性循环的并行方法

针对含有大量循环的串行程序存在的问题,提出一种基于线程级前瞻技术的循环选择方案。该方案对循环进行最优选择后建立一个可并行运行的循环集。对于该集合中的循环,选择并行效率高的代码段作并行处理,以加快串行程序运行速度。实验表明,相对于一般的简单内部循环或外部循环并行方法,该方案使9种基准代码的加速比平均上升23.8%,从而提高串行程序并行运行的效率。     

选择性循环的并行方法

针对含有大量循环的串行程序存在的问题,提出一种基于线程级前瞻技术的循环选择方案。该方案对循环进行最优选择后建立一个可并行运行的循环集。对于该集合中的循环,选择并行效率高的代码段作并行处理,以加快串行程序运行速度。实验表明,相对于一般的简单内部循环或外部循环并行方法,该方案使9种基准代码的加速比平均上升23.8%,从而提高串行程序并行运行的效率。