Уменьшение по массиву в OpenMP

Question

Я пытаюсь распараллелить следующую программу, но не знаю, как уменьшить массив. Я знаю, что это невозможно сделать, но есть ли альтернатива? Благодарю. (Я добавил сокращение на м, что является неправильным, но хотел бы иметь совет о том, как это сделать.)

#include <iostream> 
#include <stdio.h> 
#include <time.h> 
#include <omp.h> 
using namespace std; 

int main() 
{ 
    int A [] = {84, 30, 95, 94, 36, 73, 52, 23, 2, 13}; 
    int S [10]; 

    time_t start_time = time(NULL); 
    #pragma omp parallel for private(m) reduction(+:m) 
    for (int n=0 ; n<10 ; ++n){ 
    for (int m=0; m<=n; ++m){ 
     S[n] += A[m]; 
    } 
    } 
    time_t end_time = time(NULL); 
    cout << end_time-start_time; 

    return 0; 
} 

Answer 1

Да, с помощью OpenMP можно выполнить сокращение массива. В Фортране это даже построило для этого. В C/C++ вы должны сделать это сами. Вот два способа сделать это.

Первый способ делает частную версию S для каждой нити, заполняет их параллельно, а затем объединяет их в S в критическом разделе (см. Код ниже). Второй метод делает массив с размерами 10 * nthreads. Заполняет этот массив параллельно, а затем объединяет его в S без использования критического раздела. Второй метод намного сложнее и может иметь проблемы с кешем, особенно в многопроцессорных системах, если вы не будете осторожны. Для получения дополнительной информации см этот Fill histograms (array reduction) in parallel with OpenMP without using a critical section

Первый способ

int A [] = {84, 30, 95, 94, 36, 73, 52, 23, 2, 13}; 
int S [10] = {0}; 
#pragma omp parallel 
{ 
    int S_private[10] = {0}; 
    #pragma omp for 
    for (int n=0 ; n<10 ; ++n) { 
     for (int m=0; m<=n; ++m){ 
      S_private[n] += A[m]; 
     } 
    } 
    #pragma omp critical 
    { 
     for(int n=0; n<10; ++n) { 
      S[n] += S_private[n]; 
     } 
    } 
} 

Второй метод

int A [] = {84, 30, 95, 94, 36, 73, 52, 23, 2, 13}; 
int S [10] = {0}; 
int *S_private; 
#pragma omp parallel 
{ 
    const int nthreads = omp_get_num_threads(); 
    const int ithread = omp_get_thread_num(); 

    #pragma omp single 
    { 
     S_private = new int[10*nthreads]; 
     for(int i=0; i<(10*nthreads); i++) S_private[i] = 0; 
    } 
    #pragma omp for 
    for (int n=0 ; n<10 ; ++n) 
    { 
     for (int m=0; m<=n; ++m){ 
      S_private[ithread*10+n] += A[m]; 
     } 
    } 
    #pragma omp for 
    for(int i=0; i<10; i++) { 
     for(int t=0; t<nthreads; t++) { 
      S[i] += S_private[10*t + i]; 
     } 
    } 
} 
delete[] S_private; 

Answer 2

Если перевод кода на Fortran, которые могут использовать массивы в операциях по сокращению OpenMP, не привлекает , вы можете использовать кучу временных переменных. Например

int S0, S1, S2, ..., S9; 
... 
#pragma omp parallel for private(...) shared(S0, S1, S2, ..., S9) \ 
      reduction(+:S0, S1, S2, ..., S9) 
for ... 

Это оставляет вас с непривлекательной перспективой того, чтобы написать какой-то if или case заявление, чтобы определить, какой из временных должен быть обновлен. Если ваш код является просто примером, который вы хотите использовать для обучения, продолжайте.

Но если ваше намерение действительно писать параллельную префиксную рутину, тогда выполните поиск. This is a good place to start.

Answer 3

У меня есть два замечания по поводу ответа Zboson в:
1. Метод 1, конечно, правильно, но цикл редукция фактически выполняются серийно, из-за #pragma omp критический, который, конечно, необходим, поскольку частичные матрицы являются локальными для каждого потока, а corr требуемое сокращение должно выполняться нитью из-за матрицы.
2. Способ 2: Цикл инициализации может перемещаться за пределы отдельной секции и, следовательно, стать параллелизуемым.

Следующая программа реализует сокращение массива использованием OpenMP v4.0 определенного пользователем объекта уменьшения:

/* Compile with: 
    gcc -Wall -fopenmp -o ar ar.c 
    Run with: 
    OMP_DISPLAY_ENV=TRUE OMP_NUM_THREADS=10 OMP_NESTED=TRUE ./ar 
*/ 
#include <stdio.h> 
#include <omp.h> 
struct m10x1 {int v[10];}; 
int A [] =  {84, 30, 95, 94, 36, 73, 52, 23, 2, 13}; 
struct m10x1 S = {{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}}; 
int n,m=0; 

void print_m10x1(struct m10x1 x){ 
    int i; 
    for(i=0;i<10;i++) printf("%d ",x.v[i]); 
    printf("\n"); 
} 

struct m10x1 add_m10x1(struct m10x1 x,struct m10x1 y){ 
    struct m10x1 r ={{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}}; 
    int i; 
    for (i=0;i<10;i++) r.v[i]=x.v[i]+y.v[i]; 
    return r; 
} 

#pragma omp declare reduction(m10x1Add: struct m10x1: \ 
omp_out=add_m10x1(omp_out, omp_in)) initializer(\ 
omp_priv={{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}}) 

int main() 
{ 
    #pragma omp parallel for reduction(m10x1Add: S) 
    for (n=0 ; n<10 ; ++n) 
    { 
     for (m=0; m<=n; ++m){ 
     S.v[n] += A[m]; 
     } 
    } 
    print_m10x1(S); 
} 

Это следует дословно сложный пример сокращения числа на стр 97 OpenMP 4.0 features.

Хотя параллельная версия корректно работает, то, вероятно, проблемы с производительностью, которые я не исследованные:

1. add_m10x1 входов и выходов передаются по значению.
2. Цикл в add_m10x1 запускается серийно.

Упомянутый «проблемы производительности» являются моего собственного изготовления, и это совершенно просто, чтобы не вводить их:

1. Параметры для add_m10x1 должны быть переданы по ссылке (с помощью указателей в C, ссылки в C++)
2. Вычисление в add_m10x1 должно выполняться на месте.
3. add_m10x1 должно быть объявлено недействительным, а оператор возврата удален. Результат возвращается через первый параметр.
4. Декларация о сокращении прагмы должна быть соответственно изменена, объединитель должен быть просто вызовом функции, а не назначением (спецификации v4.0 p181 строк 9,10).
5. для цикла в add_m10x1 может быть распараллелены через OMP параллельно для прагме
6. Параллельный раскрой должен быть включен (например, через OMP_NESTED = TRUE)

Модифицированный часть кода, то есть:

void add_m10x1(struct m10x1 * x,struct m10x1 * y){ 
    int i; 
    #pragma omp parallel for 
    for (i=0;i<10;i++) x->v[i] += y->v[i]; 
} 

#pragma omp declare reduction(m10x1Add: struct m10x1: \ 
add_m10x1(&omp_out, &omp_in)) initializer(\ 
omp_priv={{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}})