如何改进这个基数的实现
我正在实现一个2字节的基数排序。 其概念是使用计数排序来排序整数的低16位，然后排序高16位。 这使我可以在2次迭代中运行排序。 我有的第一个想法是试图找出如何处理负面情况。 由于符号位将被翻转为负数，然后以十六进制形式使负数大于正数。 为了解决这个问题，我在符号位正向时翻转了符号位，以使[0，2 bil] = [128 000 000 000，255 255 ...）。 当它是负数时，我翻转所有的位，使其范围从（000 000 ..，127 255 ..）。 这个网站帮助我了解了这些信息。 为了完成它，我会根据pass将整数分成顶部或底部的16位。 以下是允许我这样做的代码。
static uint32_t position(int number, int pass) {
int mask;
if (number <= 0) mask = 0x80000000;
else mask = (number >> 31) | 0x80000000;
uint32_t out = number ^ mask;
return pass == 0 ? out & 0xffff : (out >> 16) & 0xffff;
}
要开始实际的基数排序，我需要形成一个尺寸为65536个元素的直方图。 我碰到的问题是输入元素的数量非常大。 创建直方图需要一段时间，所以我使用进程和共享内存并行地实现了它。 我将数组分成大小为8的子区域。然后通过65536 * 8的共享内存数组，我让每个进程创建自己的直方图。 之后，我将它们汇总在一起形成一个直方图。 以下是该代码：
for (i=0;i<8;i++) {
pid_t pid = fork();
if (pid < 0) _exit(0);
if (pid == 0) {
const int start = (i * size) >> 3;
const int stop = i == 7 ? size : ((i + 1) * size) >> 3;
const int curr = i << 16;
for (j=start;j<stop;++j)
hist[curr + position(array[j], pass)]++;
_exit(0);
}
}
for (i=0;i<8;i++) wait(NULL);
for (i=1;i<8;i++) {
const int pos = i << 16;
for (j=0;j<65536;j++)
hist[j] += hist[pos + j];
}
接下来的部分是我花了大部分时间分析缓存如何影响前缀和的性能。 使用8位和11位的基数排序，所有的直方图都可以放入L1缓存中。 有了16位，它只能适用于L2缓存。 最后，16位直方图的和最快，因为我只需要运行2次迭代就可以了。 根据CUDA网站的建议，我也同时运行前缀总和。 在2.5亿个元素中，这个运行速度比16位整数慢大约1.5秒。 所以我的前缀总和看起来像这样：
for (i=1;i<65536;i++)
hist[i] += hist[i-1];
剩下的唯一办法是向后遍历数组，并将所有元素放入临时数组中的相应位置。 因为我只需要经过两次，而不是从temp复制到数组，然后再次运行代码。 我首先使用数组作为输入运行排序，并将temp作为输出。 然后第二次使用temp作为输入和数组作为输出运行它。 这使我无论从两次mem复制回数组。 代码看起来像这样的实际排序：
histogram(array, size, 0, hist);
for (i=size-1;i>=0;i--)
temp[--hist[position(array[i], 0)]] = array[i];
memset(hist, 0, arrSize);
histogram(temp, size, 1, hist);
for (i=size-1;i>=0;i--)
array[--hist[position(temp[i], 1)]] = temp[i];
这个链接包含我迄今为止的完整代码。 我对quicksort进行了测试，整数和浮点运算速度提高了5到10倍，使用8字节的数据类型提高了约5倍。 有没有办法改进这个？
我的猜测是，在手术过程中处理整数的符号是不值得的。 它可以完成并减慢你的代码。 我会首先进行unsigned排序，然后做第二条路径，重新排序这两个部分并将其中一个底部排序。
同样从你的代码我不知道你有不同的过程一起运作。 你如何在家长收集直方图？ 你有一个进程共享变量？ 无论如何，在这里使用ptrhead会更合适。
链接地址: http://www.djcxy.com/p/70791.html