CODEWITHSUNDEEP
crecursionopenmp
Dylan
Dylan

Reputation: 107

Parallel recursive algorithm

I am trying to develop some recursive algorithm which I would like to run in parallel using open mp. I need to run the algorithm for multiple input so I want each of the Thread to run 1 input. Each Thread is independent but the results are stored in the same global variable (summing them) as the code shows:

#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]);
    }
}

I have been using critical section to ensure that the variables resultA and resultB are not accessed simultaneously but I am not sure if it is the best for my case. The speed improvement is much less that I would expect. Is there any better approach for a code like this?

Upvotes: 1

Views: 229

Answers (1)

ypnos
ypnos

Reputation: 52367

It sounds like your problem might be better solved with the reduction pattern. But its really hard to tell without more information on what you are actually computing.

See this question on how to do it for two variables and this question for the array case.

Also note that you can always implement your recursion stack yourself and parallelize the individual calls. The obvious benefit is better job balancing between thread if some recursions go much deeper than others.

Upvotes: 1

Related Questions