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):297-300.
基于MPI和OpenMP的排序算法并行优化研究
- Title:
- The Performance Analysis of Sorting Algorithms based on MPI and OpenMP
- 文章编号:
- 2096-1618(2016)03-0277-08
- 关键词:
- 排序是计算机程序设计中的一项重要操作; 其性能好坏决定整个程序性能的优劣。针对常见的快速排序、冒泡排序、归并排序、计数排序和选择排序这5种排序算法; 分别用MPI(message passing Interface)和OpenMP(open multi-processing)并行化编程环境对其进行并行程序优化; 研究分析MPI和OpenMP并行优化时的优缺点; 并对比不同并行化技术下的加速比和开销等性能; 为更高效的排序算法的并行程序设计奠定基础。
- 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.
备注/Memo
收稿日期:2016-04-11 基金项目:四川省科技计划资助项目(2012GZ0111)