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

来源：计算机研究与发展杂志2016年第2期北京时间：

作者：石嵩,李宏亮,朱巍,

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

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