并行递归算法

Question

我试图开发一些递归算法，我想使用开放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。

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