LU разложение OpenMP

#openmp #c #алгоритм #cpp #распараллеливание

Почему параллельная версия работает за то же время или больше чем последовательная
версия алгоритма? Что я сделал не так?
LU разложение с помощью OpenMP:
void lup_od_omp(double* a, int n){

int i,j,k;

for(k = 0; k < n - 1; ++k)
{
    #pragma omp parallel for shared(a,n,k) private(i,j)
    for(i = k + 1; i < n; i++)
    {
        a[i*n + k] /= a[k*n + k];
        for(j = k + 1; j < n; j++)
        {
            a[i*n + j] -= a[i*n + k]*a[k*n + j];
        }
    }
}
}

P.S. Матрица хранится в одномерном массиве. Та же самая ситуация с временем выполнения
(параллельно >= последовательно) и с матрицей, хранящейся в двумерном массиве.    

Ответы

Ответ 1

Вопрос старый, но без ответа.

Как вариант - проблема в том, что массив a совместно используется для записи в потоках.
В таком случае параллельный вариант вполне может работать даже медленнее последовательного.
На большем количестве ядер, думаю, эффект должен быть очевиднее.

Каждая запись на ядре 0 будет вытеснять любое чтение на ядре 1 и наоборот - запись
на ядре 1 будет вытеснять чтение по этим же адресам на ядре 0 (см. "когерентность кэша").

Решить проблему можно, если выделить каждому потоку свой буфер для сохранения результатов
(равноудаленный друг от друга как минимум на 32/64 байта, а еще лучше - выровненный
при этом на те же 32/64 байта [кэш-линия]).

Замечание от @Михаил М, думаю, тоже в силе, но в таком случае, я уже сомневаюсь насчет
корректности параллельного алгоритма: очевидно, в смежной ячейке может находиться значение,
модифицированное другим потоком, а это поменяет результат вычислений.