使用 openmp 并行化

Question

我有这个函数，我想使用 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;
}

我尝试使用 #pragma omp parallel for 但它不起作用。我也尝试过使用归约函数，但得到了错误的答案。
我认为原因是因为 s 的值取决于 x （这取决于每个步骤的值）。

Answer 1

您是正确的，对 x 的依赖会导致问题。这种依赖性存在于迭代之间。每次迭代都需要上一次迭代的x。因此它使得整个循环不可并行化。

看起来这个循环正在使用重复平方计算幂模数。

简而言之：不，你将无法并行化它。这种依赖性是您所使用的算法所固有的。