PDF de programación - Programación híbrida - Computación Matricial y Paralela

Computación Matricial y Paralela

Programación híbrida

Javier Cuenca

Domingo Giménez

Dpto. de Ingeniería y Tecnología de Computadores

Dpto. de Informática y Sistemas

Universidad de Murcia

http://dis.um.es/~domingo

Univ. Politécnica de Cartagena

1

Contenido
 Nociones básicas de programación

híbrida

 Ejemplos básicos
 Ejemplos con operaciones matriciales

Univ. Politécnica de Cartagena

2

Nociones básicas de
Programación Híbrida

OpenMP

Paralelismo de grano fino
Eficiencia en SMP
Códigos secuencial y paralelo 

similares

Herramientas de desarrollo y 

paralelización

MPI

Paralelismo de grado grueso
Más portable
Código paralelo muy diferente

del secuencial

Desarrollo y depuración más

difícil

Permite asignación en tiempo de 

ejecución

Asignación estática de

procesos

La asignación de memoria puede 

reducir las prestaciones

Memorias locales, que

facilitan eficiencia

Univ. Politécnica de Cartagena

3

Nociones básicas de
Programación Híbrida

Ventajas de la Programación Híbrida

● Para mejorar la escalabilidad
● Cuando muchas tareas producen desbalanceo
● Aplicaciones que combinan paralelismo de grano grueso 

y fino

● Reducción del tiempo de desarrollo de código
● Cuando el número de procesos MPI es fijo
● En caso de mezcla de paralelismo funcional y de datos

Univ. Politécnica de Cartagena

4

Nociones básicas de
Programación Híbrida

Programación Híbrida en la literatura

● La mayoría d elos artículos son sobre aplicaciones 

concretas

● Algunos artículos presentan modelos híbridos
● No hay modelos teóricos del tiempo de ejecución

Univ. Politécnica de Cartagena

5

Nociones básicas de
Programación Híbrida

Sistemas híbridos

● Redes de Pentiums duales
● HPC160 (cada nodo 4 procesadores)
● IBM SP
● Blue Horizon (144 nodos, cada uno 8 procesadores)
● Earth Simulator (640 8 procesadores vectoriales)
● Marenostrum (2406 nodos biprocesadores)

…

Univ. Politécnica de Cartagena

6

Nociones básicas de
Programación Híbrida

La gran 
mayoría
son sistemas
híbridos

Univ. Politécnica de Cartagena

7

Nociones básicas de
Programación Híbrida

Modelos

MPI+OpenMP

OpenMP usado para paralelización de bucles

OpenMP+MPI

Threads no seguros

Procesos MPI y OpenMP en modelo SPMD

Reduce el coste de las comunicaciones

                                                                           

Univ. Politécnica de Cartagena

8

Nociones básicas de
Programación Híbrida

Univ. Politécnica de Cartagena

9

Nociones básicas de
Programación Híbrida

No está claro si con programación híbrida se reduce el tiempo de

ejecución

Lanucara, Rovida: Gradiente-Conjugado

Univ. Politécnica de Cartagena

10

Nociones básicas de
Programación Híbrida

Djomehri, Jin:

Ecuaciones deferenciales

Univ. Politécnica de Cartagena

11

Nociones básicas de
Programación Híbrida

Viet, Yoshinaga, Abderazek,
Sowa: Sistemas lineales

Univ. Politécnica de Cartagena

12

Ejemplos básicos
int main(int argc, char *argv[])  {                                 
    int nthreads,nprocs,idpro,idthr;  int  namelen;
    char processor_name[MPI_MAX_PROCESSOR_NAME];
    MPI_Init(&argc,&argv);
    MPI_Comm_size(MPI_COMM_WORLD,&nprocs);
    MPI_Comm_rank(MPI_COMM_WORLD,&idpro);
    MPI_Get_processor_name(processor_name,&namelen);
#pragma omp parallel private(idthr) firstprivate(idpro,processor_name)    {
        idthr = omp_get_thread_num();
        printf("... thread %d, proceso %d procesador 

%s\n",idthr,idpro,processor_name);

        if (idthr == 0) {
            nthreads = omp_get_num_threads();
            printf(" proceso %d, threads %d, procesos %d\n",idpro,nthreads,nprocs);
        } }
    MPI_Finalize(); }

Univ. Politécnica de Cartagena

13

Ejemplos básicos

