使用OpenMP在C中并行化基数排序-Java 学习之路

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

我的程序是对典型基数排序的修改：它根据数字的二进制表示对整数数组进行排序，在这里你可以改变应该被解释为一位数的位数（基本上是用于根据整数的大小来获得不同的运行时间 .

我有一个基数函数，它有三个参数：

// 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 增量遍历所有位（int：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] }

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
    }

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

回复于 2024-04-27T13:45:47+08:00

使用OpenMP在C中并行化基数排序

1 回答

相关问题