Последовательные и параллельные версии дают разные результаты - Почему?

Question

У меня есть вложенный цикл: (L и А полностью определены входы)

#pragma omp parallel for schedule(guided) shared(L,A) \ 
    reduction(+:dummy) 
    for (i=k+1;i<row;i++){ 
      for (n=0;n<k;n++){ 
       #pragma omp atomic 
       dummy += L[i][n]*L[k][n]; 
       L[i][k] = (A[i][k] - dummy)/L[k][k]; 
      } 
      dummy = 0; 
    } 

И его последовательная версия:

for (i=k+1;i<row;i++){ 
      for (n=0;n<k;n++){ 
       dummy += L[i][n]*L[k][n]; 
       L[i][k] = (A[i][k] - dummy)/L[k][k]; 
      } 
      dummy = 0; 
    } 

Они оба дают разные результаты. Параллельная версия намного медленнее, чем последовательная версия.

Что может вызвать проблему?

Edit:

Чтобы избавиться от проблем, вызванных атомной директивой, я изменил код следующим образом:

#pragma omp parallel for schedule(guided) shared(L,A) \ 
    private(i) 
    for (i=k+1;i<row;i++){ 
     double dummyy = 0; 
     for (n=0;n<k;n++){ 
      dummyy += L[i][n]*L[k][n]; 
      L[i][k] = (A[i][k] - dummyy)/L[k][k]; 
     } 
    } 

Но это также не сработало проблему. Результаты по-прежнему различны.

Answer 1

Разница в результатах зависит от внутренней переменной цикла n, которая разделяется между потоками, поскольку она определяется вне прагмы omp.

Уточнено: Петля переменная n должна быть объявлена ​​внутри OMP прагме, так как она должна быть нить конкретным, например for (int n = 0;.....)

Answer 2

Я не очень хорошо знаком с OpenMP, но мне кажется, что ваши вычисления не зависят от заказа. А именно, результат во внутреннем цикле записывается в L[i][k], где i и k являются инвариантами для внутреннего цикла. Это означает, что одно и то же значение перезаписывается k раз во время внутреннего цикла, что приводит к состоянию гонки.

Кроме того, dummy, по-видимому, делится между различными потоками, поэтому там может быть состояние гонки, если только ваши параметры прагмы каким-то образом не предотвращают его.

В целом, мне кажется, что вычисления во внутреннем цикле должны выполняться в одном и том же порядке, если вы хотите получить тот же результат, что и при последовательном выполнении. Таким образом, только внешний цикл может быть распараллелен.

Answer 3

В вашей параллельной версии вы вставили ненужную (и, возможно, вредную) атомную директиву. После того, как вы объявили dummy редукционной переменной, OpenMP позаботится об остановке потоков, препятствующих сокращению. Я думаю, что основное влияние ненужной директивы - медленное замедление вашего кода.

Я вижу, что у вас есть другой ответ, касающийся неправильности ваших результатов. Но я замечаю, что вы, кажется, устанавливаете dummy в 0 в конце каждой итерации внешнего цикла, что кажется странным, если вы пытаетесь использовать его в качестве своего рода аккумулятора, что и предлагает предложение о сокращении. Возможно, вы хотите уменьшить до dummy через внутренний цикл?

Если у вас возникли проблемы с редукцией read this.