如果我只需要按4个键值排序，那么我可以对排序算法进行哪些优化？

Question

对于更多上下文，我为GPU着色器实现了Bitonic排序网络（并行合并类型）。我正在排序的值的结构如下：32位整数，高16位是0,1,2或3（也就是说，位18到31都是零），低16位是值从0到1023（含）。一切都是从低位开始预先排序的。我的主要目标是根据较高的位对所有内容进行排序（基本上将所有内容放入4个bin中）。第二个目标是按排序顺序排列每个bin中的较低位，但这不是一个重要的优先级。如果这意味着我的排序将更快地完成，我很乐意牺牲低位的排序顺序。

这引出了我的问题;我的bitonic排序网络着色器比我想要的更慢（大约需要半秒钟）。我怀疑这是我为threadgroupshared内存提供的所有内存障碍。有人会对如何针对我的特定情况优化排序算法提出任何建议吗？

我也愿意阅读有关如何有效实现我的主要目标的替代建议（在GPU着色器的上下文中将我感兴趣的所有值放入他们的4个箱中）。

Answer 1

你可以将所有东西分成4个箱子，但是你必须连接箱子。另一种方法是计数/基数排序，在该排序中，您可以对数组进行单次传递，以生成高位值0,1,2的计数（不需要计数为3）。这3个计数将是前3个“箱”的大小。然后将计数求和，如下所示，生成一个数组索引[]，其中包含用于基数排序的4个区间中的每一个的起始索引：

value               starting index
upper bit value 0   0
upper bit value 1   (count of 0's)
upper bit value 2   (count of 0's)+(count of 1's)
upper bit value 3   (count of 0's)+(count of 1's)+(count of 2's)

基数部分内循环将类似于：

output[index[upper bit value of input[i]]] = input[i]
index[upper bit value of input[i]] += 1
i += 1