外部並行循環中的內部順序循環 - OMP

Question

我必須並行化OMP中的第一個for循環，但在其內部有一個for循環，由於數據依賴性而不能並行化。我在外面嘗試了並行，但指針有問題。

問題的最小例如：

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

int main() 
{ 

int N = 5; 
int size = 6; 
int n, j, i; 

double t[] = {1,2,3,4,5,6}; 


double z, h2M, R2M, dz; 
int *dynamic_d; 
int *dynamic_A; 
int *dynamic_B; 
int *output; 

dynamic_d = (int *) calloc (N+1, sizeof(int)); 

for(i = 0; i < N+1; i++){ 
    *(dynamic_d + i) = i; 
} 

dynamic_A = (int*) calloc (N+2, sizeof(int)); 
dynamic_B = (int*) calloc (N+2, sizeof(int)); 
output = (int*) calloc (size, sizeof(int)); 


for (j = 0; j < size; j++) { 
    z = t[j] + 1; 
    *dynamic_A = 0; 
    *dynamic_B = 1;     

    *(dynamic_A + 1) = *dynamic_d; 
    *(dynamic_B + 1) = 1; 

    for (n = 2; n <= N+1; n++) { 
      dz = *(dynamic_d + n-1)*z; 
      *(dynamic_A + n) = *(dynamic_A + n-1) + dz + (*(dynamic_A + n-2)); 
      *(dynamic_B + n) = *(dynamic_B + n-1) + dz + (*(dynamic_B + n-2)); 
    } 

    h2M = z + *(dynamic_d + N-1) - *(dynamic_d + N); 
    R2M = -h2M + z + *(dynamic_d + N); 

    *(dynamic_A + N+1) = *(dynamic_A + N) + R2M + *(dynamic_A + N-1); 
    *(dynamic_B + N+1) = *(dynamic_B + N) + R2M + *(dynamic_B + N-1); 

    *(output + j) = t[j] + *(dynamic_A + N+1) + *(dynamic_B + N+1); 
} 

printf("\n\noutput:\n"); 
for (j = 0; j < size; j++){ 
    printf("| %d ", output[j]); 
} 
printf("\n"); 

return 0; 
} 

Answer 1

唯一數據依賴性是對兩個陣列dynamic_A和dynamic_B因爲它們是被寫入並且在循環讀出的唯一的一個。 dynamic_d只讀，output只寫入（所以沒有問題）。

但是，如果你仔細觀察的dynamic_A和dynamic_B依賴你可以看到，他們不是循環進行，因爲在迭代計算j的dynamic_A[i]任何值僅是迭代內使用。整個數組將在最外層循環的下一次迭代中被覆蓋。

您需要重寫代碼，以便每個線程都有自己的專用副本dynamic_A和dynamic_B。例如：

#pragma omp parallel private(dynamic_A, dynamic_B, z, h2M, R2M) 
{ 
    dynamic_A = (int*) calloc (N+2, sizeof(int)); 
    dynamic_B = (int*) calloc (N+2, sizeof(int)); 

    #pragma omp for 
    for (j = 0; j < size; j++) { 
    ... 
    } 

    free(dynamic_A); 
    free(dynamic_B); 
}