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

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

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

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

一种新的MPI Allgather算法及其在万亿次机群系统上的实现与性能分析

给出一个新的MPI Allgather算法--邻居交换算法（neighbor exchange）.提出的平均逻辑通信距离的概念和计算公式,可以有效地衡量通信的局部性.通过分析,发现在4种MPI Allgather算法中,邻居交换和环算法均具有最优的通信局部性.在万亿次机群深腾6800和曙光4000A上对4个MPI Allgather算法进行的性能测试和分析结果表明,邻居交换算法的长消息通信性能最优,中长消息通信性能不稳定,短消息通信性能次于递归倍增和Bruck算法.     

MapReduce框架下结合分布式编码计算的容错算法

随着分布式系统规模扩大及计算复杂度增加,分布式计算的平均故障修复时间和容错计算所产生的通信开销呈现日益上升趋势。结合分布式编码计算和副本冗余技术,提出一种新的容错算法。map节点应用分布式编码计算的思想,将数据冗余分配至多个计算节点创建编码中间结果,降低计算节点在shuffle阶段的数据传输量。reduce节点通过对接收到的编码中间结果进行解码,从而验证中间结果的正确性并得到最终计算结果。实验结果表明,在基于MapReduce的分布式计算框架下,与三模冗余和两阶段三模冗余容错算法相比,该算法在完成容错计算的同时能降低计算过程中的通信开销和平均故障修复时间,并提高分布式系统的可用性和可靠性。     

基于二维结构化网格的可压缩流体并行算法研究

基于二维/轴对称高精度可压缩多相流计算流体力学方法 MuSiC-CCASSIM的结构化网格部分,设计了区域并行分解方法;针对各处理器边界数据的通信,设计了阻塞式通信与非阻塞式通信并行算法;为了减少通信开销,设计了MPI/OpenMP混合并行优化算法。在天河二号超级计算机上进行了测试,每个核固定网格规模为625*250,最多调用8 192核。测试数据表明,采用MPI/OpenMP混合并行算法、纯MPI非阻塞式通信并行算法和纯MPI阻塞式通信并行算法的程序的平均并行效率分别达到86%、83%和77%,三种算法都具有良好的可扩展性。     

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

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

基于MPI的并行八叉树碰撞检测

通过对碰撞检测过程进行分析,发现各节点间相关性较小,存在并行化的可能.在对八叉树碰撞检测算法做适当修改的基础上,结合成熟的消息传递通信(MPI)并行编程环境,提出了基于MPI的并行碰撞检测算法.测试结果表明,碰撞检测效率有较大的提高.     

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

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

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

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

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

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

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

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

KD60集群消息传递接口群集通信算法优化

大规模集群已经发展到多核的时代,多核架构对并行计算提出了新的要求。消息传递接口(MPI)是最常用的并行编程模型,而群集通信又是MPI中的重要组成部分。研究高效的群集通信算法对并行计算效率的提升有着重要的作用。KD60平台是采用首款国产多核芯片——龙芯3号搭建的国产万亿次多核集群。首先分析了KD60平台多核集群的体系特征以及多核架构下通信具有的层次性特征;然后分析原有群集通信算法实现原理及其不足;最后以广播为例,在原有算法基础上,采用一种基于片上多核(CMP)架构改进算法,改变原有算法通信模式,同时结合实验平台KD60体系特征,对算法做了体系相关优化。实验结果表明,改进算法能够很好地利用多核结构的特点,提高了群集通信广播算法的性能。     

MPI并行程序设计的负载平衡实现方法

MPI是目前集群系统中最重要的并行编程工具,它采用消息传递的方式实现并行程序间通信。在MPI并行程序设计中实现负载平衡有着重要的意义,可以减少运行时间,提高MPI并行程序的性能。负载平衡又可分为静态负载平衡和动态负载平衡,对于静态负载平衡,提出了一种分配任务的算法,可有效地按照节点的计算能力,在节点间分配任务;对于动态负载平衡,提出了一种在MPI并行程序中实现的方法,可有效地根据节点的负载情况,在节点间迁移任务。     

基于MIC集群平台的GMRES算法并行加速

广义极小残量法(GMRES)是最常用的求解非对称大规模稀疏线性方程组的方法之一,其收敛速度快且稳定性良好。Intel Xeon Phi众核协处理器(MIC)具有计算能力强、易编程、易移植等特点。采用MPI+OpenMP+offload混合编程模型将GMRES算法移植到MIC集群平台上。采用进程间集合通信异步隐藏、数据传输优化、向量化以及线程亲和性优化等多种手段,大幅提升了GMRES算法的求解效率。最后将并行算法应用到“局部径向基函数求解高维偏微分方程”问题的求解中。测试表明,CPU节点集群上开启32个进程,并行效率高达71.74%,4块MIC卡的最高加速性能可达单颗CPU的7倍。     

