ZHANG Tian-yang,CHEN Hua.Quick Sort Algorithm based on Four Parallel Patterns[J].Journal of Chengdu University of Information Technology,2018,(01):13-17.[doi:10.16836/j.cnki.jcuit.2018.01.003]
基于4种并行模式的快速排序算法
- Title:
- Quick Sort Algorithm based on Four Parallel Patterns
- 文章编号:
- 2096-1618(2018)01-0013-05
- 关键词:
- 快速排序作为一种先进的排序算法; 以其优异的性能广泛应用于众多领域。然而; 传统的串行快速排序算法是单线程模式进行; 不能充分利用CPU的多个线程。针对上述问题; 基于包括Windows API、OpenMP、MPI和PPL的4种并行模式; 设计了一种并行的多线程快速排序算法; 对并行计算容易出现的数据竞争问题给出解决方案。设计的并行快速排序算在多线程计算机上进行实验并与单线程算法进行比较; 结果表明并行快速排序算法减小了时间开销; 达到了比较理想的线性加速效果。
- Keywords:
- quick sort; parallel algorithm; Windows API; OpenMP; MPI; PPL
- 分类号:
- TP302.7
- 文献标志码:
- A
- 摘要:
- 快速排序作为一种先进的排序算法,以其优异的性能广泛应用于众多领域。然而,传统的串行快速排序算法是单线程模式进行,不能充分利用CPU的多个线程。针对上述问题,基于包括Windows API、OpenMP、MPI和PPL的4种并行模式,设计了一种并行的多线程快速排序算法,对并行计算容易出现的数据竞争问题给出解决方案。设计的并行快速排序算在多线程计算机上进行实验并与单线程算法进行比较,结果表明并行快速排序算法减小了时间开销,达到了比较理想的线性加速效果。
- Abstract:
- As an advanced sorting algorithm, quick sort is widely applied in many fields with its excellent performance. However, the traditional serial quick sort algorithm works on the single thread mode, and it cannot make full advantage of multi-threads of CPU. As to the problem mentioned above, a kind of multi-threads parallel quick sort algorithm is designed and the solution to the data race which is likely arising in parallel computing is given, based on four parallel patterns including Windows API, OpenMP, MPI and PPL. The designed parallel quick sort algorithm is evaluated in a multi-threads computer compared with the single thread algorithm.The results indicate that the parallel quick sort algorithm reduces the time overhead and achieves an ideal linear acceleration effect.
参考文献/References:
[1] Cormen T H,Leiserson C E,Rivest R L,et al.Introduction to Algorithms[M].MIT Press,2001.
[2] 陈国良.并行算法实践[M].北京:高等教育出版社,2004.
[3] 黄伟,赖国明.基于群集系统的快速排序并行化方法[J].现代计算机(专业版),2005,(5):89-91.
[4] 游佐勇,罗省贤.多核计算环境下快速排序并行算法的实现[J].电脑与电信,2011,(1):60-62.
[5] 刘向娇,赵学武.改进的并行快速排序[J].计算机与数字工程,2014,42(5):782-784.
[6] 王帅,喻歆,何嘉.基于MPI和OpenMP的排序算法并行优化研究[J].成都信息工程大学学报,2016,31(3):277-284.
[7] 石壬息,张锦雄,王钧,等.快速排序异步并行算法的多线程实现[J].广西科学院学报,2005,(s1):54-55,65.
[8] 张火林,李国庆,张江维.基于双核系统的快速排序效率分析[J].电脑知识与技术,2008,3(8):705-707.
[9] 李跃新,周四维.并行计算中快速排序算法的改进[J].湖北第二师范学院学报,2011,8(8):1-3.
[10] 周伟明.多核计算与程序设计[M].武汉:华中科技大学出版社,2009.
[11] 周恩强,赵军锁,杨学军.MPI及MPI的高效实现[J].计算机工程与科学,1999,21(5):47-51.
[12] 严蔚敏,吴伟民.数据结构(C语言版)[M].北京:清华大学出版社,2010.
备注/Memo
收稿日期:2017-06-29基金项目:国家自然科学基金资助项目(41474100); 山东省自然科学基金项目(ZR2013DM015)