MPI_ALLGATHER实现算法的改进与性能分析

计算机工程与应用 ›› 2007, Vol. 43 ›› Issue (27): 66-71.

MPI_ALLGATHER实现算法的改进与性能分析

李占胜¹,毕会娟¹,都志辉²,焦青³

1.华北计算技术研究所软件平台研究室,北京 100083
2.清华大学计算机科学与技术系,北京 100084
3.鲁东大学图书馆,山东烟台 264025

收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2007-09-21 发布日期:2007-09-21
通讯作者: 李占胜

Improvement and performance analysis of MPI_ALLGATHER algorithm

LI Zhan-sheng¹,BI Hui-juan¹,DU Zhi-hui²,JIAO Qing³

1.Department of Software Platform,North China Institute of Computing Technology,Beijing 100083,China
2.Department of Computer Science and Technology,Tsinghua University,Beijing 100084,China
3.Library of Ludong University,Yantai,Shandong 264025,China

Received:1900-01-01 Revised:1900-01-01 Online:2007-09-21 Published:2007-09-21
Contact: LI Zhan-sheng

摘要/Abstract

摘要： 首先分析了影响MPI组通信性能的各方面因素,提出了一种衡量算法性能的模型。基于这种分析及模型,提出了一种将邻居交换和递归倍增两种算法结合的新的MPI_ALLGATHER实现算法。新的算法比邻居交换算法通信次数少,比递归倍增算法具有较好的通信局部性。通过在高性能机群系统中的测试,发现新算法在多种情况下比邻居交换算法具有更优的性能,在中等长度消息通信时具有最优的性能,在长消息通信时性能比递归倍增算法和Bruck算法的性能更优,且在长消息通信时多数情况下性能最优。

关键词: 并行编程, MPI, 组通信, MPI_ALLGATHER算法

Abstract: We discuss issues related to the high performance implementation of collective communication operations in MPICH for clusters in this paper.The Ring and Neighbor Exchange algorithms have the best communication locality property,and they have more communication steps than others.The Recursive Doubling and Bruck algorithms have less communication steps,and they have worse communication locality property than others.Based on the discussion,we present a new MPI_ALLGATHER algorithm that combines the Neighbor Exchange and Recursive Doubling algorithms.The new algorithm has less data transfer times than the Neighbor Exchange algorithm and better communication locality property than the Recursive Doubling algorithm.We evaluate the new algorithm in Myrinet cluster and find that the new algorithm performs better than the Neighbor Exchange algorithm and sometimes performs the best for medium-size messages among all the algorithms.The new algorithm also performs better for long-size messages than the Recursive Doubling and Bruck algorithms.

Key words: parallel programming, Message Passing Interface（MPI）, collective communication, MPI_ALLGATHER

李占胜¹,毕会娟¹,都志辉²,焦青³. MPI_ALLGATHER实现算法的改进与性能分析[J]. 计算机工程与应用, 2007, 43(27): 66-71.

LI Zhan-sheng¹,BI Hui-juan¹,DU Zhi-hui²,JIAO Qing³. Improvement and performance analysis of MPI_ALLGATHER algorithm[J]. Computer Engineering and Applications, 2007, 43(27): 66-71.

[1]	刘世永，陈荦，熊伟，吴烨，李军. 基于MPI的大规模栅格影像并行瓦片化算法[J]. 计算机工程与应用, 2018, 54(1): 48-53.
[2]	薛俊韬，翁玉茹，张军. 基于EMD和交叉熵的语音端点检测算法[J]. 计算机工程与应用, 2016, 52(20): 149-153.
[3]	董丽丽，董玮，张翔. 利用CUDA提高内存数据聚类效能的研究[J]. 计算机工程与应用, 2015, 51(22): 243-251.
[4]	李金忠，汤鹏杰，夏洁武，谭云兰. 迭代式MapReduce研究进展[J]. 计算机工程与应用, 2015, 51(12): 123-132.
[5]	余婧，曹菡，靳朋飞. Voronoi图k阶邻近并行矩阵迭代算法[J]. 计算机工程与应用, 2014, 50(6): 102-105.
[6]	李奔驰1，2，党创寅2，郑津津1. 分布式整数规划及其在航线扰动问题的应用[J]. 计算机工程与应用, 2013, 49(14): 19-24.
[7]	肖红林1，2，王连生3. 基于MPI的伪谱法DNS并行计算方法研究[J]. 计算机工程与应用, 2012, 48(4): 54-55.
[8]	黄华林1，2，钟诚1. 多核机群上数据密集型应用并行程序性能优化[J]. 计算机工程与应用, 2012, 48(30): 73-77.
[9]	丁汝一，杨宁，董道国. 音视频相结合的广告检测算法[J]. 计算机工程与应用, 2012, 48(22): 184-188.
[10]	付朝江. 基于龙格库塔法的弹塑性有限元并行计算[J]. 计算机工程与应用, 2011, 47(27): 52-54.
[11]	赵军1，2，吴建平2，宋君强2，辜旭赞1. 多核环境下AREM模式混合并行计算研究[J]. 计算机工程与应用, 2011, 47(21): 61-63.
[12]	葛亮，姜晓峰，倪小军. 一种云场景的实时渲染方法[J]. 计算机工程与应用, 2011, 47(11): 167-170.
[13]	卢照，师军. 并行最短路径搜索算法的设计与实现[J]. 计算机工程与应用, 2010, 46(3): 69-71.
[14]	薛淞文，申卫昌，剡公孝，乔龙. 随机模式匹配并行算法在工作站机群上的实现[J]. 计算机工程与应用, 2010, 46(21): 129-131.
[15]	陶冶，曾志勇. Robust的分布式k中心聚类算法的研究与实现[J]. 计算机工程与应用, 2009, 45(32): 122-125.