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

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

作　　者：柯琦[1,2] 钟诚[1] 陈清媛[1] 陆向艳[1] 

机构地区：[1]广西大学计算机与电子信息学院,南宁530004 [2]广西财经学院信息与统计学院,南宁530003

出　　处：《计算机应用》2013年第3期821-824,共4页journal of Computer Applications

基　　金：国家自然科学基金资助项目(60963001)

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

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

分 类 号：TP338.6[自动化与计算机技术—计算机系统结构] TP301.6[自动化与计算机技术—计算机科学与技术]