Как я могу распараллелить этот цикл с помощью OpenMP?

Question

Я только начал изучать OpenMP и нашел этот код ниже

#pragma omp parallel for
for (int i = 1; i < N; i++) { A[i] = B[i] – A[i – 1]; }

Интересно, можно ли распараллелить этот цикл?

Answer 1

Вот эквивалентный код, который читает только из 1 массива:

auto a = A[ 0 ];
for( int i = 1; i < N; i++ )
{
    a = B[ i ] - a;
    A[ i ] = a;
}

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

Кстати, если ваши значения являются числами с плавающей запятой, целыми числами или чем-то одинаково быстрым для вычисления operator -, скорость кода может быть ограничена пропускной способностью ОЗУ, а невычисления.Распараллеливание не очень поможет.

Answer 2

Я бы сказал нет (по крайней мере, не так, как стоило бы). Рассмотрим способ базового распараллеливания с использованием двух потоков:

// thread # 1
for(int i = 1; i < N / 2; i++) { A[i] = B[i] – A[i – 1]; }

// thread # 2
for(int i = N / 2; i < N; i++) { A[i] = B[i] – A[i – 1]; }

Потоки будут работать параллельно, поэтому второй поток будет вычислять A [N / 2] на основе A [N / 2 - 1], который, вероятно, еще не рассчитан первым потоком. Если вы найдете способ предварительно рассчитать «смежные» элементы (например, N / 2 - 1 в нашем случае), то это может сработать. Но для этого вы должны пройти все элементы до N / 2. Вы также можете сделать некоторые арифметические трюки для предварительного вычисления некоторых элементов, но тогда у вас должны быть другие циклы, которые сделают распараллеливание неэффективным ...