Analysis-driven Engineering of Comparison-based Sorting Algorithms on GPUs
Analysis-driven Engineering of Comparison-based Sorting Algorithms on GPUs
复制标题
DOI：
10.1145/3205289.3205298
复制
发表时间：
2018-06
期刊：
影响因子：
--
通讯作者：
Ben Karsin;Volker Weichert;H. Casanova;J. Iacono;Nodari Sitchinava
中科院分区：
文献类型：
--
作者：
Ben Karsin;Volker Weichert;H. Casanova;J. Iacono;Nodari Sitchinava
我们研究图形处理单元 (GPU) 基于比较的排序算法中内存访问、存储体冲突、线程多重性（也称为超额订阅）和指令级并行性之间的关系。我们通过实验验证了所提出的公式，该公式将这些参数与算法对内存访问次数的渐近分析联系起来。使用这个公式，我们分析并比较了几种 GPU 排序算法，确定了每种算法的关键性能瓶颈。基于此分析，我们提出了一种 GPU 高效的多路合并排序算法 GPU-MMS，它可以最大限度地减少或消除这些瓶颈，并平衡特定硬件的各种限制因素。我们实现了 GPU-MMS 的实现，并将其与三种 GPU 架构上最先进的 GPU 库中的排序算法实现进行比较。尽管这些库实现经过高度优化，但我们发现 GPU-MMS 在随机整数输入方面比它们平均高出 21%，在随机键值对方面比它们平均高出 14%。
We study the relationship between memory accesses, bank conflicts, thread multiplicity (also known as over-subscription) and instruction-level parallelism in comparison-based sorting algorithms for Graphics Processing Units (GPUs). We experimentally validate a proposed formula that relates these parameters with asymptotic analysis of the number of memory accesses by an algorithm. Using this formula we analyze and compare several GPU sorting algorithms, identifying key performance bottlenecks in each one of them. Based on this analysis we propose a GPU-efficient multiway merge-sort algorithm, GPU-MMS, which minimizes or eliminates these bottlenecks and balances various limiting factors for specific hardware. We realize an implementation of GPU-MMS and compare it to sorting algorithm implementations in state-of-the-art GPU libraries on three GPU architectures. Despite these library implementations being highly optimized, we find that GPU-MMS outperforms them by an average of 21% for random integer inputs and 14% for random key-value pairs.