多核机群上通信高效的整数序列并行排序方法

doi:10.3724/SP.J.1087.2013.00821

计算机应用 ›› 2013, Vol. 33 ›› Issue (03): 821-824.DOI: 10.3724/SP.J.1087.2013.00821

多核机群上通信高效的整数序列并行排序方法

柯琦^1,2,钟诚^1*,陈清媛¹,陆向艳¹

1.广西大学计算机与电子信息学院, 南宁 530004;
2.广西财经学院信息与统计学院, 南宁 530003

收稿日期:2012-09-24 修回日期:2012-11-01 出版日期:2013-03-01 发布日期:2013-03-01
通讯作者: 钟诚
作者简介:柯琦(1985-),女,广西恭城人,助教,硕士,主要研究方向:并行分布计算; 钟诚(1964-),男,广西桂平人,教授,博士生导师,博士,主要研究方向:并行分布计算、可信计算与软件; 陈清媛(1987-),女,贵州金沙人,硕士研究生,主要研究方向:可信计算与软件; 陆向艳(1973-),女,广西南宁人,副教授,主要研究方向:并行分布计算。
基金资助:
国家自然科学基金资助项目(60963001)。

Communication-efficient parallel sorting integers sequence on multi-core cluster

KE Qi^1,2, ZHONG Cheng^1*, CHEN Qingyuan¹, LU Xiangyan¹

1.Computer and Electronic Information College, Guangxi University, Nanning Guangxi 530004, China;
2.School of Information and Statistics, Guangxi University for Finance and Economics, Nanning Guangxi 530003, China

Received:2012-09-24 Revised:2012-11-01 Online:2013-03-01 Published:2013-03-01

摘要/Abstract

摘要： 建立一个适用于整数序列排序的数据分配模型,在多核计算节点组成的异构机群上设计通信高效的整数序列并行算法。所提出的数据分配模型依据机群中各节点不同的计算能力、通信速率和存储容量,动态计算出调度分配给各节点的数据块的大小以平衡各个节点的负载。所设计的并行排序算法利用整数序列的特性,主节点采取两轮分发数据与接收结果的方法,从节点运用分桶打包方式返回有序的整数子序列给主节点,主节点采用桶映射方法将各个有序子序列直接整合成最终有序序列,以减少需要耗费较多通信时间的数据归并操作。分析与实验测试结果表明,给出的多核机群上的整数序列并行排序算法高效,具有良好的可扩展性。

关键词: 整数排序, 并行算法, 多核机群, 数据分配

Abstract: A data distribution strategy and a communication-efficient parallel algorithm for sorting integers sequence were proposed on the heterogeneous cluster with multi-core machines. The presented data distribution model properly utilized different computation speed, communication rate and memory capacity of each computing node to dynamically compute the size of the data block to be assigned to each node to balance the loads among nodes. In the proposed parallel sorting algorithm, making use of the characteristic of integers sequence, master node distributed the data blocks to the salve nodes and received the sorted subsequences with two-round mode, each salve node returned its sorted subsequence to master node by bucket-packing method, and master node linked its received sorted subsequences to form directly a final sorted sequence by the bucket mapping in order to reduce the data merge operations with large communication cost. The analysis and experimental results on the heterogeneous cluster with multi-core machines show that the presented parallel sorting integers sequence algorithm is efficient and scalable.

Key words: integers sorting, parallel algorithm, multi-core cluster, data distribution

中图分类号:

柯琦钟诚陈清媛陆向艳. 多核机群上通信高效的整数序列并行排序方法[J]. 计算机应用, 2013, 33(03): 821-824.

KE Qi ZHONG Cheng CHEN Qingyuan LU Xiangyan. Communication-efficient parallel sorting integers sequence on multi-core cluster[J]. Journal of Computer Applications, 2013, 33(03): 821-824.

参考文献