int main (int argc,char **argv)  {
//Variables
  int i,load,begin,end,*a,n,l,u,x,keepon=1,position=­1,thread=­1;
  int nthreads,nprocs,idpro,idthr;
  int  namelen;
  char processor_name[MPI_MAX_PROCESSOR_NAME];
  MPI_Status estado;

//Iniciación MPI
  MPI_Init(&argc,&argv);
  MPI_Comm_size(MPI_COMM_WORLD,&nprocs);
  MPI_Comm_rank(MPI_COMM_WORLD,&idpro);
  MPI_Get_processor_name(processor_name,&namelen);

Univ. Politécnica de Cartagena

14

Ejemplos básicos

  if(idpro==0)  {  //Entrada y envío de datos
    printf("De el numero de datos del array: "); scanf("%d",&n);
    MPI_Bcast(&n, 1, MPI_INT, 0, MPI_COMM_WORLD);
    a=(int *) malloc(sizeof(double)*n);
    printf("De los valores minimo y maximo: "); scanf("%d %d",&l,&u);
    generar_enteros(a,n,l,u); escribir_enteros(a,n);
    printf("De el numero a buscar: "); scanf("%d",&x);
    MPI_Bcast(&x, 1, MPI_DOUBLE, 0, MPI_COMM_WORLD);
    for(i=1;i<nprocs;i++)          

MPI_Send(&a[i*n/nprocs],n/nprocs,MPI_INT,i,ENVIO_INICIAL,

          MPI_COMM_WORLD);
  }  else {  //Recepción de datos
    MPI_Bcast(&n, 1, MPI_INT, 0, MPI_COMM_WORLD);
    MPI_Bcast(&x, 1, MPI_DOUBLE, 0, MPI_COMM_WORLD);
    a=(int *) malloc(sizeof(int)*n/nprocs);
    MPI_Recv(a,n/nprocs,MPI_INT,0,ENVIO_INICIAL,MPI_COMM_WORLD,
        &estado);
  }

Univ. Politécnica de Cartagena

15

Ejemplos básicos

//Puesta en marcha de los threads 
#pragma omp parallel private(idthr,i,load,begin,end)
  {
#pragma omp master
    nthreads = omp_get_num_threads();
    idthr = omp_get_thread_num(); load = n/nprocs/nthreads;  
    begin = idthr*load; end = begin+load;
    for (i = begin; ((i<end) && keepon); i++) {
      if (a[i] == x) {
        keepon = 0; position = i; thread=idthr;
      }
#pragma omp  flush(keepon,position)
    }  }

Univ. Politécnica de Cartagena

16

Ejemplos básicos

  if(idpro==0) { //Recibir datos
    if(position!=­1)
      printf("Encontrado en la posicion %di, por el thread %d de %d, 
            del proceso %d\n",position,thread,nthreads,idpro);
    for(i=1;i<nprocs;i++){
MPI_Recv(&position,1,MPI_INT,i,ENVIO_FINAL,MPI_COMM_WORLD,&estado);
MPI_Recv(&thread,1,MPI_INT,i,ENVIO_FINAL_THR,MPI_COMM_WORLD,&estado);
MPI_Recv(&nthreads,1,MPI_INT,i,ENVIO_FINAL_NTHR,MPI_COMM_WORLD,
   &estado);
      if(position!=­1)
        printf("Encontrado en la posicion %d,por el tread %d de %d, 
          del proceso %d\n",position+i*n/nprocs,thread,nthreads,i);
    }  
  }  else  {  //Enviar datos
MPI_Send(&position,1,MPI_INT,0,ENVIO_FINAL,MPI_COMM_WORLD);
MPI_Send(&thread,1,MPI_INT,0,ENVIO_FINAL_THR,MPI_COMM_WORLD);
MPI_Send(&nthreads,1,MPI_INT,0,ENVIO_FINAL_NTHR,MPI_COMM_WORLD);
  }  MPI_Finalize(); }

Univ. Politécnica de Cartagena

17

Ejemplos con operaciones
matriciales
●Multiplicación matriz­matriz:

N0 p0
N0 p1
N1 p0
N1 p1
N2 p0
N2 p1

N0 p0
N0 p1
N1 p0
N1 p1
N2 p0
N2 p1

 MPI

N0 p0
N0 p1
N1 p0
N1 p1
N2 p0
N2 p1

SPMD MPI+OpenMP
¿cuál es preferible?

N0
               MPI+OpenMP:
N1
menos memoria
menos comunicaciones
puede haber peor uso de memoria

N2

Univ. Politécnica de Cartagena

18

Ejemplos con operaciones
matriciales

Códigos de:

 matriz­vector
 
 matriz­matriz

Univ. Politécnica de Cartagena

19