基于图形硬件的双调排序算法优化

摘要：

介绍一种新的并行排序算法,该算法以双调归并排序为基础,运用图形硬件的并行体系结构和二叉排序树数据结构的优点,用部分并行代替所有阶段的顺序执行,对双调排序算法进行优化.对该算法进行分析,在理论上n个序列在P个流处理器上的排序,最优的时间复杂度为O((nlogn)/p).实验测试结果表明,优化后的算法比其它基于图形硬件的双调归并排序算法所用时间短.

关键词：双调归并排序、流计算、图形处理器、归并、算法优化、排序网

所属期刊栏目：29

分类号：TP301.6(计算技术、计算机技术)

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

页数：共3页

页码：3660-3662