Сортировка с использованием OpenMP

[razr_]

Ребят, помогите пожалуйста распараллелить с помощью OpenMP сортировку подсчетом (Counting Sort).

Код последовательной версии:

#include <iostream>
#include <time.h>
 
//------------------------------------------------------------------------------
using namespace std;
 
//------------------------------------------------------------------------------
const int MAX = 30;
 
//------------------------------------------------------------------------------
class cSort
{
public:
    void sort( int* arr, int len )
    {
	int mi, mx, z = 0; findMinMax( arr, len, mi, mx );
	int nlen = ( mx - mi ) + 1; int* temp = new int[nlen];
	memset( temp, 0, nlen * sizeof( int ) );
 
	for( int i = 0; i < len; i++ ) temp[arr[i] - mi]++;
 
	for( int i = mi; i <= mx; i++ )
	{
	    while( temp[i - mi] )
	    {
		arr[z++] = i;
		temp[i - mi]--;
	    }
	}
 
	delete [] temp;
    }
 
private:
    void findMinMax( int* arr, int len, int& mi, int& mx )
    {
	mi = INT_MAX; mx = 0;
	for( int i = 0; i < len; i++ )
	{
	    if( arr[i] > mx ) mx = arr[i];
	    if( arr[i] < mi ) mi = arr[i];
	}
    }
};
//------------------------------------------------------------------------------
int main( int argc, char* argv[] )
{
    srand( time( NULL ) ); int arr[MAX];
    for( int i = 0; i < MAX; i++ )
	arr[i] = rand() % 140 - rand() % 40 + 1;
 
    for( int i = 0; i < MAX; i++ )
	cout << arr[i] << ", ";
    cout << endl << endl;
 
    cSort s; s.sort( arr, MAX );
 
    for( int i = 0; i < MAX; i++ )
	cout << arr[i] << ", ";
    cout << endl << endl;
 
    return system( "pause" );
}
//------------------------------------------------------------------------------

[s-andriano]

Сортировка подсчетом имеет сложность O(N).
При такой сложности основной вклад во время выполнения будет играть доступ к ОП.
Понятно, что у процессора несколько ядер, но память-то одна: раз узкое место именно в ней, то распараллеливание вычисление по нескольким потокам не приведет к росту производительности.
Так зачем тогда затевать всю эту работу?

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

Но, учитывая вышесказанное, думаю, данный алгоритм будет расходовать больше времени, чем исходный.

[razr_]

В том то и проблема, что мне нужно получить хоть небольшой, но выигрыш во времени

[s-andriano]

Сообщение от razr_

...хоть небольшой, но выигрыш во времени

Сочувствую.
Тут, вероятно, нужно оптимизировать работу с памятью, а не надеяться на распараллеливание вычислений процессора.

Вы можете привести конкретные цифры: при каких размерах массивов и диапазоне сортируемых данных какое время какой кусок выполняется?