Сокращение по массиву в OpenMP

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

#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;
}

Ответ 1

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

Первый метод делает закрытую версию S для каждого потока, заполняет их параллельно, а затем объединяет их в S в критическом разделе (см. код ниже). Второй метод делает массив с размерами 10 * nthreads. Заполняет этот массив параллельно, а затем объединяет его в S без использования критического раздела. Второй метод намного сложнее и может иметь проблемы с кешем, особенно в многопроцессорных системах, если вы не будете осторожны. Подробнее см. В этом Гистограммы заполнения (уменьшение массива) параллельно с OpenMP без использования критического раздела

Первый метод

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;

Ответ 2

У меня есть два замечания относительно ответа Zboson:
1. Метод 1, безусловно, правильный, но цикл восстановления фактически запускается серийно из-за критического #pragma omp, который, конечно, необходим, так как частичные матрицы являются локальными для каждого потока, и соответствующее сокращение должно выполняться потоком из-за матрица.
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.

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

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

Упомянутые "проблемы с производительностью" являются моими собственными решениями, и совершенно просто не вводить их:

Параметры add_m10x1 должны передаваться по ссылке (через указатели в C, ссылки на С++)
Вычисление в add_m10x1 должно выполняться на месте.
add_m10x1 должен быть объявлен void и оператор return удален. Результат возвращается через первый параметр.
Декларация о сокращении прагмы должна быть соответствующим образом изменена, объединитель должен быть просто вызовом функции, а не назначением (спецификации v4.0 p181 строки 9,10).
Цикл for в add_m10x1 можно распараллелить с помощью omp parallel для pragma
Параллельная вложенность должна быть включена (например, через 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}} )

Ответ 3

Если перевод вашего кода в 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, чтобы определить, какой из временных файлов должен быть обновлен. Если ваш код является просто примером, который вы хотите использовать для обучения, продолжайте.

Но если ваше намерение действительно писать параллельную префиксную рутину, тогда выполните поиск. Это хорошее место для начала.