CODEWITHSUNDEEP
cparallel-processingopenmppragma
AbdelKh
AbdelKh

Reputation: 542

OpenMP | Parallelizing a loop with dependent iterations

I am trying to parallelize an encoding function, I tried adding a simple pragma around the for but the result was wrong. I figured that iterations are dependent (by code variable) and therefore they can not be directly parallelized.

int encodePrimeFactorization(int number){
    int code = 0;
    for (int i=PF_NUMBER-1; i>=0 ; i--){
      code = code * 2;
      int f = prime_factors[i];
      if (number % f == 0){
        code = code + 1;
      }
    }
    return code;
}

Is there a way to make code variable independent for each iteration?

Upvotes: 2

Views: 882

Answers (1)

Zulan
Zulan

Reputation: 22670

Yes. At least for me, it's easier to think about that if you look at the algorithm this way:

int code = 0;
for (int i=PF_NUMBER-1; i>=0 ; i--) {
  code = code << 1;
  int f = prime_factors[i];
  if (number % f == 0){
    // The last bit of code is never set here,
    // because it has been just shifted to the left
    code = code | 1;
  }
}

Now you can shift the set-bit already while setting:

int code = 0;
for (int i=PF_NUMBER-1; i>=0 ; i--) {
  int f = prime_factors[i];
  if (number % f == 0){
    code = code | (1 << i);
  }
}

Now it becomes a trivial reduction. Now you can shift the set-bit already while setting:

int code = 0;
#pragma omp parallel for reduction(|,code)
for (int i=PF_NUMBER-1; i>=0 ; i--) {
  int f = prime_factors[i];
  if (number % f == 0){
    code |= (1 << i);
  }
}

That said, you will not get any performance gain. This works only up to 31 bits, which is far too little work to benefit from parallelization overhead. If this is a hot part in your code, you have to find something around it to apply the parallelization.

Upvotes: 2

Related Questions