MPI_ALLTOALL实现算法的改进号性能分析

通过分析全互换通信中4种算法的性能,提出了一种改进算法.该改进算法递归倍增的创建子进程,通过增加通信进程数目来减少通信次数.对比分析改进算法与成对互换算法的通信次数,改进算法的通信次数是成对互换算法的一半.实验机群是在版本为MPICH2-1.0.8并行环境下测试,结果表明,消息类型为长消息通信且通信进程教为2的幂次方时,该改进算法比成对互换算法的性能更优.     

基于MPI的并行蚁群算法的实现

蚁群算法是新兴的仿生进化算法,具有并行计算、正反馈等特点,与其它各种启发式算法相比该算法具有明显的优越性。该文将实现蚁群算法的并行化,并用来求解TSP问题,结果证明能显著提高蚁群算法的收敛速度。     

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

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

一种跨平台的并行编程框架设计与实现

并行程序设计的复杂性及并行计算平台的多样性导致程序可移植性较差。为此,设计并实现一种跨平台、分层次的并行编程框架OpenCH。该框架通过两层并行函数库和层次化的API设计,对上层应用程序隐藏并行化细节,为基于不同计算平台的库函数设计了统一的函数接口,使底层平台的变化对上层应用程序透明。根据底层函数库的开发,给出一种填充式的编程方法和任务调度系统。将OpenCH应用于遥感影像分类,实验结果证明,基于该框架开发的并行程序可运行于多种并行计算平台,并具有较高的并行加速比,编程框架本身造成的时间开销低于15%。     

基于模式的并行编程环境中任务队列模式的研究与实现

并行程序的设计是并行计算的难点之一。本文在基于模式的并行编程方法的基础上,对一种典型的并行计算与通信模式-任务队列模式进行了深入的研究,并在基于模式的并行编程环境中对该模式进行了实现。本文将通过两个典型的应用实例说明在基于模式的并行编程环境中使用任务队列模式进行问题的并行求解与并行程序开发的过程,并从实现效率和可编程性方面对使用任务队列模式的并行程序和传统的MPI/PVM实现的并行程序进行了分析与比较。     

MPI中的3种数据打包发送方式及其性能分析

首先介绍 了在MPI并行编程环境下，实现群体发送的3种打包发送方式，然后分别分析了这3种发送方式的性能，最后总结出了这3种打包发送方式各自适用的环境。     

以基于MPI的并行蚁群算法求解TSP问题

蚁群算法是新兴的仿生进化算法,具有并行计算、正反馈等特点,与其它各种启发式算法相比该算法具有明显的优越性.该文将实现蚁群算法的并行化,并用来求解TSP问题,结果证明能显著提高蚁群算法的收敛速度.     

MPI程序中通信原语转换方法研究

在当前存在的大量非结构化MPI程序中，许多基于点对点通信原语的代码段可以替换为相应的结构化集合通信原语，在MPI代码结构分析的基础上提出了一种MPI程序中点对点通信原语到集合通信原语转换的方法，首先分析非结构化MPI代码的内部结构，建立Diophantine不等式系统，然后用Omega库运算得到点对点通信代码段的通信模式集，再辅以数据交换分析确定对应的集合通信原语并替换，并给出了相应的实例分析。     

并行图像处理算法的设计与实现

在并行计算机上使用并行算法对数字图像进行处理，使一些计算复杂度很高和计算量很大的计算问题得到较好解决，并获得满意的结果。     

异构环境下树型计算系统的设计与实现

针对异构集群并行效率不高的特点,通过分析由于计算系统设计不合理而产生的种种问题,提出了一种基于异构环境下的树型计算系统,用以兼容各类计算平台,降低全局通信流量和均衡主控节点负载,从而改善集群通信效率,使集群的扩展更加灵活,并且通过实验验证了该系统的可行性。     

并行最短路径搜索算法的设计与实现

针对串行最短路径搜索算法本身固有的局限性,难以随着网络规模的增大而提高搜索速度的问题,设计并实现了一种基于并行Dijkstra思想的并行最短路径搜索算法,使算法复杂度由O（N²）减少到O（N²/p+N*（p-1））,提高了算法的效率。实验结果表明,该算法搜索速度快且性能稳定,当结点数目相当庞大时,算法的优越性更加明显。     

