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函数中任务构造中的数据属性。 变量middle应该是firstprivate而不是shared因为它可能会被执行两个任务的线程所改变。 但是，如果我将代码中显示的变量begin和end设置为shared ，则程序将失败。 我不知道为什么他们（ begin和end ）应该是firstprivate而不是shared 。 在我看来，执行两个任务的线程分别保持变量的begin和end ，它们不会相互影响。 另一方面， ParallelQuickSort函数是递归的，因此在变量begin或end存在竞争（例如，在父函数和子函数中）。 由于变量具有不同的功能（父母和子女功能），我不确定这个嫌疑人。
首先，在一个给定区域内被确定为private变量在显式任务中自动firstprivate被private ，所以你不需要将它们明确地声明为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);
}
}
请注意，尽管此代码可行，但速度比单线程版本要慢：大型Xeon X7350（Tigerton）盒上有2个线程的时间为88.2秒，而单线程时为50.1秒。 原因是创建任务继续执行交换两个数组元素的非常简单的任务。 使用任务的开销是巨大的，你应该把一个合理的上限设置在低于该值的任务禁用状态，假设子阵列的大小达到了1024个元素。 确切数量取决于OpenMP运行时实现，CPU类型和内存速度，所以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秒。
链接地址: http://www.djcxy.com/p/79261.html