在 GPU 上使用 C++ AMP 实现并行基数排序
5.00/5 (11投票s)
探讨在 GPU 上实现基数排序的各种方法
引言
排序是一项基本操作，对于许多依赖于它进行数据分区和聚类的 HPC 算法至关重要。基数排序是一种非比较计数排序，其复杂度与待排序元素的数量呈线性关系。这使得它对于需要排序数百万个元素的算法特别有吸引力。今天，我们将深入了解基数排序的细节，并探讨如何使用 C++ AMP 在 GPU 上实现它。C++ AMP 是 Microsoft 提供的一个出色的跨平台 GPU 计算 API。我们还提供了完整的源代码供您学习、修改和改进。假定您了解 C++ AMP/CUDA/任何其他 GPU 计算 API，因为大部分逻辑都以图和伪代码的形式呈现。
基本算法
基数排序的顺序版本实际上是一个非常简单的算法。最好将其表述如下：
for every element in array:
select a digit from most significant to least significant;
sort by the digit;
if digits are equal place elements in the order they appear.
下图说明了这一概念：
该图说明了使用十进制数字进行排序。但是，对于无符号整数，可以使用任何基数的数字来排序元素。使用每个位作为数字（基数）进行排序将需要 32 次连续排序，使用 2 位基数将需要 16 次连续排序，依此类推。此时，我们仍然需要知道如何按选定的数字进行排序。为此，我们应用前缀和（一种累积计数）算法，如下例所示，用于二进制基数。
基于前缀和的排序
前缀和是累积和。前缀和数组的每个元素是其索引小于所考虑索引的所有元素之和。下图应该会使这一点更清楚。
那么这与排序有什么关系呢？其背后的逻辑非常巧妙。当我们使用 1 位基数对数组进行排序时，我们实际上是在将输入位划分为 0 和 1。该分区涉及确定在此位之前遇到的位的累积计数，并将其写入由该计数给出的输出位置。算法如下所示：
步骤 1
将所有等于 0 的数字标记为 1，然后计算标志位的累积和。所有被标记为 1 的位都将写入输出数组，位置由累积和给出。
第二步
将所有等于 1 的数字标记为 1，然后计算标志位的累积和。所有被标记为 1 的位都将写入输出数组，位置由累积和给出。
GPU 实现
到目前为止，我们已经了解到基数排序基本上涉及重复的前缀和以及基于前缀和值的分散写入。该算法大部分时间都花在计算前缀和上。其余的只是内存访问。因此，关键在于找出一种有效的前缀和并行算法。
问题在于前缀和本质上是一个串行操作。每个元素与其所有前驱元素之间都存在数据依赖关系。通过分步进行，每步添加 2 个元素，可以一定程度上缓解这个问题。一如既往，一张图胜过千言万语。
此算法的伪代码如下：
For index in 0 .. log2(N):
For all k in parallel:
If k >= pow2(index)
x[k] = x[k] + x[k – pow2(index)]
内存带宽要求
您可能会注意到，在处理大型数组时，我们朴素的实现可能存在性能问题。该过程的每个步骤都需要访问内存中的整个数组，而缺乏局部性会将最好的缓存逼到极限。此外，大多数 GPU 没有自动内存缓存（一些较新的 NVIDIA GPU 是例外），并且要求您通过 tile 静态（CUDA 中的共享内存）访问手动管理缓存。
让我们改进我们的算法，以便能够高效地处理大型数组。
分而治之以加速前缀和
解决方案是分块处理数组。数组的每个部分将完全驻留在线程块中，并且该部分的累积和将如前所述计算。由于我们将在超快的 tile 静态共享内存中完成所有工作，因此内存访问问题将消失。
一旦计算出部分累积和，就可以使用在先前步骤中计算出的累积和将它们组合起来。该算法归结为：
- 将数组划分为块，计算每个块中元素的总和，并将其存储在中间缓冲区中。这可以使用分块的部分规约来完成，使用众所周知的规约算法。有关详细信息，请参阅代码。
- 计算每个块的部分累积和，并使用上一步计算出的累积和进行组合。
最后
这总结了我们关于基数排序内部工作原理的讨论。您可能还记得，排序可以使用任何基数的数字进行。该代码使用 2 位数字对整数进行排序，对于 32 位整数，总共需要 16 次排序步骤。每个排序步骤都需要处理 4 个值（0、1、2 和 3），需要 4 次前缀和计算。所有 4 个前缀和都在分而治之算法的一个步骤中计算，进一步减少了内存需求。
性能
该代码是在 GTX470 GPU 和 Q6600 CPU 上进行配置的。您可以自行配置进行基准测试，并分享结果。
您会注意到，对于非常少的键（少于约 30,000 个键），CPU 性能更好。但是，对于更多的键（超过约 100 万个键），GPU 的速度大约快 50 倍到 80 倍。此外，GPU 排序所需的时间在高达约一百万个键时变化很小。线性关系仅在此点之后才显现。这是因为需要大量并行工作才能充分利用 GPU，并且在此点之前，工作量的增加对 GPU 性能的影响很小或没有影响。
代码
您可以通过本文顶部的链接浏览本文以及代码，也可以在 GitHub 上查看。