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

发布时间：2017-09-22 17:17

  本文关键词：阵列众核处理器上的高效归并排序算法

  更多相关文章： 阵列众核 归并排序 排序网络 单指令多数据流 单程序多数据流 片上通信

【摘要】：排序是计算机科学中最基本的问题之一,随着众核处理器结构的不断发展,设计众核结构上的高效排序算法具有重要意义.众核处理器的一个重要方向是阵列众核处理器,根据阵列众核处理器的结构特点,提出了2种面向阵列众核结构的高效归并排序算法,通过利用DMA(direct memory access)多缓冲机制提高访存效率、深度平衡归并策略保持众多核心之间的负载均衡、SIMD(single instruction multiple data)归并方法提高归并计算效率以及片上交换归并策略提高片上数据重用率,大幅度提高了阵列众核处理器的排序性能.在异构融合阵列众核处理器DFMC(deeply-fused many-core)原型系统的实验结果表明,算法排序速度达647MKeys/s(million keys per second),其排序效率(排序速度/峰值性能)是NVIDIA GPU上最快的归并排序算法(GTX580平台)的3.3倍,是Intel Xeon Phi上最快的归并排序算法的2.7倍.最后,建立了阵列众核处理器上归并排序算法的性能分析模型,利用该模型分析了主要结构参数与算法性能的关系,对阵列众核处理器的研究有一定的指导意义.
【作者单位】： 江南计算技术研究所;
【关键词】： 阵列众核 归并排序 排序网络 单指令多数据流 单程序多数据流 片上通信
【基金】：国家“八六三”高技术研究发展计划基金项目(2014AA01A301) “核高基”国家科技重大专项基金项目(2013zx0102-8001-001-001)~~
【分类号】：TP301.6;TP332
【正文快照】： 排序是计算机科学及算法研究中最基本、最重要的研究问题之一[1],是数据库、图运算、科学计算以及大数据等诸多重要应用的基础,排序效率对这些应用程序的性能有重要的影响,在不同计算平台和环境上不断提高排序的性能,具有重要的现实意义.近年来,众核处理器在学术界和工业界得

【相似文献】

中国期刊全文数据库 前1条

1 阚圣哲;曹宗雁;;众核GPU上双调归并排序的优化[J];科研信息化技术与应用;2011年05期

，

本文编号：902073