c - 在 C 上使用 OpenMP 并行一段时间

Question

我正在尝试在一段时间内进行并行处理，如下所示:

while(!End){
    for(...;...;...) // the parallel for

    ...
    // serial code
}

for 循环是 while 循环的唯一并行部分。如果我这样做，我会有很多开销:

cycles = 0;
while(!End){ // 1k Million iterations aprox
    #pragma omp parallel for
    for(i=0;i<N;i++) // the parallel for with 256 iteration aprox
        if(time[i] == cycles){
           if (wbusy[i]){
               wbusy[i] = 0;
               wfinished[i] = 1;
           }
        }


    // serial code
    ++cycles;    

}

for 循环的每次迭代都是相互独立的。

串行代码和并行代码之间存在依赖关系。

Answer 1

因此，通常不必太担心将并行区域放入循环中，因为现代 openmp 实现在使用线程组等方面非常有效，并且只要循环中有大量工作就可以了。但在这里，外循环计数约为 1e9，内循环计数约为 256 - 并且每次迭代完成的工作很少 - 开销可能与正在完成的工作量相当或更糟，并且性能会受到影响。

所以这之间会有明显的区别:

cycles = 0;
while(!End){ // 1k Million iterations aprox
    #pragma omp parallel for
    for(i=0;i<N;i++) // the parallel for with 256 iteration aprox
        if(time[i] == cycles){
           if (wbusy[i]){
               wbusy[i] = 0;
               wfinished[i] = 1;
           }
        } 

    // serial code
    ++cycles;    
}

还有这个:

cycles = 0;
#pragma omp parallel
while(!End){ // 1k Million iterations aprox
    #pragma omp for
    for(i=0;i<N;i++) // the parallel for with 256 iteration aprox
        if(time[i] == cycles){
           if (wbusy[i]){
               wbusy[i] = 0;
               wfinished[i] = 1;
           }
        } 

    // serial code
    #pragma omp single 
    {
      ++cycles;    
    }
}

但实际上，不幸的是，每次迭代都扫描时间数组，不仅 (a) 速度慢，而且 (b) 工作量不足以让多个核心保持忙碌 - 这是内存密集型的。如果线程数超过几个，即使没有开销，实际上也会比串行线程获得更差的性能，这只是因为内存争用。诚然，您在此处发布的内容只是一个示例，而不是您的真实代码，但为什么不预处理时间数组，以便您可以检查下一个任务何时准备好更新:

#include <stdio.h>
#include <stdlib.h>

struct tasktime_t {
    long int time;
    int task;
};

int stime_compare(const void *a, const void *b) {
    return ((struct tasktime_t *)a)->time - ((struct tasktime_t *)b)->time;
}

int main(int argc, char **argv) {
    const int n=256;
    const long int niters = 100000000l;
    long int time[n];
    int wbusy[n];
    int wfinished[n];

    for (int i=0; i<n; i++) {
        time[i] = rand() % niters;
        wbusy[i] = 1;
        wfinished[i] = 0;
    }

    struct tasktime_t stimes[n];

    for (int i=0; i<n; i++) {
        stimes[i].time = time[i];
        stimes[i].task = i;
    }

    qsort(stimes, n, sizeof(struct tasktime_t), stime_compare);

    long int cycles = 0;
    int next = 0;
    while(cycles < niters){ // 1k Million iterations aprox
        while ( (next < n) && (stimes[next].time == cycles) ) {
           int i = stimes[next].task;
           if (wbusy[i]){
               wbusy[i] = 0;
               wfinished[i] = 1;
           }
           next++;
        }

        ++cycles;
    }

    return 0;
}

这比扫描方法的串行版本快约 5 倍(并且比 OpenMP 版本快得多)。即使您不断更新串行代码中的 time/wbusy/wfinished 数组，您也可以使用 priority queue 跟踪它们的完成时间。每次更新花费 O(ln(N)) 时间，而不是扫描每次迭代花费 O(N) 时间。