Я написал код, связанный с быстрой сортировкой с помощью OpenMP, следующим образом:
#include <iostream>
#include <ctime>
#include <algorithm>
#include <functional>
#include <cmath>
using namespace std;
#include <omp.h>
void ParallelQuickSort(int *begin, int *end)
{
if (begin+1 < end)
{
--end;
int *middle = partition(begin, end, bind2nd(less<int>(), *end));
swap(*end, *middle);
#pragma omp task shared(begin) firstprivate(middle)
ParallelQuickSort(begin, middle);
#pragma omp task shared(end) firstprivate(middle)
ParallelQuickSort(++middle, ++end);
}
}
int main()
{
int n = 200000000;
int* a = new int[n];
for (int i=0; i<n; ++i)
{
a[i] = i;
}
random_shuffle(a, a+n);
cout<<"Sorting "<<n<<" integers."<<endl;
double startTime = omp_get_wtime();
#pragma omp parallel
{
#pragma omp single
ParallelQuickSort(a, a+n);
}
cout<<omp_get_wtime() - startTime<<" seconds."<<endl;
for (int i=0; i<n; ++i)
{
if (a[i] != i)
{
cout<<"Sort failed at location i="<<i<<endl;
}
}
delete[] a;
return 0;
}
Проблема, с которой я сталкиваюсь в коде, - это атрибут данных в конструкции задачи внутри функции ParallelQuickSort. Переменная middle должна быть firstprivate вместо shared, так как она может быть изменена потоками, выполняющими две задачи. Однако, если я установлю начало и конец переменной как shared, как показано в коде, программа завершится ошибкой. Интересно, почему они (begin и end) должны быть firstprivate вместо shared. На мой взгляд, поскольку потоки, выполняющие две задачи, сохраняют переменные begin и end соответственно, они не будут влиять друг на друга. С другой стороны, функция ParallelQuickSort является рекурсивной, и поэтому в переменной begin или end (например, в родительской функции и в дочерней) присутствует гонка. Я не уверен в этом подозреваемом, поскольку переменные находятся в разных функциях (родительская и дочерняя функции).
