Performance evaluation of GPU-based parallel sorting algorithms

doi:10.1371/journal.pone.0342167

Performance evaluation of GPU-based parallel sorting algorithms

2026-02-03

0

PRE

AI

M

Mohammed Alaa Ala’anzy *

DOI：10.1371/journal.pone.0342167

原文链接

原文求助

摘要

En 中文

排序可以采用两种主要方法：顺序排序和并行排序。在顺序排序中，数据以单线程方式处理，对于大型数据集可能较慢。然而，并行排序将任务分配到多个处理单元，通过同时处理数据实现更快的速度。此外，计算统一设备架构（CUDA）技术使开发者能够利用GPU的通用并行计算能力，显著加速排序等任务。本文研究了基于GPU的归并排序（MS）、快速排序（QS）、冒泡排序（BS）、基数Top-k选择排序（RS）和慢速排序（SS）的并行化，并提出了针对现代GPU高效处理大型数据集的优化算法。主要目标是评估这些算法在利用CUDA的GPU上的性能，重点分析不同数据类型下的并行时间复杂度和空间复杂度。实验在四种数据集场景下进行：随机生成数据、逆序数据、已排序数据和近似排序数据。同时，将GPU加速实现的性能与其顺序实现进行比较，以评估计算效率和可扩展性的改进。早期基于GPU的此类实现通常比标量CPU代码实现获得2倍至9倍的加速比。随着新一代GPU的增强，包括并行感知基元和基数或归并优化操作，加速比得到显著提升。我们的实验表明，基于GPU的基数排序在1000万个随机排序元素上实现了约50倍的显著加速（顺序：240.8 ms，并行：4.83 ms）；快速排序和归并排序分别实现了97倍和103倍的加速（快速：1461.97 ms vs. 15.1 ms；归并：2212.33 ms vs. 21.4 ms）。冒泡排序在并行实现中显著改善（从123,321.9 ms降至7377.8 ms，约17倍改进），但整体性能较差。慢速排序展示了适度但一致的加速，执行时间从顺序版本的74.07 ms减少到GPU上的3.99 ms，实现了约18.6倍的加速。这些实验结果表明，新的单GPU实现可达到17倍至超过100倍的加速，超过以往报告的典型增益，并与近期研究中报道的前沿并行排序算法的加速率相当或更高。

Keyword:

GPU-based parallel sorting

CUDA

merge sort

quick sort

radix sort

Performance evaluation of GPU-based parallel sorting algorithms

摘要

期刊

机构

引用论文