如何在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數組，還是他們只是中間產品？換句話說，你想要計算什麼？