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

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

Optimal bitonic sort for graphics hardware

A novel parallel sorting is presented.This algorithm is based bitonic merge-sort scheme.The benefit of using GPU's parallel architecture and a binary tree improve the approach.Instead of a completely sequential execution of all stages,the approach is executed them partially overlapped.For sorting n keys utilizing p stream processor units,this approach achieves the optimal time complexity O((nlogn) /p).The approach performs very well in practice,which is caused by several optimizations.Furthermore,the approa...