面向规则DOACROSS循环的流水并行代码自动生成

发掘DOACROSS 循环中蕴含的并行性,选择合适的策略将其并行执行,对提升程序的并行性能非常重要.流水并行方式是规则DOACROSS 循环并行的重要方式.自动生成性能良好的流水并行代码是一项困难的工作,并行编译器对程序自动并行时常常对DOACROSS 循环作保守处理,损失了DOACROSS 循环包含的并行性,限制了程序的并行性能.针对上述问题,设计了一种选择计算划分循环层和循环分块层的启发式算法,给出了一个基于流水并行代价模型的循环分块大小计算公式,并使用计数信号量进行并行线程之间的同步,实现了基于OpenMP 的规则DOACROSS 循环流水并行代码的自动生成.通过对有限差分松弛法（finite difference relaxation,简称FDR）的波前（wavefront）循环和时域有限差分法（finite difference time domain,简称FDTD）中典型循环以及程序Poisson,LU 和Jacobi 的测试,算法自动生成的流水并行代码能够在多核处理器上获得明显的性能提升,使用的流水分块大小计算公式能够较为精确地计算出循环流水并行时的最佳分块大小.自动生成的流水并行代码与基于手工选择的最优分块大小的流水并行代码相比,加速比达到手工选择加速比的89%.     

循环携带反依赖的MPI自动并行化研究

传统的面向MPI的自动并行化使用的依赖测试技术,只能确定代码中是否含有循环携带依赖,而不对循环携带依赖的类型进行判定。经研究发现,当循环携带的是反依赖时,代码仍然可以在一定条件下实现面向MPI的自动并行化。基于依赖测试方法和数据流信息,通过创建合理的依赖数据副本,提出了一种循环携带反依赖的MPI自动并行方法。实验结果表明,所提出的方法能够有效识别存在循环携带反依赖的并行循环,将其作为后端生成MPI代码的依据可有效提高MPI程序的效率。     

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

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

一种精确的调用图生成技术

调用图是过程间分析和程度自动并行化的基础。生成精确调用图可以进一步开发程序的并行性。此文针对Ｆｏｒｔｒａｎ程序，提出了一项完全消除哑过程，产生精确调用图的技术与相应的算法。该算法已在面向ＭＰＰ Ｆｏｒｔｒａｎ的程序自动并行化工具中实现。     

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

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

程序自动并行化中的数组终写关系分析

在程序自动并行化中过程中,数据收集阶段可能产生冗余通信,该文利用数组终写关系分析的方法来消除冗余通信,实现嵌套循环中数组数据最后写关系的快速求解,并将结果提供给编译器后端,生成精确数据收集代码。描述数组终写关系的研究目的和内容,将所处理的嵌套循环根据其结构特征进行分类,给出实现算法的过程。测试结果证明了该算法的正确性和高效性,所产生的精确数据收集代码能够有效地消除部分冗余通信,从而优化和提高了并行化程序的性能。     

基于融合程序控制流的动态分解算法

计算和数据分解是分布主存系统中并行编译的关键,在并行优化编译器的并行识别过程中,许多串行代码无法找到全局一致的分解结果。针对这种情况,该文提出一种融合程序控制流的动态分解算法,增加控制流对分解的影响,使生成的分解结果更适合于后端自动生成的并行代码。实验分析结果表明了该方法的有效性。     

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

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

基于JavaCC的C代码自动并行化的设计与实现

针对当前大量遗产代码无法重复利用的问题,设计一种新的编译工具将C的串行代码转换为基于MPI+OpenMP的混合并行编程代码,降低了并行编程的开发成本。首先,通过对JavaCC的优化,实现一种可以解析C语言的词法和语法分析器,进行源代码分析并生成抽象语法树;其次,根据语法树对源代码进行控制依赖性和数据依赖性分析,产生可并行化的语句块分区;再次,按照提出的并行代码生成方法得到目标代码;最后,基于Visual Studio 2010构建目标代码仿真验证环境。实验结果表明,该工具可以较为理想地实现串行代码自动并行化,与手工编写的代码在加速比上的误差为8.2%~18.4%。     

制导控制系统的实时多线程软件设计

计算和数据分解是分布主存系统中并行编译的关键,在并行优化编译器的并行识别过程中,许多串行代码无法找到全局一致的分解结果.针对这种情况,该文提出一种融合程序控制流的动态分解算法,增加控制流对分解的影响,使生成的分解结果更适合于后端自动生成的并行代码.实验分析结果表明了该方法的有效性.     

非定常Monte Carlo输运问题的并行算法

文中给出了非定常MonteCarlo(下文简写为MC)输运问题的并行算法 ,对并行程序的加载运行模式进行了讨论和优化设计 .针对MC并行计算设计了一种理想情况下无通信的并行随机数发生器算法 .动态MC输运问题有大量的I/O操作 ,特别是读取剩余粒子数据文件需要大量的I/O时间 ,文中针对I/O问题 ,提出了三种并行I/O算法 .最后给出了并行算法的性能测试结果 ,对比串行计算时间 ,使用 6 4台处理机时的并行计算时间缩短了 30倍     

多物理并行数值模拟中的两层紧耦合联接算法

