3

我用 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，程序将失败。我想知道为什么他们 ( beginand end) 应该firstprivate代替shared. 在我看来，由于执行这两个任务的线程分别保持变量begin和end，它们不会相互影响。另一方面，ParallelQuickSort函数是递归的，因此变量begin或end（例如，在父函数和子函数中）。我不确定这个嫌疑人，因为变量在不同的函数（父函数和子函数）中。

4

1 回答 1

2

首先，确定private在给定区域中的变量会自动firstprivate在显式任务中，因此您无需将它们显式声明为firstprivate. 其次，您的代码包含++end;并--end;修改 的值，如果是end，则会影响其他任务。在这里是正确的数据共享类 - 每个任务只保留 的值，以及它们在创建任务时曾经拥有的值。endsharedfirstprivatebeginendmiddle

你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 秒，两个线程。

于 2012-11-19T08:44:51.130 回答