Параллелизация сортировки radix в C с помощью OpenMP

Question

Как вы планируете распараллеливать алгоритм сортировки оснований в C с помощью OpenMP?

Моя программа представляет собой модификацию вашей типичной сортировки radix: она сортирует массив целых чисел на основе двоичного представления цифры, где вы можете изменять количество бит, которое должно интерпретироваться как одна цифра (который по существу будет использоваться для получения различного времени работы на основе того, насколько велики ваши целые числа).

У меня есть базисная-функция, которая принимает три аргумента:

// 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); 

Далее, мои радиксы-функция перебирает через все биты (INT: 32 бита) с b шагом:

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

Состоит из трех частей:

• Подсчет числа определенных разрядов (фактически бит), чтобы определить h Большое количество хранения требует ведро. 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, б), создать битовую маску и сдвиг вправо рассчитывать на основе Ъ:

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 
    } 

Если сортировка знаковых целых чисел, вам необходимо настроить для наиболее значимое поле (также арифметический сдвиг вправо для целых чисел со знаком является зависимым от компилятора/платформы). Одним из решений (для целых чисел, дополняемых двумя символами) является преобразование в целое число без знака и дополнение знакового бита для генерации индекса ведра.