Reducción de la matriz en OpenMP

Estoy tratando de paralelizar el siguiente programa, pero no sé cómo reducir en una matriz. Sé que no es posible hacerlo, pero hay una alternativa? Gracias. (He añadido reducción en m que está mal, 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;
}
Author: Jeff, 2013-12-06
Source

3 answers

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

El primer método hace una versión privada de S para cada hilo, los rellena en paralelo, y luego los fusiona en S en una sección crítica (consulte el código a continuación). El segundo método hace una matriz con dimensiones 10 * nthreads. Rellena esta matriz en paralelo y luego la fusiona en S sin usar una matriz crítica apartado. 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 más detalles vea esto Rellene histogramas (reducción de matriz) en paralelo con OpenMP sin usar 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;
 25
Author: Z boson,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2017-05-23 10:30:59

Tengo dos comentarios sobre la respuesta de Zboson:
1. El método 1 es ciertamente correcto, pero el bucle de reducción en realidad se ejecuta en serie, debido a la #pragma omp critical que es, por supuesto, necesaria ya que las matrices parciales son locales para cada hilo y la reducción correspondiente tiene que ser hecha por el hilo que debe la 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 matrices utilizando la facilidad de reducción definida por el usuario 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 textualmente el ejemplo de reducción de números complejos en la página 97 de OpenMP 4.0 features.

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

  1. add_m10x1 las entradas y salidas se pasan por valor.
  2. El bucle en add_m10x1 se ejecuta en serie.

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

  1. Los parámetros a add_m10x1 deben pasarse por referencia (a través de punteros en C, referencias en C++)
  2. El cálculo en add_m10x1 debe hacerse en su lugar.
  3. add_m10x1 debe ser declarado nulo y la instrucción return eliminada. El resultado se devuelve mediante el primer parámetro.
  4. La declaración reduction pragma debe modificarse en consecuencia, el combinador debe ser solo una llamada a la función y no una asignación (v4.0 specs p181 lines 9,10).
  5. El bucle for en add_m10x1 puede ser paralelizado a través de un paralelo omp para pragma
  6. Se debe habilitar el anidamiento paralelo (por ejemplo, a través de OMP_NESTED=TRUE)

La parte modificada del código entonces 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}} )
 7
Author: NameOfTheRose,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2015-02-06 08:22:15

Si traducir su código a Fortran, que puede usar arrays en operaciones de reducción de OpenMP, no es atractivo, podría usar un montón 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 le deja con la perspectiva poco atractiva de tener que escribir algún tipo de declaración if o case para determinar cuál de los temporales se actualizará. Si su código es solo un ejemplo que desea usar para aprender, continúe.

Pero si tu intención es realmente escribir un prefijo paralelo sum rutina y luego buscar alrededor. Este es un buen lugar para comenzar.

 0
Author: High Performance Mark,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2017-05-23 11:55:16