c++ - 如何正确使用 openMP

Question

我正在尝试通过使用 openMP 来加速我的 MPI 项目。我有一个包含 1000 个 2d 点的数据集，我正在使用强力算法来查找 2d 图中的最小距离。但是，当我尝试拆分执行线程时，它会极大地损害性能。如何正确使用 openMP？

这是我的尝试:

double calcDistance(double input[][2], int start, int stop){

    double temp;
    //declare and initialize minimum
    double minimum =  pow (((input[start+1][0]) - (input[start][0])),2) + pow(((input[start+1][1]) - (input[start][1])),2);
    minimum = sqrt(minimum);

    closestIndex1 = start;
    closestIndex2 = start+1;
    //Brute Force Algorithm to find minimum distance in dataset.

        #pragma omp parallel for
        for(int i=start; i<stop;i++){
            for(int j=start; j<stop;j++){

                    temp = pow(((input[j][0]) - (input[i][0])),2) + pow(((input[j][1]) - (input[i][1])),2);
                    temp = sqrt(temp);
                    if(temp < minimum && i < j){
                            minimum = temp; 
                            closestIndex1 = i;
                            closestIndex2 = j;
                    }//endif
            }//end j
          }//end i
return minimum;
}

我不得不说哇。谢谢，这非常有帮助，确实解决了我的一大堆问题。再次感谢你，gha.st。

Answer 1

分析

首先，纯属运气您的程序看起来像这样工作。您确实存在数据竞争，这会导致我的机器上出现无效结果。考虑本文的以下测试工具:

::std::cout << ::xtd::target_info() << "\n\n"; // [target os] [target architecture] with [compiler]

static const int count = 30000;
auto gen = ::std::bind(::std::normal_distribution<double>(0, 1000), ::std::mt19937_64(42));
std::unique_ptr<double[][2]> input(new double[count][2]);
for(size_t i = 0; i < count; ++i)
{
    input[i][0] = gen();
    input[i][1] = gen();
}

::xtd::stopwatch sw; // does what its name suggests
sw.start();
double minimum = calcDistance(input.get(), 0, count);
sw.stop();
::std::cout << minimum << "\n";
::std::cout << sw << "\n";

在删除 omp pragma 的情况下执行函数时，其输出为:

Windows x64 with icc 14.0

0.0559233
7045 ms

或

Windows x64 with msvc VS 2013 (18.00.21005)

0.0559233
7272 ms

当完整地执行 omp pragma 时，它的输出是:

Windows x64 with icc 14.0

0.324085
675.9 ms

或

Windows x64 with msvc VS 2013 (18.00.21005)

0.0559233
4338 ms

由于机器使用 24 个线程(在启用 HT 的 12 个内核上)，加速是显而易见的，但可能会更好，至少对于 msvc 而言。生成更快程序的编译器 (icc) 也通过给出每次运行都不同的错误结果来显示数据竞争。

注意:在为具有 10k 迭代的 x86 编译调试版本时，我还能够看到 msvc 的错误结果。

迭代局部变量的正确使用

temp代码中的变量的生命周期为最内层循环的一次迭代。通过移动其范围以匹配其生命周期，我们可以消除数据竞争的一个来源。我还冒昧地删除了两个未使用的变量并更改了 minimum 的初始化为常数:

double calcDistance(double input[][2], int start, int stop){
    double minimum = ::std::numeric_limits<double>::infinity();
    //#pragma omp parallel for // still broken
    for(int i = start; i < stop; i++){
        for(int j = start; j < stop; j++) {
            double temp = pow(((input[j][0]) - (input[i][0])), 2) + pow(((input[j][2]) - (input[i][3])), 2);
            temp = sqrt(temp);
            if(temp < minimum && i < j) minimum = temp;
        }
    }
    return minimum;
}

适当的 OMP 最小计算

OMP 支持 reductions ，这很可能会表现得相当好。为了尝试它，我们将使用以下 pragma，它确保每个线程独立工作 minimum使用最小运算符组合的变量:

#pragma omp parallel for reduction(min: minimum)

结果验证了 ICC 的方法:

Windows x64 with icc 14.0

0.0559233
622.1 ms

但是 MSVC 咆哮 error C3036: 'min' : invalid operator token in OpenMP 'reduction' clause ，因为它不支持最小缩减。为了定义我们自己的缩减，我们将使用一种称为 double-checked locking 的技术。 :

double calcDistance(double input[][2], int start, int stop){
    double minimum = ::std::numeric_limits<double>::infinity();
    #pragma omp parallel for
    for(int i = start; i < stop; i++){
        for(int j = start; j < stop; j++) {
            double temp = pow(((input[j][0]) - (input[i][0])), 2) + pow(((input[j][1]) - (input[i][1])), 2);
            temp = sqrt(temp);
            if(temp < minimum && i < j)
            {
                #pragma omp critical
                if(temp < minimum && i < j) minimum = temp;
            }
        }
    }
    return minimum;
}

这不仅是正确的，而且与 MSVC 的性能相当(请注意，这比不正确的版本快得多!):

Windows x64 with msvc VS 2013 (18.00.21005)

0.0559233
653.1 ms

ICC 的性能没有明显下降:

Windows x64 with icc 14.0

0.0559233
636.8 ms

序列优化

虽然上面是串行代码的适当并行化，但考虑到您正在计算一大堆 temp，它可以得到显着优化。由于您的 i < j，您永远不会使用的结果条件。

通过简单地改变内循环的起点，不仅可以完全避免这种计算，还可以简化循环条件。

我们使用的另一个技巧是延迟 sqrt计算到最后可能的一秒，因为它是一个同态变换，我们可以只对距离的平方进行排序。

最后，调用pow因为正方形的效率相当低，因为它会产生大量我们不需要的开销。

这导致了最终的代码

double calcDistance(double input[][2], int start, int stop){
    double minimum = ::std::numeric_limits<double>::infinity();
    #pragma omp parallel for
    for(int i = start; i < stop; i++) {
        for(int j = i + 1; j < stop; j++) {
            double dx = input[j][0] - input[i][0];
            dx *= dx;
            double dy = input[j][1] - input[i][1];
            dy *= dy;
            double temp = dx + dy;
            if(temp < minimum)
            {
                #pragma omp critical
                if(temp < minimum) minimum = temp;
            }
        }
    }
    return sqrt(minimum);
}

导致最终表现:

Windows x64 with icc 14.0

0.0559233
132.7 ms

或

Windows x64 with msvc VS 2013 (18.00.21005)

0.0559233
120.1 ms