Атрибут данных в задаче OpenMP
Я написал код, связанный с быстрой сортировкой с 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 функция. Переменная середина должна быть firstprivate вместо shared как это может быть изменено потоками, выполняющими две задачи. Однако, если я установлю переменную begin и end как shared как показано в коде, программа потерпит неудачу. Интересно почему они (begin а также end) должно быть firstprivate вместо shared, На мой взгляд, поскольку потоки, выполняющие две задачи, сохраняют переменную begin а также end соответственно они не будут влиять друг на друга. С другой стороны, ParallelQuickSort функция рекурсивна, и поэтому в переменной есть раса begin или же end (например, в родительской функции и в дочерней функции). Я не уверен в этом подозреваемом, так как переменные находятся в разных функциях (функция parent и child).
Решение
Во-первых, переменные, которые определены как private в данном регионе автоматически firstprivate в явных задачах, поэтому вам не нужно объявлять их явно как firstprivate, Во-вторых, ваш код содержит ++end; а также --end; которые изменяют значение end, влияя на другие задачи, если end является shared, firstprivate правильный класс обмена данными здесь — каждая задача просто сохраняет значения begin, end а также middle что они имели в то время, когда задача была создана.
Ваш ParallelQuickSort должно быть так просто, как это:
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
ParallelQuickSort(begin, middle);
#pragma omp task
ParallelQuickSort(++middle, ++end);
}
}
Обратите внимание, что хотя этот код работает, он намного медленнее однопоточной версии: 88,2 секунды с двумя потоками на большом блоке Xeon X7350 (Tigerton) по сравнению с 50,1 секундами с одним потоком. Причина заключается в том, что создание задач продолжается до очень простой задачи замены двух элементов массива. Затраты на использование задач огромны, и вы должны установить разумный верхний порог, ниже которого задачи следует отключить, например, когда размер подмассива достигнет 1024 элементов. Точное число зависит от реализации OpenMP во время выполнения, типа вашего процессора и скорости памяти, поэтому значение 1024 выбирается более или менее случайным образом. Тем не менее, оптимальное значение не должно создавать две задачи, которые обрабатывают элементы, которые попадают в одну и ту же строку кэша, поэтому число элементов должно быть кратным 16 (64 байта на строку кэша / 4 байта на целое число):
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 if((end - begin) > 1024)
ParallelQuickSort(begin, middle);
#pragma omp task if((end - begin) > 1024)
ParallelQuickSort(++middle, ++end);
}
}
С этой модификацией код выполняется в течение 34,2 секунды с двумя потоками в одном окне.
Другие решения
Других решений пока нет …
detector