c - C 语言基数排序与 OpenMP 的并行化

Question

您将如何使用 OpenMP 并行化 C 语言的基数排序算法？

我的程序是对典型基数排序的修改:它根据数字的二进制表示形式对整数数组进行排序，您可以在其中改变应解释为一位数字的位数(其中本质上将用于根据整数的大小获得不同的运行时间)。

我有一个带有三个参数的基函数:

// n is the number of elements in data
// b is number of bits that should be interpreted as one digit
void radix(int* data, int n, int b);

此外，我的基函数使用 b 迭代所有位(整数:32 位)。增量:

for(bit = 0; bit < 32; bit += b) { ... }

其中包含三个部分:

• 计算某个数字(实际上是位)的出现次数，以确定存储桶需要多少存储空间。 bucket[(data[i] >> bit) & (int)(pow(2,b)-1)]++

• 将值放入临时数组(存储桶)中。

  bitval = (data[i] >> bit) & (int)(pow(2,b)-1)

  temp_data[bucket[bitval]++] = data[i]

• 将值从临时存储桶复制到 *data给函数的指针。

  for(i = 0; i < n; i++) { data[i] = temp_data[i] }

Answer 1

并行化将成为一个问题，因为限制因素将是内存带宽(CPU 开销非常小，并且只有一个内存总线)。

另外，不要使用浮点函数 pow(2,b)，而是基于 b 创建位掩码和右移计数:

    numberOfBits = b;
    shiftCount = 0;
    while(1){  // main loop
        // set numberOfBuckets
        numberOfBuckets = 1 << numberOfBits;
        bitMask = numberOfBuckets - 1;
        // code to generate histogram for this field goes here
        // ...
        shiftCount += numberOfBits;
        // check for partial bit field
        if((shiftCount + numberOfBits) > (8*sizeof(unsigned int))){
            numberOfBits = (8*sizeof(unsigned int)) - shiftCount;
            shiftCount = (8*sizeof(unsigned int)) - numberOfBits;
            continue; // do partial bit field
        }
        // check for done
        if(shiftCount == (8*sizeof(unsigned int)))
            break; // done
    }

如果对有符号整数进行排序，您需要调整最重要的字段(有符号整数的算术右移也取决于编译器/平台)。一种解决方案(对于二进制补码有符号整数)是转换为无符号整数并对符号位求补以生成存储桶索引。