GPU排序新突破：Onesweep LSD基数排序算法

"Onesweep是一种针对GPU的更快的最小位数字基数排序算法，由NVIDIA Corporation的Andy Adinets和Duane Merrill提出。该算法专为处理存储在全局内存中的大规模数据排序问题设计，显著降低了最后级别内存流量，提高了排序效率。在NVIDIA A100 GPU上，Onesweep在排序256M随机32位键时可达到29.4 GKey/s的速度，相比CUB有约1.5倍的性能提升。" 在计算机科学领域，排序算法是数据处理的重要部分，特别是在高性能计算和大数据处理中。GPU（图形处理单元）由于其并行计算能力，已经成为解决大规模计算问题的首选平台。然而，有效地在GPU上执行排序任务仍然是一个挑战，因为需要处理大量数据并减少内存访问的开销。 Onesweep算法引入了一种创新的单次传递前缀和方法，用于最小位数字（LSD）基数排序。传统的GPU基数排序通常需要两次遍历来完成每个数字位的分配，导致较高的全局内存操作数量。Onesweep通过一次遍历就完成这个过程，显著减少了内存交互次数，大约只需要2n次全局读写操作，从而降低了内存带宽的需求，这对于GPU性能至关重要。 在性能比较方面，Onesweep在处理随机32位键时表现优异，速度比CUB（目前最先进的GPU LSD基数排序库）快约1.5倍。这表明Onesweep在处理大规模数据集时能提供更高的吞吐量。此外，对于具有不同分布的32位键，Onesweep相对于当前的GPU最重大位（MSD）基数排序算法HRS提供了更一致的性能，并且在大多数情况下表现更优。 关键词包括：图形处理器、排序算法、毕业设计、算法。这些关键词强调了Onesweep算法在GPU计算环境中的重要性，以及它对教育和研究领域的潜在贡献。Onesweep的提出，不仅优化了现有的GPU排序技术，还可能启发未来更高效的并行计算解决方案。