[1]INOUE H, MORIYAMA T, KOMATSU H, et al. AA-Sort: a new parallel sorting algorithm for multi-core SIMD processors [C]// Proceedings of the 16th International Conference on Parallel Architecture and Compilation Techniques. Washington, DC: IEEE Computer Society, 2007:189-198.
[2]RAMPRASAD N, BARUAH P K. Radix sort on the cell broadband engine [C]// HiPC2007: Proceedings of the 14th Annual IEEE International Conference on High Performance Computing. Piscataway, NJ: IEEE Press, 2007.
[3]CEDERMAN D, TSIGAS P. On sorting and load balancing on GPU [J]. ACM SIGARCH Computer Architecture News,2008,36(5):11-18.
[4]GREB A, ZACHMANN G. GPU-ABiSort: optimal parallel sorting on stream architectures [C]// Proceedings of the 20th International Parallel and Distributed Processing Symposium. Washington, DC: IEEE Computer Society, 2006: 25-29.
[5]HAO S, DU Z, BADER D, et al. A partition-merge based cache-conscious parallel sorting algorithm for CMP with shared cache [C]// Proceedings of the 38th International Conference on Parallel Processing. Washington, DC: IEEE Computer Society, 2009:396-403.
[6]HULTN R, KESSLER C W, KELLER J. Optimized on-chip-pipelined mergesort on the Cell/B.E. [C]// Proceedings of the 16th International Euro-Par Conference on Parallel Processing, Part Ⅱ. Berlin: Springer-Verlag, 2010: 187-198.
[7]SATISH N, KIM C, CHHUGANI J, et al. Fast sort on CPUs and GPUs: a case for bandwidth oblivious SIMD sort [C]// Proceedings of 2010 ACM SIGMOD International Conference on Management of data. New York: ACM Press, 2010: 351-362.
[8]ZHONG C, QU Z Y, YANG F, et al. Efficient and scalable thread-level parallel algorithms for sorting multisets on multi-core systems [J]. Journal of Computers, 2012,7(1):30-41.
[9]ZHONG C, KE Q, LIU J, et al. Thread-level parallel algorithm for sorting integer sequence on multi-core computers [C]// Proceedings of the 4th International on Parallel Architectures, Algorithms and Programming. Washington, DC: IEEE Computer Society, 2011: 37-41.
[10]ZHONG C, FENG P, YIN M X, et al. Sampling-based cache-efficient parallel sorting on multi-core systems [J]. Journal of Computational Information Systems, 2012, 8(8):6713-6722.
[11]ZHONG C, LI X, YANG F, et al. Scheduling divisible loads with return messages on multi-core heterogeneous clusters with unknown system parameters [J]. International Journal of Advancements in Computing Technology, 2012, 4(7):110-120.
[12]柯琦,钟诚,李智,等. 多核计算机上的最大和子序列并行算法[C]// 计算机技术与应用进展2010.合肥:中国科学技术大学出版社, 2010: 586-590.
[13]陈国良. 并行计算——结构·算法·编程 [M]. 修订版. 北京:高等教育出版社, 2003: 140-141.

[1]	付朝江, 王天奇, 林悦荣. 基于有效并行求解策略的显式有限元分析并行算法[J]. 计算机应用, 2018, 38(4): 1072-1077.
[2]	陈羽中, 郭松荣, 陈宏, 李婉华, 郭昆, 黄启成. 基于并行分类算法的电力客户欠费预警[J]. 计算机应用, 2016, 36(6): 1757-1761.
[3]	褚征, 于炯, 鲁亮, 英昌甜, 卞琛, 王跃飞. 基于内存云的大块数据对象并行存取策略[J]. 计算机应用, 2016, 36(6): 1526-1532.
[4]	王春波, 董红斌, 印桂生, 刘文杰. 基于Hadoop的超像素分割算法[J]. 计算机应用, 2016, 36(11): 2985-2992.
[5]	何莉, 刘晓东, 李松阳, 张倩. 多核环境下并行粒子群算法[J]. 计算机应用, 2015, 35(9): 2482-2485.
[6]	李双李文敬孙环龙林中明. 基于多核机群的人工鱼群并行算法[J]. 计算机应用, 2013, 33(12): 3380-3384.
[7]	庹清宋耀虎. 基于Java的按位拆分快速排序并行算法[J]. 计算机应用, 2012, 32(09): 2455-2457.
[8]	王海峰. 快速复杂网络聚类图形处理器并行算法[J]. 计算机应用, 2012, 32(09): 2458-2462.
[9]	袁晖坪. 广义行（列）对称矩阵的QR分解及其算法[J]. 计算机应用, 2012, 32(04): 990-993.
[10]	周凯汀郑力新林福泳. 周期B样条基函数系数的并行算法[J]. 计算机应用, 2011, 31(07): 1800-1803.
[11]	苗莎郑晓薇. 三次插值样条曲线拟合多核并行算法[J]. 计算机应用, 2010, 30(12): 3194-3196.
[12]	蔡昭权魏文红王高才郑宗晖卢庆武. 一种基于De Bruijn网络结构的并行矩阵乘算法[J]. 计算机应用, 2009, 29(3): 880-883.
[13]	魏文红李清霞王文丰. 一种基于Biswapped网络的并行矩阵乘算法[J]. 计算机应用, 2009, 29(12): 3218-3220.
[14]	冯高锋. 基于Cell多核的光线投射并行算法[J]. 计算机应用, 2009, 29(1): 245-247,.
[15]	郭静田有先. 基于像素预判的各向异性扩散并行图像恢复[J]. 计算机应用, 2009, 29(05): 1353-1358.

多核机群上通信高效的整数序列并行排序方法

Communication-efficient parallel sorting integers sequence on multi-core cluster

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics