Как работают операции сокращения в OpenMP под капотом - PullRequest
Новая
       33

Как работают операции сокращения в OpenMP под капотом

0 голосов
/ 29 мая 2019

Я пытаюсь оптимизировать производительность в цикле параллельно для , где у меня есть редукционная переменная (называемая delta ), и мне интересно, как это обрабатывается под капотом библиотекой OpenMP.

Давайте возьмем в качестве примера следующий фрагмент кода, в котором я просто объявляю переменную как редукционную в начале цикла следующим образом: 

#pragma omp parallel shared(delta, A, B, rows, colms) private(i, j)
.
.
.
    #pragma omp for reduction(+:delta)
            for (i=1; i<=rows; i++){
                for (j=1; j<=colms; j++){
                delta += fabs(A[i][j]- B[i][j]);
                }
    }
.
.
.
//end of parallel region

Мне интересно, устанавливает ли каждый поток во время вычисления блокировку при доступе к переменной delta и, кроме того, могу ли я повысить производительность, заменив переменную delta на массив delta [number_of_threads] , где каждый поток будет записывать в разные позиции массива во время вычисления, а затем суммировать все элементы после параллельной области.

1 Ответ

3 голосов
/ 29 мая 2019

Каждый поток будет иметь свою собственную копию 'delta' в своем кадре стека: 

#pragma omp parallel shared(delta, A, B, rows, colms) private(i, j)
{
    double local_delta; // one copy per thread

    __omp_init_schedule(1, rows, &lb, &ub);
    for (i=lb; i<=ub; i++) {
        for (j=1; j<=colms; j++) {
                local_delta += fabs(A[i][j]- B[i][j]);
        }
    }
   __omp_reduce(&delta, local_delta);  // accumulate thread's delta with shared var
   __omp_barrier();                    // do the barrier of the for construct
}

Пожалуйста, примите вышесказанное как псевдокод. Фактический шаблон кода будет зависеть от реализации, встраивания и других видов оптимизации, которые может выполнить реализация OpenMP. Если вы хотите прочитать немного о том, как все работает, посмотрите на [1] и [2].

Реализация __omp_reduce() может быть либо чем-то основанной на дереве, либо последовательной, используя либо блокировки, либо атомарные инструкции. Реализации OpenMP обычно довольно умны и выбирают правильный алгоритм для машины и / или количества используемых потоков.

Выполнение модификации delta[numthreads], вероятно, приведет к снижению производительности более чем в 100 раз, поскольку это типичный пример ложного разделения, поскольку delta[0] для потока 0 и delta[1] для первого потока будут находиться в одной строке кэша, и это вызывает много трафика на кеш и память. Лучше было бы ввести паттинг delta[numthreads * 8] (при условии, что delta равен 8 байтам), чтобы каждый поток получал свою собственную строку кэша. Однако тогда вам все еще нужно выполнить окончательное агрегирование, и, вероятно, реализация OpenMP по-прежнему будет работать лучше.

[1] https://www.dontknow.de/openmp-stuff/the-thing-from-another-world-or-how-do-openmp-compilers-work-part-1/

[2] https://www.dontknow.de/openmp-stuff/thunk-you-very-much-or-how-do-openmp-compilers-work-part-2/

...