c - 并行递归算法

Question

我正在尝试开发一些我想使用 open mp 并行运行的递归算法。我需要为多个输入运行算法，所以我希望每个线程运行 1 个输入。每个线程都是独立的，但结果存储在同一个全局变量中(对它们求和)，如代码所示:

#include <stdio.h>
#include <omp>

double * resultA;
double * resultB;

void recursiveAlgorithm(double a)
{
    double b = someFunction(a);
    uint c = anotherFunction(a);

    if (b < 0)
    {
         #pragma omp critical
         {
              resultA[c] = resultA[c] + b;
         }
         return;
    }
    if (b > 100)
    {
         #pragma omp critical
         { 
              resultB[c] = resultB[c] + b;     
         } 
         return;
    } 
    recursiveAlgorithm(b);
}


int main( int argc, const char* argv[] )
{
    double input[5] = {0, 1, 2, 3, 4};

    resultA = malloc(1000*1000*3, sizeof(double));
    resultB = malloc(1000*1000*3, sizeof(double));

    #pragma omp parallel for
    for (uint i; i < 5; i++){
         recursiveAlgorithm(input[i]);
    }
}

我一直在使用临界区来确保不会同时访问变量 resultA 和 resultB，但我不确定它是否最适合我的情况。速度提升远低于我的预期。对于这样的代码，有没有更好的方法？

Answer 1

听起来您的问题可能可以通过归约模式得到更好的解决。但是，如果没有关于您实际计算的内容的更多信息，就很难判断。

参见 this question关于如何为两个变量和this question做这件事对于阵列情况。

另请注意，您始终可以自己实现递归堆栈并并行化各个调用。如果某些递归比其他递归深入得多，那么明显的好处是可以更好地平衡线程之间的工作。