OpenMP - параллелизм и вложенные циклы - PullRequest
Новая
       6

OpenMP - параллелизм и вложенные циклы

0 голосов
/ 25 мая 2018

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

while( var > tol && iter <= maxIter ) {
    ++iter;
    var = 0.0;

    for (i=1; i<=n; ++i)
        for (j=1; j<=n; ++j) {         
            Tnew[i*n2+j] = 0.25*( T[(i-1)*n2+j] + T[(i+1)*n2+j] 
                                + T[i*n2+(j-1)] + T[i*n2+(j+1)] );

            var = fmax(var, fabs(Tnew[i*n2+j] - T[i*n2+j]));
        }
}

Лично я считаю, что лучшим вариантом было бы поместить его непосредственно перед внутренним циклом, поскольку я считаю, что это не вызовет проблем с зависимостями.Однако, друг сказал мне, что это будет слишком дорого.Каков наилучший способ и почему?

1 Ответ

0 голосов
/ 31 мая 2018

Прежде всего, я думаю, что вы забыли поменять местами массивы Tnew и T в конце всех итераций внешнего цикла.Предполагая, что это указатели, вот исправленный серийный код: 

while(var > tol && iter <= maxIter) {
    ++iter;
    var = 0.0;
    for (i=1; i<=n; ++i)
        for (j=1; j<=n; ++j) {         
            Tnew[i*n2+j] = 0.25*(T[(i-1)*n2+j] + T[(i+1)*n2+j] 
                                + T[i*n2+(j-1)] + T[i*n2+(j+1)]);
            var = fmax(var, fabs(Tnew[i*n2+j] - T[i*n2+j]));
        }
    }
    temp = TNew;
    TNew = T;
    T = temp;
}

Теперь вы можете попытаться распараллелить i -циклоп.Обратите внимание, что var должна быть общей переменной, поэтому ее обновления будут происходить в самой внутренней параллельной области;мы будем использовать critical конструкцию для обеспечения атомарности.Вот основной код: 

while(var > tol && iter <= maxIter) {
    ++iter;
    var = 0.0;
    #pragma omp parallel for
    for (i=1; i<=n; ++i)
        for (j=1; j<=n; ++j) {         
            Tnew[i*n2+j] = 0.25*(T[(i-1)*n2+j] + T[(i+1)*n2+j] 
                                + T[i*n2+(j-1)] + T[i*n2+(j+1)]);
            #pragma omp critical
            {
                var = fmax(var, fabs(Tnew[i*n2+j] - T[i*n2+j]));
            }
        }
    }
    temp = TNew;
    TNew = T;
    T = temp;
}

Как правильно заметил ваш друг, накладные расходы на создание / завершение потока могут быть высокими, если область parallel создается и уничтожается большое количество раз.Следовательно, с помощью конструкции master или single мы должны теперь попытаться переместить эту параллельную конструкцию за пределы самого внешнего цикла.Вот пример перевода: 

#pragma omp parallel private(iter) shared(var, maxIter)
{   
    while(var > tol && iter <= maxIter) {
        ++iter;
        #pragma omp barrier
        #pragma omp single
        {
            var = 0.0;
        }
        #pragma omp for
        for (i=1; i<=n; ++i)
            for (j=1; j<=n; ++j) {         
                Tnew[i*n2+j] = 0.25*(T[(i-1)*n2+j] + T[(i+1)*n2+j] 
                                    + T[i*n2+(j-1)] + T[i*n2+(j+1)]);
                #pragma omp critical
                {
                    var = fmax(var, fabs(Tnew[i*n2+j] - T[i*n2+j]));
                }
            }
        }
        #pragma omp single
        {
            temp = TNew;
            TNew = T;
            T = temp;
        }
    }
}

Обратите внимание, что важно приватизировать iter.Также обратите внимание, что явные и неявные барьеры гарантируют отсутствие расы между различными доступами к var, TNew и T.

О конструкции critical: Обратите внимание, чтоэто может быть дорого вызывать критическую область большое количество раз внутри самой внутренней петли.Вы должны использовать приватную переменную для получения максимальной разницы для каждого потока, а затем использовать критическую область вне циклов for, чтобы получить правильное значение var.Я оставлю вам фактический перевод.

Предложение : Протестируйте этот код для некоторого большого набора данных, то есть для некоторых больших значений n (около 500-2000)и небольшие значения tol (около 0,01-0,001), чтобы увидеть любое видимое ускорение по сравнению с серийным кодом;в противном случае затраты на синхронизацию могут нейтрализовать любые преимущества параллелизма, делая параллельную версию менее эффективной, чем последовательная.

...