大规模结构有限元分析程序在多核集群计算环境中的性能分析和优化

通过对基于MPI编程模型实现的开源有限元计算分析软件在多核集群计算平台中的程序性能的分析,找出程序瓶颈及其原因,实现了基于MPI编程模型的并行程序在多核计算环境中的性能优化。根据程序性能瓶颈的分析,提出了基于MPI/OpenMP混合并行编程模型的大规模线性/非线性方程组求解和多线程多进程同时进行消息通信的两种程序性能优化方案。不同计算规模的实验结果表明,在多核集群计算平台中,MPI/OpenMP混合编程模型实现的大规模非线性方程组求解器相对于单纯基于MPI编程模型实现的并行程序,其性能有2倍到3倍的提升;多线程多进程同时消息传递的优化方案虽然对程序能够起到性能优化作用,但是对解决程序消息通信瓶颈的问题不是最好的方法。两个方案总体性能分析结果表明,基于MPI/OpenMP混合编程模型实现的并行程序,在多核集群计算平台中能够更好地发挥硬件系统的计算能力。     

多层次并行体绘制算法的研究与应用

三维数据场的体绘制技术是科学可视化中一个重要的研究方向,本文在研究和总结体绘制的发展历程与关键技术的基础之上,着重研究了体绘制中的光线投射算法,结合多核处理器机群系统,提出并实现了一种基于多层次并行编程模型的并行光线投射体绘制算法,并成功地将该算法应用于三维城市浅层地质模型,取得了良好的可视化效果。分别对MPI环境和多层次并行编程MPI+OpenMP环境下的光线投射算法进行了不同计算规模的性能比较实验。实验和分析表明,多层次并行光线投射体绘制算法加快了体绘制的速度,MPI+OpenMP多层次并行模型性能高于纯MPI编程模型的性能。     

MPI和OpenMP混合并行模型下的遥感编目信息检索

目的 空间位置检索是遥感影像检索中的关键步骤,为进一步提高海量遥感影像编目数据定位检索效率,降低误检率,提出一种基于MPI和OpenMP混合编程模型对射线法进行多层次并行化实现。方法 首先完善传统射线法处理点在多边形边上以及射线与边的端点相交的情况;其次采用MPI实现基于程序层面多机并行,OpenMP实现算法层面单机多线程并行,通过开启多个线程同时处理多边形的各个点,判断它们是否在另一个多边形的内部。结果 当系统中所有节点开启线程数之和等于主节点的最佳线程数时,全局计算速度达到最佳。混合并行算法相比串行算法检索时间减少50%以上,效率更高。结论 MPI+OpenMP混合并行比普通的串行执行、单纯MPI并行或单纯OpenMP并行执行空间定位检索算法效率显著提高,这种并行方案普遍适用于集群环境下的并行程序,并且可以进一步拓展到其他图像处理算法领域。     

基于有效并行求解策略的显式有限元分析并行算法

针对大规模结构非线性动力问题的有限元分析非常耗时,基于消息传递接口（MPI）机群环境,提出多种基于并行求解策略的显式有限元并行算法。基于显式消息传递的区域分解技术,采取重叠、非重叠区域分解技术及动态任务分配方法,通过将计算与通信重叠,优化处理器间的通信,对非重叠通信区域分解并行算法、重叠通信区域分解并行算法、群动态任务分配算法、动态任务分配算法及动态负载平衡算法进行研究。为在机群环境下实现非线性动力有限元分析,开发了基于有效并行求解策略的显式有限元并行算法。编写了基于消息传递编程模式的并行有限元程序,在工作站机群上实现了数值算例,分析了算法的性能,并与传统的Newmark算法进行了比较。算例表明：群动态任务分配算法的性能优于动态任务分配算法,低于区域分解算法的性能,动态负载平衡算法最优。对相同规模的问题提出的算法比Newmark算法快,优于Newmark算法。对结构非线性动力问题的有限元分析,所提出的并行算法是可行有效的。     

一种新的求解复杂函数优化问题的并行粒子群算法

并行计算能够有效地缩减大规模问题求解的时间需求。文章先简要介绍了粒子群算法的标准版本,对比细粒度的粒子群算法的简单并行,引入种群和移民的思想,提出了一种基于多种群的粒子群算法的并行版本。算法在曙光3000超级服务器上完成,利用MPI处理各个进程间的通讯。使用BUMP函数的数值实验表明了该算法的有效性。