关键区域的c开销超过了for循环并行化的速度

Question

我正在尝试在函数中并行化以下串行代码

    float arr[100];
    for ( int i = 0; i < 100; ++i) arr[i]=0;
    int i,j;
    for ( i = 0; i < 100; ++i) {
      float* pi = arr+i;
      int index[10];
      f(i, index); // f fills in the array index
      for (j = 0; j < 10; ++j) {
        float* pj = arr+index[j];
        if (pj > pi){
            float tmp = g(i,j); // some function g
            *pi += tmp;
            *pj += tmp;
        }
      }
    }

在另一个函数中也出现了类似的情况

    float arr[100];
    for ( int i = 0; i < 100; ++i) arr[i]=0;
    int i,j;
    for ( i = 0; i < 100; ++i) {
      float* pi = arr+i;
      int index[10];
      f(i, index); // f fills in the array index
      for (j = 0; j < 10; ++j) {
        float* pj = arr+index[j];
        if (pj > pi){    
            h(pi,i); // function h updates the memory pointed by pi, 
            // by adding to  to *pi something, which only depends on i but not on the values pointed by pi.
            h(pj,j); // 
        }
      }
    }

我的方式是：

    float arr[100];
    for ( int i = 0; i < 100; ++i) arr[i]=0;
    int i,j;
#pragma omp parallel for shared(arr) private(i,j) schedule(auto)
    for ( i = 0; i < 100; ++i) {
      float* pi = arr+i;
      int index[10];
      f(i, index);
      for (j = 0; j < 10; ++j) {
        float* pj = arr+index[j];
        if (pj > pi){
            float tmp = g(i,j);
            *pi += tmp;
            #pragma omp atomic update
            *pj += tmp;
        }
      }
    }

和

    float arr[100];
    for ( int i = 0; i < 100; ++i) arr[i]=0;
    int i,j;
#pragma omp parallel for shared(arr) private(i,j) schedule(auto)
    for ( i = 0; i < 100; ++i) {
      float* pi = arr+i;
      int index[10];
      f(i, index);
      for (j = 0; j < 10; ++j) {
        float* pj = arr+index[j];
        if (pj > pi){
           h(pi,i); 
           #pragma omp critical (pj)
           h(pj,j); // 
        }
      }
    }

我使用原子指令和关键指令，因为多个线程可以同时写入pj指向的内存。（如果我是对的，线程不会同时写入pi指向的内存。）

然而，添加原子指令和关键指令会增加运行时间，使其与串行代码的运行时间大致相同。

所以我想知道我该怎么办？

Answer 1

将此代码并行化的整个想法是有缺陷的。根本没有足够的工作来证明启动和同步线程的开销是合理的。

有了原子更新，同步本身的开销不会太大，但关键部分将破坏所有性能：一次只能有一个线程进入，同步的典型开销时间在微秒量级（取决于等待的实现方式）。这比只用一个核心来做工作要糟糕得多。

如果您完全致力于并行化（我不会在这里使用"优化"一词）调用h()的循环，那么您应该确保h()以线程安全的方式运行（可能使用原子操作），而忘记#pragma omp critical。