复杂物理现象通常由多类复杂的物理过程紧耦合构成，其数值模拟也通常由适用不同物理过程的多类并行应用程序紧耦合完成．如何设计这些物理过程之间的联接算法，既要保证程序之间数据传递的高效，又要保证程序各自运行和总体模拟的高效，还要保证程序各自开发的独立，是一个值得研究的课题．该文基于广泛应用于高温高压多物理研究中的辐射流体力学和中子输运多物理并行数值模拟，在非结构网格上，提出了两种联接算法：完全松散联接算法和两层紧耦合联接算法，前者侧重于实现程序各自运行的高效和开发的独立，后者在前者的基础上，还权衡了数据传递和总体模拟的高效．在两台并行机的数百个处理机上，通信复杂度分析和数值实验结果表明两个算法均是有效的，可推广适用于辐射或中子输运与其他流体力学的多物理并行数值模拟应用中．特别地，两层紧耦合联接算法是高效可扩展的，取得了近似最优的并行性能．     

Adapting a Navier-Stokes solver for three parallel machines

This paper presents the results of parallelizing a three-dimensional Navier-Stokes solver on a 32K-processor Thinking Machines CM-2, a 128-node Intel iPSC/860, and an 8-processor CRAY Y-MP. The main objective of this work is to study the performance of the flow solver, INS3D-LU code, on two distributed-memory machines, a massively parallel SIMD machine (CM-2) and a moderately parallel MIMD machine (iPSC/860), and compare it with its performance on a shared-memory MIMD machine with a small number of processors (Y-MP). The code is based on a Lower-Upper Symmetric-Gauss-Seidel implicit scheme for the pseudocompressibility formulation of the three-dimensional incompressible Navier-Stokes equations. The code was rewritten in CMFORTRAN with shift operations and run on the CM-2 using the slicewise model. The code was also rewritten with distributed data and Intel message-passing calls and run on the iPSC/860. The timing results for two grid sizes are presented and analyzed using both 32-bit and 64-bit arithmetic. Also, the impact of communication and load balancing on the performance of the code is outlined. The results show that reasonable performance can be achieved on these parallel machines. However, the CRAY Y-MP outperforms the CM-2 and iPSC/860 for this particular algorithm.The author is an employee of Computer Sciences Corporation. This work was funded through NASA Contract NAS 2-12961.     

基于标记语言的跨平台并行编程框架设计

大量遗留的串行代码需要进行并行化改造,而并行程序复杂性及并行计算平台多样性导致改造成本较高.为此,设计了一种基于标记语言的三层并行编程框架,完成了从串行程序层到并行中间代码层、并行中间代码层到目标并行编程语言程序层的二个转换阶段.采用对串行代码进行语言标记的方法来实现并行中间代码层,该代码层实际是共享存储、分布式存储并行平台编程语言的一种抽象.该框架还实现了一种性能标记方法,可用于并行参数自动寻优.用于雷达数据处理的实验结果表明,实现了对应并行代码的生成,且并行加速比与人工实现的并行代码相当.     

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

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

A finite volume method parallelization for the simulation of free surface shallow water flows

We construct a parallel algorithm, suitable for distributed memory architectures, of an explicit shock-capturing finite volume method for solving the two-dimensional shallow water equations. The finite volume method is based on the very popular approximate Riemann solver of Roe and is extended to second order spatial accuracy by an appropriate TVD technique. The parallel code is applied to distributed memory architectures using domain decomposition techniques and we investigate its performance on a grid computer and on a Distributed Shared Memory supercomputer. The effectiveness of the parallel algorithm is considered for specific benchmark test cases. The performance of the realization measured in terms of execution time and speedup factors reveals the efficiency of the implementation.     

基于插桩技术的并行程序性能分析方法设计和实现*

介绍了一种异构环境下的并行调试及性能分析工具ParaVT的设计方法和实现.通过对并行程序源代码的分析处理,利用自动插桩模板插入用于调试和性能分析的用户代码,从而对并行程序进行断点调试和性能参数收集,达到进一步优化程序设计的目的.     

用户指导的并行化策略的研究与实现

提出的用户指导的并行化策略,提供给程序员一个图形化的交互界面,首先由程序员选择并行算法,然后通过配置向导对所选择的并行算法进行定制,生成配置文件,然后参照配置文件自动生成并行程序的框架代码,并将程序员提供的元任务的串行代码嵌入到框架代码中,最后生成并行程序,这样程序员就可以较方便高效地编写并行程序了。     

面向PMVS算法的自动两级并行翻译方法

当使用高分辨率的图像作为图像处理算法的输入时会降低算法运行速度,将算法并行化可提升执行效率,但手动将串行程序转换为并行程序则较为繁琐,并且现有自动并行翻译工具性能不稳定,同时翻译后的程序是单一并行模式。面向基于面片的三维多视角立体视觉（PMVS）算法,提出一种从C到CUDA的自动两级并行翻译方法。使用ANTLR自动解析源C代码,通过分析数据依赖关系和循环数组私有化来识别可并行化的循环结构,将算法翻译成CPU多线程和GPU两级并行结构的代码。在算法执行过程中,将输入图像在CPU和GPU上分别进行处理,降低了算法总执行时间。实验结果表明,该方法的计算加速比随着输入图像分辨率的增加逐渐提高,最高约达到32,相比于PPCG和OpenACC自动并行翻译方法提升明显。     

并行计算稀疏矩阵乘以向量的负载平衡算法

稀疏矩阵乘以一个向量（SpM×V）的问题是许多大型应用问题的核心计算问题，文中提出了一种在并行计算机上并行计算SpMXV的负载平衡算法，计算复杂性为O（N）（N为稀疏矩阵的阶），而目前计算此类问题的最优负载平衡算法的计算复杂性为O（N·P）（P为处理机台数）。文章最后给出了并行数值实验。