Префикс суммы слишком долго OpenMP

Question

Я реализую проблему префиксных сумм в OpenMP, и, похоже, я не получаю ускорения. На самом деле параллельная реализация занимает больше времени, чем последовательная.

Вот мой код для префикса сумм:

for (k = 1; k < n; k = kk) { 
    kk = k << 1; 

    #pragma omp parallel for 
    for (i = kk - 1; i < n; i += kk) { 
     x[i] = x[i-k] + x[i]; 
    } 
} 

for (k = k >> 1; k > 1; k = kk) { 
    kk = k >> 1; 

    #pragma omp parallel for 
    for (i = k - 1; i < n - kk; i += k) { 
     x[i + kk] = x[i] + x[i + kk]; 
    } 
} 

Я собирал это с помощью GCC -fopenmp -O3 prefix_sums.c. Результаты, которые я получаю за 1 000 000 целых чисел являются:

для последовательного осуществления (составитель и с -O3):

0.001132 
0.000929 
0.000872 
0.000865 
0.000842 

для параллельной реализации (5 повторно запускается на 4 ядра):

0.025851 
0.005493 
0.006327 
0.007092 
0.030720 

Может ли кто-нибудь объяснить мне, в чем проблема? Реализация дает правильный результат, но почему это так долго?

спасибо.

Answer 1

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

Answer 2

Поскольку каждый элемент зависит от предыдущего элемента, вам придется разбить алгоритм в два этапа. Каждый поток будет вычислять только префикс на подмножестве целых чисел на первом этапе (так что каждый поток не имеет зависимости от какого-либо другого потока) и добавит результат других соответствующих потоков.

Например: x [3] зависит от x [0], x [1], x [2] и x [3]. Вы можете разбить расчет x [4] на два подмножества. Пусть один поток вычислит x [1], добавив 1 и 2, и пусть вторая нить суммирует 3 и 4 в x [4]. После этого шага потоки должны синхронизироваться (что openMP делает для вас, если вы начинаете второй параллельный цикл), а второй поток будет вычислять окончательный ответ, добавив x [2] в x [4]. Если у вас много целых чисел и много потоков, это может быть даже полезно, если вы выполните разбивку на три этапа.

Это в основном параллельное сокращение, которое может использоваться для распараллеливания большинства (?) Итерационных алгоритмов. В работе DrDobbs приведена теория и некоторые образы, на которых точно показано параллельное редукция.

Пс: При более внимательном рассмотрении вашего алгоритма, кажется, вы выполняете сложную проблему с префиксом довольно сложно. У него все еще есть много зависимостей (которые я внимательно изучил), но я думаю, что мои вышесказанные утверждения остаются в силе, и вы можете провести параллельное сокращение. Но мне было интересно: вы реализовали алгоритм, который был на самом деле предназначен для создания аппаратных схем?

Answer 3

Сумма префикса может быть параллельной как для MIMD (например, с помощью OpenMP), так и с SIMD (например, с SSE/AVX).

Это немного больно с OpenMP, чтобы сделать префиксную сумму, но это не так уж плохо. Я уже подробно рассказал об этом simd-prefix-sum-on-intel-cpu и здесь parallel-cumulative-prefix-sums-in-openmp-communicating-values-between-thread

Редактировать: вы делаете префиксную сумму на месте (in situ). Ссылки выше делают это не на месте (ex situ). Я изменил код (см. Ниже), чтобы сделать префиксную сумму на месте, когда вы это делаете, и проверил ее. Возможно, вам понадобится больше двух физических ядер, чтобы увидеть какой-либо benfit.

В основном вы делаете это за два прохода. В первом проходе вы делаете частичные суммы, а затем во втором проходе исправляете частичные суммы с константой для каждой частичной суммы. Второй проход будет векторизован хорошим компилятором (например, с GCC, но не с MSVC). Также возможно использовать SIMD и на первом проходе, но никакой компилятор, который я использовал, не будет векторизовать, поэтому вы должны сделать это самостоятельно с помощью встроенных средств.

Алгоритм идет как O (n), поэтому он быстро становится привязанным к памяти, а не вычисляется. Это означает, что для массивов, которые подходят только в кеше L1, служебные данные OpenMP слишком велики. В этом случае лучше просто использовать SIMD (у которого нет накладных расходов). Для больших массивов вы можете использовать как SIMD, так и MIMD, но в какой-то момент алгоритм становится привязанным к памяти, и он не намного быстрее, чем непараллельный алгоритм.

#include <stdio.h> 
#include <omp.h> 

void prefixsum_inplace(float *x, int N) { 
    float *suma; 
    #pragma omp parallel 
    { 
     const int ithread = omp_get_thread_num(); 
     const int nthreads = omp_get_num_threads(); 
     #pragma omp single 
     { 
      suma = new float[nthreads+1]; 
      suma[0] = 0; 
     } 
     float sum = 0; 
     #pragma omp for schedule(static) 
     for (int i=0; i<N; i++) { 
      sum += x[i]; 
      x[i] = sum; 
     } 
     suma[ithread+1] = sum; 
     #pragma omp barrier 
     float offset = 0; 
     for(int i=0; i<(ithread+1); i++) { 
      offset += suma[i]; 
     } 
     #pragma omp for schedule(static) 
     for (int i=0; i<N; i++) { 
      x[i] += offset; 
     } 
    } 
    delete[] suma; 
} 

int main() { 
    const int n = 20; 
    float x[n]; 
    for(int i=0; i<n; i++) x[i] = 1.0*i; 
    prefixsum_inplace(x, n); 
    for(int i=0; i<n; i++) printf("%f %f\n", x[i], 0.5*i*(i+1)); 
}