Внутренний последовательный цикл во внешнем параллельном цикле - OMP

Question

Я должен распараллелить первый цикл цикла в OMP, но внутри него существует цикл 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 зависимостям вы можете увидеть, что они не являются проходными осуществляются, так как любое значение dynamic_A[i] вычисленного в итерации j используется только в этой итерации. Весь массив будет перезаписан в следующей итерации внешнего цикла.

Вам необходимо переписать код, чтобы каждый поток имел свою личную копию 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); 
}