parallelizing using openmp

Question

I have this function which I would like to parallelize using openmp:

for(i=len-1;i>=0;i--){
  if(bin[i]==49) // bin is a binary number & is
                 // stored in a string. 49 is ascii value of 1
  {
     s=(s*x)%n;    
  }
  x=(x*x)%n;
}

I tried using #pragma omp parallel for but it dint work. I tried with the reduction function too and yet I got wrong answers.
I think the reason is because value of s depends on x (which is dependent on each steps value).

Mysticial · Accepted Answer · 2011-11-05 07:58:43Z

2

You are correct that the dependency on x causes problems. This dependency is between iterations. Each iteration requires the x from the previous iteration. So it renders the entire loop not parallelizable.

It looks like this loop is computing a power-modulus using repeated squaring.

So in short: No you won't be able to parallelize it. The dependency is inherent in the algorithm that you're using.

answered Nov 5, 2011 at 7:58

Mysticial

473k46 gold badges343 silver badges337 bronze badges

Sign up to request clarification or add additional context in comments.

6 Comments

user1019083 Over a year ago

So is there any other way to implement this to make it extremely fast? I am trying to implement RSA algorithm for large numbers. But for say for a 50 digit prime number it takes about 1 hour to decrypt. This function is taking too much time.

Mysticial Over a year ago

Since you can't parallelize here, you'll need to do it at a higher level. If you have multiple of these powermods to do (and they are independent), you can do those in parallel. Though I'm not too familiar with the RSA algorithm so I don't know how much parallelism there is at higher levels.

user1019083 Over a year ago

Ok i will check into that. Thank you so much. What about this loop? Is it possible to parallelize? for(i=0,k=0;i<n;i++,k++) { c=msg(a[i]); b[k++]=msg(c); } There is no dependency, so it should be possible to work out

Mysticial Over a year ago

As long as msg() is re-entrant, then yes, it's parallelizable. (also, make sure that a and b don't overlap)

Mysticial Over a year ago

Actually, no reduction is needed. So just use #pragma omp parallel for. Reductions are only needed when the result of the iterations will "reduce" to a variable. (such as summing up all the elements) But in your example, you aren't doing that. You're writing into different elements of array b. So there is no reduction.

|

Collectives™ on Stack Overflow

parallelizing using openmp

1 Answer 1

6 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

6 Comments

Your Answer

Sign up or log in

Post as a guest

Related