WANG Shuai,YU Xin,HE Jia.The Performance Analysis of Sorting Algorithms based on MPI and OpenMP[J].Journal of Chengdu University of Information Technology,2016,(03):277-284.
基于MPI和OpenMP的排序算法并行优化研究
- Title:
- The Performance Analysis of Sorting Algorithms based on MPI and OpenMP
- 文章编号:
- 2096-1618(2016)03-0277-08
- Keywords:
- computer application; high performance computing; sorting; parallel programming; speedup; MPI; openMP
- 分类号:
- TP302.7
- 文献标志码:
- A
- 摘要:
- 排序是计算机程序设计中的一项重要操作,其性能好坏决定整个程序性能的优劣。针对常见的快速排序、冒泡排序、归并排序、计数排序和选择排序这5种排序算法,分别用MPI(message passing Interface)和OpenMP(open multi-processing)并行化编程环境对其进行并行程序优化,研究分析MPI和OpenMP并行优化时的优缺点,并对比不同并行化技术下的加速比和开销等性能,为更高效的排序算法的并行程序设计奠定基础。
- Abstract:
- Sorting is an important operation of designing a computer program. Its performance usually determines the quality of the whole program. This paper carries out parallel optimization of five common sorting algorithms, including quick sort, bubble sort, merge sort, counting sort and select sort, based on the MPI(Message Passing Interface)and OpenMP(Open Multi-Processing)parallel programming environment. The pros and cons using MPI and OpenMP are analyzed, and the performances including speedup and overhead are compared. The purpose of this paper is to lay the foundation for designing more efficient parallel sorting programs.
参考文献/References:
[1] Cormen T H,Leiserson C E,Rivest R L,et al.Introduction to Algorithms[M].2nd ed.The MIT Press,2001.
[2] Dongarra J.The top 10 Algorithms[J].IEEE Computing in Science & Engineering,2000,2(1):22-23.
[3] Innovative Computing Lab University of Tennessee.Advance MPI[R]. DavidCronk:Tennessee,2004.
[4] OpenMP Forum.OpenMP Fortran Application Program Interface[M].2000:15-25.
[5] David Kuek.OpenMP Overview[J].WOMPAT,2000:20-25.
[6] 郑国彪,曹侃宇.冒泡排序法及其改进[J].青海大学学报:自然科学版,2002,20(3):43 -46.
[7] 谭浩强.C语言程序设计[M].北京:清华大学出版社,2001.
[8] C A R Hoare.Quicksort[J].The Computer,1962,15(1):10-15.
[9] 严蔚敏,吴伟民. 数据结构(C语言版)[M].北京:清华大学出版社,2014:283-284.
[10] Annay Levitin.The Design and Analysis of Algorithms[M].Beijing:Tsinghua University Press,2004.
[11] 梁利刚,易超,杨绣丞,等.静态排序算法设计与分析[J].计算机应用与软件,2012,29(3):283-286.
[12] Donald E,Knuth.Art of Computer Programming Volume3[M].Sorting And Searching.(2nd Edition),2012.
[13] 张军.多核集群下一种混合并行编程模型的研究[J].计算机应用,2009.
[14] 蒋沁谷.GRAPES全球模式MPI和OpenMP混合并行方法[J].数值天气预报,2014.
[15] Rabenseifner R,Hager G,Jost G,et al.Hybrid MPI and OpenMP parallel programming[C].2006:11.
[16] Smith L,Bull M.Development of mixed model MPI/OpenMP Applications[J].Scientific Programming,2001,9(2):83-98.
[17] 李建江,薛巍,张武生,等.并行计算机及编程基础[M].北京:清华大学出版社,2011.
[18] 李晋.进程的多对多(M:N)线程模型研究[J].计算机系统结构,2009.
相似文献/References:
[1]崔栋才,胡志恒.一种用于6LoWPAN的低功耗路由协议[J].成都信息工程大学学报,2018,(01):28.[doi:10.16836/j.cnki.jcuit.2018.01.006]
CUI Dong-cai,HU Zhi-heng.A Low-power Routing Protocol for 6LoWPAN[J].Journal of Chengdu University of Information Technology,2018,(03):28.[doi:10.16836/j.cnki.jcuit.2018.01.006]
[2]张 超,孙绩华,段 玮.云南区域站降水资料利用Surfer软件实现Cressman插值的研究[J].成都信息工程大学学报,2018,(01):84.[doi:10.16836/j.cnki.jcuit.2018.01.015]
ZHANG Chao,SUN Ji-hua,DUAN Wei.Research on Cressman Interpolation using Surfer Software based onPrecipitation data of Yunnan Regional Station[J].Journal of Chengdu University of Information Technology,2018,(03):84.[doi:10.16836/j.cnki.jcuit.2018.01.015]
[3]陈 琳,李 容.基于动态Web的Python多线程空气质量数据程序设计[J].成都信息工程大学学报,2016,(02):180.
CHEN Lin,LI Rong.Python Multithreaded Air Pollution Products Program based on Dynamic Web[J].Journal of Chengdu University of Information Technology,2016,(03):180.
[4]杨馥溢,杨 璐,魏 敏,等.星空背景的多运动小目标检测方法[J].成都信息工程大学学报,2016,(06):583.
YANG Fu-yi,YANG Lu,WEI Min,et al.The Method for Multi-Moving Small Target under Celestial Background[J].Journal of Chengdu University of Information Technology,2016,(03):583.
[5]张广超,马尚昌,张素娟.降水现象仪模拟软件设计与实现[J].成都信息工程大学学报,2016,(06):588.
YANG Fu-yi,YANG Lu,WEI Min,et al.The Method for Multi-Moving Small Target under Celestial Background[J].Journal of Chengdu University of Information Technology,2016,(03):588.
[6]韦晶晶,李国平.一次东南路径西南低涡引发广西强降水的
湿位涡和二阶湿位涡特征[J].成都信息工程大学学报,2016,(06):592.
WEI Jing-jing,LI Guo-ping.Characteristic of Moist Potential Vorticity and Second Order Moist
Potential Vorticity of Heavy Rainfall over Guangxi Cause by
Southwest Vortex of Southeast Path[J].Journal of Chengdu University of Information Technology,2016,(03):592.
[7]赵鑫宁,喻 歆,吴 锡.一种基于混合概率选择算子的改进遗传算法[J].成都信息工程大学学报,2016,(03):247.
ZHAO Xin-ning,YU Xin,WU Xi.Improving Genetic Algorithm based on A Hybrid Probabilistic Selector[J].Journal of Chengdu University of Information Technology,2016,(03):247.
[8]孙蓓蕾,陈高云.基于多策略的个性化智能组卷的研究[J].成都信息工程大学学报,2016,(03):261.
SUN Bei-lei,CHEN Gao-yun.Studies on the Intelligent Composing Paper with Multi-strategy and Individuality[J].Journal of Chengdu University of Information Technology,2016,(03):261.
备注/Memo
收稿日期:2016-04-11 基金项目:四川省科技计划资助项目(2012GZ0111)