基于GPU的并行排序算法设计与优化

利用GPU来加速科学问题的求解已成为高性能计算的一个重要研究方向，而排序算法是一个非常基础的算法，设计基于GPU的并行排序算法可以直接支持一大类科学计算应用。基于对GPU内部层次化内存模型和流处理单元的抽象与分析，设计实现层次化确定性采样排序算法，该算法与同类型的并行排序算法相比，能够更加有效的利用GPU的高并行性和层次化内存模型。同时，本研究深入对比GPU和CPU特点，设计并实现基于CPU-GPU协同工作的快速排序算法。不仅对这些算法进行理论分析，本研究还设计开发原型系统进行实验验证，将理论和实验结果进行对比分析，进一步对本研究提出的优化方法、算法以及相应的程序实现进行改进和提高，并结合MapReduce并行计算框架对本研究成果进行实际应用。本研究提供的基础性理论与方法一方面可充分挖掘GPU计算潜力，另一方面对广泛的应用问题和领域在新型加速器增强型体构上提供高效支持。

利用GPU来加速科学问题的求解已成为高性能计算的一个重要研究方向，而排序算法是一个非常基础的算法，设计基于GPU的并行排序算法可以直接支持一大类科学计算应用。在充分了解GPU硬件体系结构与已有的各种排序算法性能特点的基础上，本研究提出并实现了一种集成优化的GPU排序方法，将桶排序、快速排序、归并排序等在不同的阶段有效集成起来，结合双缓冲等优化手段，可以有效均衡负载并大幅提高算法的整体性能。此外，通过对比GPU和CPU特点，设计并实现基于CPU-GPU协同工作的排序算法；在已知数据集特点的情况下，设计实现了更为有效的定制排序算法。通过设计开发原型系统对各种算法进行了实验验证，测试结果表明本研究提出的方法可以高效处理不同规模、不同数据分布特点的数据集。我们还进一步将本研究得到的经验与成果应用到一些大型实用程序的数据处理（性能提高50倍）与模拟分析（性能提高10倍）中，这些工作充分展示了本研究不仅在基础性算法设计、优化与分析方面，而且在对这些基础性成果的应用方面，都取得了显著的成果。