c++ - español - Reducir en matriz en OpenMP

openmp tutorial

Question

Estoy intentando paralelizar el siguiente programa, pero no sé cómo reducirlo en una matriz. Sé que no es posible hacerlo, pero ¿hay alguna alternativa? Gracias. (Agregué una reducción en m que es incorrecta pero me gustaría tener un consejo sobre cómo hacerlo).

#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

Sí, es posible hacer una reducción de matriz con OpenMP. En Fortran incluso tiene una construcción para esto. En C / C ++ tienes que hacerlo tú mismo. Aquí hay dos maneras de hacerlo.

El primer método crea una versión privada de S para cada hilo, los rellena en paralelo y luego los combina en S en una sección crítica (ver el código a continuación). El segundo método crea una matriz con dimensiones de 10 * n hilos. Llena esta matriz en paralelo y luego la fusiona en S sin usar una sección crítica. El segundo método es mucho más complicado y puede tener problemas de caché especialmente en sistemas multi-socket si no tiene cuidado. Para obtener más detalles, consulte este Histogramas de relleno (reducción de matriz) en paralelo con OpenMP sin utilizar una sección crítica

Primer método

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

Segundo método

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

Si traducir su código a Fortran, que puede usar matrices en operaciones de reducción de OpenMP, no es atractivo, podría usar un grupo de variables temporales. Por ejemplo

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

Esto te deja con la poco atractiva posibilidad de tener que escribir algún tipo de declaración de case o case para determinar cuál de los temporales debe actualizarse. Si su código es solo un ejemplo que desea usar para aprender, continúe.

Pero si su intención es realmente escribir una rutina de suma de prefijo paralela, entonces busque alrededor. Este es un buen lugar para comenzar.

Answer 3

Tengo dos comentarios sobre la respuesta de Zboson:
1. El método 1 es ciertamente correcto, pero el ciclo de reducción se ejecuta realmente en serie, debido a #pragma omp critical, que es por supuesto necesario ya que las matrices parciales son locales para cada hilo y la reducción correspondiente tiene que ser hecha por el hilo debido al matriz.
2. Método 2: el bucle de inicialización se puede mover fuera de la sección individual y, por lo tanto, ser paralelizable.

El siguiente programa implementa reducción de matriz utilizando la facilidad de reducción definida por el usuario de 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);
}

Esto sigue al pie de la letra el ejemplo de reducción de números complejos en la página 97 de las características de OpenMP 4.0 .

Aunque la versión paralela funciona correctamente, probablemente haya problemas de rendimiento, que no he investigado:

1. Las entradas y salidas add_m10x1 se pasan por valor.
2. El ciclo en add_m10x1 se ejecuta en serie.

Dichos "problemas de rendimiento" son de mi propia creación y es completamente sencillo no presentarlos:

1. Los parámetros para agregar_m10x1 se deben pasar por referencia (a través de punteros en C, referencias en C ++)
2. El cálculo en add_m10x1 se debe hacer en su lugar.
3. add_m10x1 debe declararse desierta y la declaración de devolución debe eliminarse. El resultado se devuelve a través del primer parámetro.
4. El pragma de reducción de declaración debe modificarse en consecuencia, el combinador debe ser solo una llamada de función y no una asignación (v4.0 especificaciones p181 líneas 9,10).
5. El bucle for en add_m10x1 se puede paralelizar a través de un omp paralelo para pragma
6. Anidamiento en paralelo debe estar habilitado (por ejemplo, a través de OMP_NESTED = TRUE)

La parte modificada del código es:

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}} )