Параллельный цикл с использованием OpenMP, когда итерации цикла не являются независимыми

Question

У меня есть реализация цифрового бесселевого фильтра, который является узким местом производительности для моей программы. Я хотел бы распараллелить основной цикл с помощью OpenMP.

Функция принимает входной массив paddedsignal и массивы коэффициентов фильтра dcof и ccof и производит временный массив temp который фильтруют. Основной цикл этого процесса выглядит следующим образом:

for (i=order; i<end; i++) 
    { 
     temp[i] = ccof[0]*paddedsignal[i]; 
     for (p=1; p<=order; p++) 
     { 
      temp[i] += ccof[p]*paddedsignal[i-p] - dcof[p]*temp[i-p]; 
     } 
    } 

В частности, обратите внимание, что значение temp[i] зависит от предыдущих значений temp[i-p]. Это смешивает простую директиву #pragma omp for, так как значение temp[i] вблизи границ между разделами массива, которое будет обрабатываться разными потоками, будет иметь проблемы с состоянием гонки. В основном, если поток 1 принимает индексы между 0-99, а поток 2 принимает 100-199, значение в 100 будет неправильным, так как оно будет вычислено до значения в 99, от которого это зависит.

Есть ли способ спасти эту ситуацию? Я отчаиваюсь относительно того, что я могу сделать, чтобы распараллелить это, поскольку тот факт, что отфильтрованные значения зависят от соседних значений, делает его по сути серийным вычислением. Есть ли способ обойти это?

Answer 1

В основном вы не можете распараллелить внешний цикл из-за зависимости, которую вы правильно идентифицируете.

Вы можете распараллелить внутренний цикл с уменьшением. Но это было бы полезно только для больших order, и даже тогда, возможно, просто приведет к ложному обмену, потому что данные перетасовываются. Можно было бы попытаться усложнить данные, чтобы чередовать signal и temp среди потоков, что потребовало бы сортировки конструкции совместного использования вручную. Я сомневаюсь, что это того стоит, так как сокращение приведет к увеличению накладных расходов.

Легче распараллелить фильтры с конечной импульсной характеристикой, если это альтернатива для вас. Вы также можете сегментировать весь сигнал в несколько перекрывающихся сегментов и самостоятельно вычислять фильтр, но на границах этих фрагментов будет некоторая вычислительная ошибка.

Answer 2

Возможно, вы ищете #pragma omp для заказа . Он выполняет код в том же порядке, в котором он будет выполняться последовательно

Но имейте в виду:

• могут быть использованы только в динамическом экстента для директивы
• очень «дорого» (вполне вероятно, что ваше убыстрение не будет столь же хорошо, как вы могли бы подумать)

Для получения дополнительной информации см: omp ordered