OpenMP: Параллелизуем для циклов внутри цикла while

Question

Я реализую алгоритм вычисления графика с использованием направленного на усиление. Я хотел бы добавить директивы OpenMP для ускорения некоторых циклов. После чтения некоторых курсов я добавил некоторые директивы OpenMP в соответствии с моим пониманием. Код компилируется, но не возвращает тот же результат, что и последовательная версия.

Интересно, будете ли вы любезны взглянуть на мой код и помочь мне разобраться, что происходит с моей версией OpenMP.

Пожалуйста, скачайте архив здесь: http://www.mediafire.com/download/3m42wdiq3v77xbh/drawgraph.zip

Как вы видите, часть кода, который я хочу, чтобы распараллелить является:

unsigned long graphLayout(Graph * graph, double * coords, unsigned long maxiter) 

В частности, эти две петли, которые потребляет много вычислительных ресурсов:

/* compute repulsive forces (electrical: f=-C.K^2/|xi-xj|.Uij) */  
    for(int j = 0 ; j < graph->nvtxs ; j++) { 
    if(i == j) continue; 
    double * _xj = _position+j*DIM; 
    double dist = DISTANCE(_xi,_xj);   
    // power used for repulsive force model (standard is 1/r, 1/r^2 works well) 
    // double coef = 0.0; -C*K*K/dist;  // power 1/r 
    double coef = -C*K*K*K/(dist*dist); // power 1/r^2 
    for(int d = 0 ; d < DIM ; d++) force[d] += coef*(_xj[d]-_xi[d])/dist; 
    } 

/* compute attractive forces (spring: f=|xi-xj|^2/K.Uij) */ 
    for(int k = graph->xadj[i] ; k < graph->xadj[i+1] ; k++) { 
    int j = graph->adjncy[k]; /* edge (i,j) */ 
    double * _xj = _position+j*DIM; 
    double dist = DISTANCE(_xi,_xj);    
    double coef = dist*dist/K; 
    for(int d = 0 ; d < DIM ; d++) force[d] += coef*(_xj[d]-_xi[d])/dist; 
    } 

Заранее благодарю за любую помощь, которую вы можете предоставить!

Answer 1

У вас есть данных гонок в вашем коде, например, при выполнении maxmove = nmove; или energy += nforce2;. В любом многопоточном коде вы не можете записывать в переменную, разделяемую потоками, до тех пор, пока не будете использовать атомный доступ (#pragma omp atomic read/write/update) или пока вы не будете явно синхронизировать доступ к такой переменной (критические разделы, блокировки). Сначала прочитайте несколько руководств по OpenMP, с вашим кодом больше проблем, например.

if(nmove > maxmove) maxmove = nmove; 

эта линия, как правило, не работает даже с Атомикс (вы должны использовать так называемые сравнения и обмена-атомарной операции для решения этой проблемы). Гораздо лучшее решение здесь - дать каждому потоку вычислить его локальный максимум и затем свести его к глобальному максимуму.