阵列众核处理器上的高效归并排序算法

摘要：

排序是计算机科学中最基本的问题之一,随着众核处理器结构的不断发展,设计众核结构上的高效排序算法具有重要意义.众核处理器的一个重要方向是阵列众核处理器,根据阵列众核处理器的结构特点,提出了2种面向阵列众核结构的高效归并排序算法,通过利用DMA(direct memory access)多缓冲机制提高访存效率、深度平衡归并策略保持众多核心之间的负载均衡、SIMD (single instruction multiple data)归并方法提高归并计算效率以及片上交换归并策略提高片上数据重用率,大幅度提高了阵列众核处理器的排序性能.在异构融合阵列众核处理器DFMC(deeply-fused many-core)原型系统的实验结果表明,算法排序速度达647 MKeys/s(million keys per second),其排序效率(排序速度/峰值性能)是NVIDIA GPU上最快的归并排序算法(GTX580平台)的3.3倍,是Intel Xeon Phi上最快的归并排序算法的2.7倍.最后,建立了阵列众核处理器上归并排序算法的性能分析模型,利用该模型分析了主要结构参数与算法性能的关系,对阵列众核处理器的研究有一定的指导意义.

关键词：阵列众核、归并排序、排序网络、单指令多数据流、单程序多数据流、片上通信

所属期刊栏目：53

分类号：TP302(计算技术、计算机技术)

资助基金：国家“八六三”高技术研究发展计划基金项目2014AA01A301;“核高基”国家科技重大专项基金项目2013zx0102-8001-001-001This work was supported by the National High Technology Research and Development Program of China 863 Program2014AA01A301;the National Science and Technology Major Projects of Hegaoji2013zx0102-8001-001-001

在线出版日期：2016-06-01（万方平台首次上网日期，不代表论文的发表时间）

页数：共12页

页码：362-373