如何在OpenMP中进行并行化操作

Question

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

我该如何做到平行？

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个像这样的组。

P.S. min和min3是宏。

Answer 1

有一种蛮力的方式来做你想做的事情，但更好的并行化将需要多一点关于你想要什么进出例程的输入。

在循环中的数据依赖关系是这样的，在IJ空间：

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

，其中在点三个值取决于这些点2秒，而那些依赖于那些PT 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数组，还是他们只是中间产品？换句话说，你想要计算什么？