OpenMP 可能无法直接并行化的代码

Question

OpenMP 可能无法直接并行化的代码

致力于自动并行化器并寻找 OpenMP 可能无法直接并行化的基准(“直接并行化”的意思是:只需指定正确的 OpenMP 指令，即可创建并行可执行文件而不修改代码)。

正题，是否可以使用 OpenMP 并行化以下代码？

1.

double a[ARRAY_DIM], c[ARRAY_DIM];
  .
double ret;
ret = 0.;
for ( i = 0; i < ARRAY_DIM; i++ ) {
  c[i] = exp( ret );
  ret += a[i];
}
return ret;

2.

double a[ARRAY_DIM], c[ARRAY_DIM];
   .
double ret;
ret = 0.;
for ( i = 0; i < ARRAY_DIM; i++ ) {
  if ( a[i] > 0.01 ) {
    ret = c[i];
  }
}
return ret;

Answer 1

代码示例 1 可以使用 prefix sum solution 与 OpenMP 并行化。

对于代码示例 2，我在下面的代码中有两个解决方案，分别称为 foo1 和 foo2。函数 foo1 更容易实现，但如果 a[i] > 0.01 经常为真，则效率可能会低得多。例如，如果它始终为 true，那么它必须在每次迭代中写入 ret 以便杀死并行化。对于函数 foo2 ，它只需按线程顺序写入，而不是每次迭代，并且由于迭代次数远大于线程数，因此效率更高。

#include <omp.h>
#include <stdio.h>
#define ARRAY_DIM 1000
double a[ARRAY_DIM], c[ARRAY_DIM];

double foo1() {
  double ret = 0;
  #pragma omp parallel for ordered schedule(static)
  for (int i = 0; i < ARRAY_DIM; i++) {
    if ( a[i] > 0.01 ) {
      #pragma omp ordered
      ret = c[i];
    }
  }
  return ret;
}

double foo2() {
  int k = -1;
  #pragma omp parallel
  {
    int k2 = -1;
    #pragma omp for schedule(static)
    for (int i = 0; i < ARRAY_DIM; i++) if ( a[i] > 0.01 ) k2 = i;
    #pragma omp for schedule(static) ordered
    for(int i=0; i<omp_get_num_threads(); i++)
      #pragma omp ordered
      if(k2 >= 0) k = k2;
  }
  return c[k];
}

int main(void) {
  for(int i=0; i<ARRAY_DIM; i++) a[i] = 1;
  for(int i=0; i<ARRAY_DIM; i++) c[i] = i;
  printf("%f\n", foo1());
  printf("%f\n", foo2());
}