2

我知道 OpenMP 的基础知识，并且我知道为了并行化 a 的迭代不能依赖于以前的迭代。也可以使用归约，但它们仅支持基本运算符，例如 +、-、/、*、&&、||。

我怎样才能使这个并行？

for (i = 1; i < n; ++i) {
    for (j = 1; j < n; ++j) {
        // stanga
        if (res[i][j - 1] != res[i][j]) {
            cmin2[i][j][0] = min(cmin2_res[i][j - 1][0] + 1, cmin[i][j][0]);
            cmin2_res[i][j][0] = min(cmin2[i][j - 1][0] + 1, cmin_res[i][j][0]);
         } else {
            cmin2[i][j][0] = min(cmin2[i][j - 1][0] + 1, cmin[i][j][0]);
            cmin2_res[i][j][0] = min(cmin2_res[i][j - 1][0] + 1, cmin_res[i][j][0]);
         }
         // sus
         if (res[i - 1][j] != res[i][j]) {
             cmin2[i][j][0] = min3(cmin2[i][j][0], cmin2_res[i - 1][j][0] + 1, cmin[i][j][1]);
             cmin2_res[i][j][0] = min3(cmin2_res[i][j][0], cmin2[i - 1][j][0] + 1, cmin_res[i][j][1]);
         } else {
             cmin2[i][j][0] = min3(cmin2[i][j][0], cmin2[i - 1][j][0] + 1, cmin[i][j][1]);
             cmin2_res[i][j][0] = min3(cmin2_res[i][j][0], cmin2_res[i - 1][j][0] + 1, cmin_res[i][j][1]);
         }
     }
 }

我的问题是我如何分解它以便能够并行运行它（如果可能的话，也许使用减少）。

问题是，在每次迭代中，操作都必须按此顺序完成，因为我还有 3 组这样的 for。

PS min 和 min3 是宏。

4

1 回答 1

3

有一种蛮力的方法可以做你想做的事，但更好的并行化需要更多关于你想要进出例程的输入。

在 ij 空间中，循环中的数据依赖项如下所示：

     i →
  ..........
j .....1....
↓ ....12....
  ...123....

其中第三点的值取决于那些点 2，而那些取决于点 1 处的值，等等。由于这种对角结构，您可以重新排序循环以对角线遍历网格，例如第一次迭代结束 (0 ,1), (1,0) 然后是 (0,2),(1,1),(2,0) 等等。您的问题的简化版本如下所示：

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <sys/time.h>

int **int2darray(int n, int m);
void free2darray(int **array);
void init2darray(int **array, int n, int m);
void tick(struct timeval *timer);
double tock(struct timeval *timer);

int main(int argc, char **argv) {

    const int N=10000;
    int **serialarr, **omparr;

    struct timeval serialtimer, omptimer;
    double serialtime, omptime;

    serialarr = int2darray(N,N);
    omparr    = int2darray(N,N);

    init2darray(serialarr, N, N);
    init2darray(omparr,    N, N);

    /* serial calculation */
    tick(&serialtimer);
    for (int i=1; i<N; i++)
        for (int j=1; j<N; j++)
            serialarr[i][j] = serialarr[i-1][j] + serialarr[i][j-1];
    serialtime = tock(&serialtimer);

    /* omp */
    tick(&omptimer);
    #pragma omp parallel shared(omparr) default(none)
    {
        for (int ipj=1; ipj<=N; ipj++) {
            #pragma omp for
            for (int j=1; j<ipj; j++) {
                int i = ipj - j;
                omparr[i][j] = omparr[i-1][j] + omparr[i][j-1];
            }
        }
        for (int ipj=N+1; ipj<2*N-1; ipj++) {
            #pragma omp for
            for (int j=ipj-N+1; j<N; j++) {
                int i = ipj - j;
                omparr[i][j] = omparr[i-1][j] + omparr[i][j-1];
            }
        }
    }
    omptime = tock(&omptimer);

    /* compare results */
    int abserr = 0;
    for (int i=0; i<N; i++)
        for (int j=0; j<N; j++)
            abserr += abs(omparr[i][j] - serialarr[i][j]);

    printf("Difference between serial and OMP array: %d\n", abserr);
    printf("Serial time = %lf\n", serialtime);
    printf("OMP time    = %lf\n", omptime);

    free2darray(omparr);
    free2darray(serialarr);
    return 0;
}


int **int2darray(int n, int m) {
    int *data = malloc(n*m*sizeof(int));
    int **array = malloc(n*sizeof(int*));
    for (int i=0; i<n; i++)
        array[i] = &(data[i*m]);

    return array;
}

void free2darray(int **array) {
    free(array[0]);
    free(array);
}

void init2darray(int **array, int n, int m) {
    for (int i=0; i<n; i++)
        for (int j=0; j<m; j++)
            array[i][j] = i*m+j;
}

void tick(struct timeval *timer) {
    gettimeofday(timer, NULL);
}

double tock(struct timeval *timer) {
    struct timeval now;
    gettimeofday(&now, NULL);
    return (now.tv_usec-timer->tv_usec)/1.0e6 + (now.tv_sec - timer->tv_sec);
}

运行给出：

$ gcc -fopenmp -Wall -O2 loops.c -o loops -std=c99 
$ export OMP_NUM_THREADS=8
$ ./loops
Difference between serial and OMP array: 0
Serial time = 0.246649
OMP time    = 0.174936

你会注意到加速很差，即使 N 很大，因为每次迭代的计算量很小，它是并行化的内部循环，我们正在以一种奇怪的、缓存不友好的顺序遍历内存。

上面的一些可能会被修复，但它会帮助更多地了解你正在尝试做的事情；例如，您关心 cmin2_res 数组，还是它们只是中间产品？换句话说，你想计算什么？

于 2012-11-04T18:04:39.330 回答