基于主从式并行遗传算法的S盒优化算法

针对传统遗传算法优化高阶S盒中适应度评价值计算量相对大的问题,利用MPI+C环境结合主从式并行遗传算法框架来改进传统串行遗传算法,在MPP处理机——“深腾-1800”（联想）上进行测试,实验结果表明,运用此并行算法优化6阶、8阶的双射S盒,只在优化8阶的情况下能得到更好的加速比,从而验证了主从模式在解决适应度评价值计算量大的问题时,可达到接近线性的加速比。     

一种改进并行遗传算法解决TSP

针对旅行商问题（Travelling Salesman Problem,TSP）的遗传算法的大规模操作,需要大量运算时间而且容易造成局部最优解,提出一种并行混合遗传算法。该方法基于MPI并行环境,利用种群中选择、交叉、变异操作的并行化,将种群中个体平均的分配到处理器中进行操作,有效地避免局部最优解的出现和减少算法的运行时间。实验证明该方法相对于简单遗传算法具有更强全局寻优能力以及耗费更少的操作时间。     

基于MPI的大规模栅格影像并行瓦片化算法

当前主流GIS软件以及互联网地图应用在WebGIS（网络地理信息系统）解决方案中都广泛采用地图切片（又称瓦片）,切片处理服务是实现影像在WebGIS上快速无缝浏览的关键技术。针对目前传统算法以及商业GIS软件在大数据量栅格影像快速瓦片化方面的不足,提出一种名为ParaTile的高效栅格影像快速瓦片化方法,ParaTile基于MPI共享外存的并行技术,利用多进程对原始栅格影像进行数据划分,每个进程对其所划分的区域进行独立读写和计算,而后再按照TMS或者Google Tile定义的标准将瓦片进行编码输出。实验采用不同级别大小的遥感影像进行测试,结果表明ParaTile在面对不同规模的数据时,无论从速度还是算法稳定性上都较现有算法和工具具有显著优势,特别是当数据量越大时,这种优势愈加明显。     

Robust的分布式k中心聚类算法的研究与实现

并行处理的研究在数据挖掘中是十分必要的。在理论分析的基础上,提出在对经典串行PAM算法进行并行时应如何从局部聚类信息生成完备的全局聚类信息,据此提出了算法DPAM,在提高计算性能的同时,使聚类质量等价于相应串行PAM算法。为提高并行算法的执行效率,还介绍了如何减小计算结点间通信的代价。最后对提出的算法进行性能分析和实验,说明该算法是高效可行的。     

面向层次化NoC的混合并行编程模型

为更好发挥多核处理器的硬件性能,针对层次化的片上网络架构,提出MPI/OpenMP混合并行编程模型。运用基于MPI的任务级并行模型实现片内簇间的高效通信,采用OpenMP模型实现簇内四核的通信、同步和数据交换。实验结果表明,与单一并行编程模型相比,混合并行编程模型加速比提高了20%~50%。     

并行k均值聚类算法的完备性证明与实现

对经典k均值算法进行分析,证明如何在减少节点间通信代价的情况下,从局部聚类信息生成完备的全局聚类信息,使聚类质量等价于相应串行算法,并具有较高的执行效率,在此基础上给出可信的基于消息传递接口的并行k均值算法。实验结果表明,该算法是高效的和可行的。     

LBGK模型的分布式并行计算

以二维9速模型D2Q9(LBGK)为例,针对不同集合形状的流场,研究了数据分布与通信量及并行效率之间的关系。在“自强3000”集群式超级计算机上就流场网格的不同规模、多种数据分布及通信方案进行了数值实验。测试结果表明,LBGK模型的并行效率高、可扩展性好,在数据分布方案与流场网格形状相似时,并行效率最高。该结论与理论分析相吻合。     

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

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

P4并行环境的建立过程分析

在使用Linux构建的工作站集群环境下,对支持并行编程的C函数库P4（Portable Programs for Parallel Processors）的初始化过程进行了研究,重点剖析了进程创建和通信建立这两个部分,并对源代码中涉及到的主要数据结构及其使用给出了详尽的分析说明。对研究和开发并行编程工具有一定的参考价值。