Как распараллелить эту структуру?

Question

Я пытаюсь распараллеливание следующую структуру с использованием OpenMP в C++:

x1,x2,y1,y2,k1,k2 = 0; 
a1,a2,b1,b2; //initialized to some value 
vec1,vec2; 

for (i=0;i<N;++i) { 
    for (j=0;j<M;++j) { 
     x2 = j - a2; 
     y2 = i - b2; 

     func(x1,y1,x2,y2); // the function changes x1,y1 values 

     x2 = x1; 
     y2 = y1; 

     func2(x1,y1,x2,y2); // the function changes x1,y1 values 

     x1 += a1; 
     y1 += b1; 

     k1 = func3(x1,y1); 

     vec2[k2] = vec1[k1]; 
     vec2[k2+1] = vec1[k1+1]; 

     k2 += 2; 
    } 
} 

Не могли бы вы мне помочь ?. Я очень ценю любую помощь, которую вы можете предоставить.

EDIT:

Последнее решение, которое я попытался это:

x1,x2,y1,y2,k1,k2 = 0; 
a1,a2,b1,b2; //initialized to some value 
vec1,vec2; 

#pragma omp parallel for ordered schedule(dynamic,1) collapse(2) 
for (i=0;i<N;++i) { 
    for (j=0;j<M;++j) { 
     x2 = j - a2; 
     y2 = i - b2; 

     func(x1,y1,x2,y2); // the function changes x1,y1 values 

     x2 = x1; 
     y2 = y1; 

     func2(x1,y1,x2,y2); // the function changes x1,y1 values 

#pragma omp critical 
{ 
     x1 += a1; 
     y1 += b1; 
} 

     k1 = func3(x1,y1); 

#pragma omp ordered 
{ 
     vec2[k2] = vec1[k1]; 
     vec2[k2+1] = vec1[k1+1]; 
} 

#pragma omp atomic 
     k2 += 2; 
    } 
} 

В результате в сбоем сегментации.

Answer 1

Я прочитал ваш чат с @Guiroux, а также определил, что ваши петли независимы. Единственная вещь, которая в настоящее время переносится с итерации на итерацию, равна k2, которая может быть вычислена непосредственно из i и j вместо (k2 = 2*j+2*M*i).

Таким образом, ваш распараллеливание код может быть просто

int k1, k2; 
double x1,x2,y1,y2; 
double a1,a2,b1,b2; //initialized to some values 
double vec1[2*M*N],vec2[2*M*N]; // vec1 is read-only past this point 

/* 
    NOTE: private(var) means that it may no longer have same value it had previously. 
    In your case, these were all set to 0 before. After reading chat, it seems that 
    they were never actually used as input anyway. As long as they are written to 
    before being read from (i.e. x1,y1 in func), no seg fault will occur. 
*/ 
#pragma omp parallel for private(x2,y2,x1,y1,k1,k2) 
for (int i=0; i<N; ++i) {  // I defined i,j here 
    for (int j=0; j<M; ++j) { // If you define them outside parallel for, 
           // they must also be made private 

     // variables set below are all private, so no threads will overwrite 
     // work that other threads have done 
     x2 = j - a2; 
     y2 = i - b2; 

     func(x1,y1,x2,y2); // the function sets x1,y1 values 

     x2 = x1; 
     y2 = y1; 

     func2(x1,y1,x2,y2); // the function sets x1,y1 values 

     x1 += a1; 
     y1 += b1; 

     k1 = func3(x1,y1); 

     // k2 is never the same for 2 different values of i, 
     // so different threads will never clobber each other here: 
     k2 = 2*j+2*M*i; 
     vec2[k2] = vec1[k1]; 
     vec2[k2+1] = vec1[k1+1]; 

    } 
} 

Вы не должны разрушаться обе петли. До тех пор, пока N > nCoresOnYourComputer, вы можете увидеть, как работа будет равномерно распределена между всеми процессорами.

Надеюсь, что все имеет смысл. Попробуйте и выясните в моем коде, почему мне пришлось определить определенные переменные private (vs по умолчанию shared), и почему k2 необходимо переопределить, как и я.

Упражнение для читателя: как еще вы можете установить k2 (что также безопасно избегает условий гонки), но в основном сохраняет логику, из которой вы первоначально использовали (т. Е. k2 += 2 на каждой итерации)?