外部并行循环中的内部顺序循环 - 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); 
}