0

我正在实现一个 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 作为输入和 array 作为输出第二次运行它。这使我无法两次将内存复制回数组。实际排序的代码如下所示：

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];

这个链接包含我到目前为止的完整代码。我对快速排序进行了测试，整数和浮点数的运行速度提高了 5 到 10 倍，而 8 字节数据类型的运行速度提高了大约 5 倍。有没有办法改善这一点？

4

1 回答 1

0

我的猜测是在操作期间处理整数的符号是​​不值得的。它使您的代码复杂化并减慢速度。我会先进行第一种排序unsigned，然后再进行第二条路径，该路径只是重新排序两半并反转其中一个底片。

同样从您的代码中，我不知道您如何让不同的进程一起运行。你如何收集父母的直方图？你有一个进程共享变量？无论如何，在这里使用 ptrhead 会更合适。

于 2013-07-14T07:16:57.553 回答