Radix排序是一种非比较型计数排序算法，它以线性时间复杂度对数据进行排序，特别适用于需要排序数百万元素的场景。本文将深入探讨Radix排序的工作原理，并分析如何利用C++ AMP在GPU上实现这一算法。C++ AMP是微软推出的一款优秀的跨平台GPU计算API。文章末尾提供了完整的源代码，供读者学习、修改和优化。
Radix排序的顺序版本算法非常简单。其基本逻辑可以表达为：对于数组中的每个元素，从最高位到最低位选择一个数字，然后根据这个数字进行排序；如果数字相等，则按照它们出现的顺序排列。以下图表展示了这一概念：
图表展示了使用十进制数字进行排序。然而，对于无符号整数，可以使用任何基数的数字进行排序。如果使用每个位作为数字（基数），则需要32次连续排序，2位基数则需要16次连续排序，依此类推。在这一点上，仍然需要知道如何根据选定的数字进行排序。为此，应用前缀和（一种累积计数）算法，如下所示，用于二进制基数：
前缀和是一种累积和。数组的前缀和的每个元素是其索引小于当前考虑索引的所有元素的和。以下图表希望使这一点变得清晰：
前缀和与排序的关系非常优雅。当使用1位基数对数组进行排序时，实际上是将输入位划分为0和1。划分涉及确定在遇到当前位之前遇到的位的累积计数，并将该计数写入由该计数给出的输出位置。算法详细如下：
步骤1：将所有等于0的数字标记为1，然后取标记位的前缀和。所有标记为1的位都写入输出数组，位置由前缀和给出。
步骤2：将所有等于1的数字标记为1，然后取标记位的前缀和。所有标记为1的位都写入输出数组，位置由前缀和给出。
到目前为止，已经理解了Radix排序基本上涉及重复的前缀和和基于前缀和值的分散写入。算法的大部分时间都花在计算前缀和上。其余的只是内存访问。关键是要找出一种高效的并行算法来计算前缀和。
问题是，前缀和是一种固有的串行操作。每个元素和它前面的所有元素之间都有数据依赖。这个问题可以通过逐步进行，每一步增加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 static（CUDA中的共享内存）访问手动管理缓存。
让改进算法，以便能够高效地处理大型数组。
解决方案是将数组分成部分。数组的每个部分将完全位于一个线程瓦片内，这个部分的前缀和将按照前面讨论的方式计算。内存访问问题将消失，因为将在超快的tile static共享内存中完成所有工作。
一旦计算出部分前缀和，就可以使用前一步计算的和将它们组合在一起。算法归结为：
将数组划分为瓦片，找到每个瓦片元素的和并存储在中间缓冲区中。这可以使用瓦片部分归约来完成，使用众所周知的归约算法。有关详细信息，请参考代码。
找到每个瓦片的部分前缀和，并使用前一步计算的和进行组合。
这就是对Radix排序内部工作原理的讨论。正如可能记得的，排序可以使用任何基数的数字进行。代码使用2位数字对整数进行排序，对于32位整数需要16次总排序步骤。每个排序步骤必须处理4个值（0、1、2和3），需要4个前缀和。所有4个前缀和都在分而治之算法的一步中计算，进一步减少了内存需求。