grado en ingenierÍa de computadores departamento de...
Post on 06-Sep-2018
219 Views
Preview:
TRANSCRIPT
1
Prof. Dr. José Antonio de Frutos Redondo Curso 2013-2014
GRADO EN INGENIERÍA DE COMPUTADORES Arquitectura e Ingeniería de Computadores
Departamento de Automática Programación paralela MPI
© J. A. de Frutos Redondo 2013
Arq
uite
ctur
a e
Inge
nier
ía d
e C
ompu
tado
res
MPI 2
Programación con MPI
n Introducción n MPI mediante un ejemplo n Funciones MPI elementales n Comunicación colectiva n Agrupación de datos para comunicaciones
2
© J. A. de Frutos Redondo 2013
Arq
uite
ctur
a e
Inge
nier
ía d
e C
ompu
tado
res
MPI 3
Introducción
n Recordemos: n Desde el punto de vista hardware, estas máquinas:
n Están típicamente construidas por medio de computadores completos (procesador + memoria), incluyendo E/S.
n Interconexión entre ellos por medio de redes (estáticas o dinámicas).
n Comunicación por medio de operaciones explícitas de E/S. n Desde el punto de vista del modelo de programación:
n Acceso directo sólo a direcciones privadas (memoria local). n Comunicación por intercambio de mensajes.
n Existe intervención apreciable del sistema operativo. n Normalmente se programa por intermedio de librerías.
© J. A. de Frutos Redondo 2013
Arq
uite
ctur
a e
Inge
nier
ía d
e C
ompu
tado
res
MPI 4
n MPI significa “Message Passing Interface”. n Es un conjunto de funciones en C (o subrutinas en
FORTRAN) con las que se puede implementar un programa usando paso de mensajes. Nosotros usaremos C.
n MPI permite coordinar la ejecución del programa en múltiples procesadores con memoria distribuida.
n MPI está normalizada: n Cualquier programa escrito con esta librería funcionará sobre
cualquier máquina en que MPI esté instalado. n La normalización ha sido realizada por un equipo independiente
con participantes de la industria, de la universidad y laboratorios de investigación.
Introducción
3
© J. A. de Frutos Redondo 2013
Arq
uite
ctur
a e
Inge
nier
ía d
e C
ompu
tado
res
MPI 5
n En el comienzo de todo programa debemos especificar: # include “mpi.h”
n Con ello, disponemos de las funciones y constantes definidas en la librería.
n Todas las funciones y constantes de MPI comienzan con el prefijo MPI_. n En el caso de las funciones sigue una letra mayúscula y las
demás minúsculas: MPI_Init. n En el caso de constantes, son todas mayúsculas: MPI_CHAR.
n Todas las funciones devuelven un entero int salvo que se diga lo contrario.
Introducción
© J. A. de Frutos Redondo 2013
Arq
uite
ctur
a e
Inge
nier
ía d
e C
ompu
tado
res
MPI 6
n Antes de comenzar a usar la librería debemos llamar a la función MPI_Init. n Sólo debe hacerse una vez.
n Para terminar, debe llamarse a la MPI_Finalize. # include “mpi.h” ... main(int argc, char *argv[]) { ... /* Antes de este punto, no llamar a ninguna función MPI */
MPI_Init(&argc, &argv); ... MPI_Finalize(); /* Pasado este punto, no llamar a ninguna función MPI */ ... }
Introducción
4
© J. A. de Frutos Redondo 2013
Arq
uite
ctur
a e
Inge
nier
ía d
e C
ompu
tado
res
MPI 7
n Llamamos grupo de comunicación (communicator) a una familia de procesos que tienen permitido el intercambio de mensajes.
n Existe un grupo de comunicación por defecto, llamado MPI_COMM_WORLD. En él se encuentran todos los procesos en el momento de arranque.
n Dentro de cada grupo de comunicación, cada proceso se identifica por su rango (un identificador numérico) que se puede obtener con MPI_Comm_rank.
n El número total de procesos en un grupo de comunicación se puede obtener con MPI_Comm_size.
Introducción
© J. A. de Frutos Redondo 2013
Arq
uite
ctur
a e
Inge
nier
ía d
e C
ompu
tado
res
MPI 8
n Para enviar y recibir mensajes, utilizamos las funciones básicas: n MPI_Send
n MPI_Recv
n Los mensajes pueden sólo intercambiarse dentro del mismo grupo de comunicación.
n Cada mensaje enviado lleva una etiqueta identificadora (tag) que es única dentro de cada grupo de comunicación.
Introducción
5
© J. A. de Frutos Redondo 2013
Arq
uite
ctur
a e
Inge
nier
ía d
e C
ompu
tado
res
MPI 9
Un ejemplo sencillo de MPI
n Antes de poder ejecutar el ejemplo, cada máquina debe tener acceso a una copia. n O bien, todas ellas tienen acceso a la misma copia (disco
compartido).
n ¿Qué ocurre cuando lanzamos una ejecución? n Cada máquina comienza la ejecución de su copia. n Cada máquina realiza una ejecución independiente.
n Cada proceso puede ejecutar distintas zonas del programa si la lógica de éste depende de la identificación (rango) del proceso.
© J. A. de Frutos Redondo 2013
Arq
uite
ctur
a e
Inge
nier
ía d
e C
ompu
tado
res
MPI 10
Un ejemplo sencillo de MPI
/* saludos.c -- Envía un mensaje desde todos los procesos con rango != 0 al proceso de rango
0. Éste imprime los mensajes recibidos. */ #include <stdio.h> #include <string.h> #include "mpi.h" main(int argc, char* argv[]) { int mi_rango; /* rango de este proceso */ int p; /* número total de procesos */ int fuente; /* rango del remitente */ int dest; /* rango del destinatario */ int tag = 0; /* etiqueta para el mensaje */ char mensaje[256]; /* buffer para el mensaje */ MPI_Status status; /* status de return */
6
© J. A. de Frutos Redondo 2013
Arq
uite
ctur
a e
Inge
nier
ía d
e C
ompu
tado
res
MPI 11
Un ejemplo sencillo de MPI
MPI_Init(&argc, &argv); /* Arrancar MPI */ /* Hallar rango del proceso actual */ MPI_Comm_rank(MPI_COMM_WORLD, &mi_rango);
/* Número de procesos */ MPI_Comm_size(MPI_COMM_WORLD, &p); if (mi_rango != 0) { /* Crear mensaje */ sprintf(mensaje, “Saludos desde el proceso '%d'", mi_rango); dest = 0;
/* Usar strlen+1 para transmitir también '\0' */ MPI_Send(mensaje, strlen(mensaje)+1, MPI_CHAR, dest, tag,
MPI_COMM_WORLD); } else { /* mi_rango == 0 */ for (fuente = 1; fuente < p; fuente++) { MPI_Recv(mensaje, sizeof(mensaje), MPI_CHAR, fuente, tag, MPI_COMM_WORLD, &status); printf("%s\n", mensaje); }
} MPI_Finalize(); /* Finalizar MPI */ }
© J. A. de Frutos Redondo 2013
Arq
uite
ctur
a e
Inge
nier
ía d
e C
ompu
tado
res
MPI 12
Funciones elementales MPI
n La función de MPI_Send tiene el siguiente prototipo: MPI_Send(void *mensaje, /* ç */
int cuenta, /* ç */
MPI_Datatype tipodato, /* ç */
int destino, /* ç */
int etiqueta, /* ç */
MPI_Comm grupo_com); /* ç */
n Los tipos de datos son, por ejemplo: MPI_CHAR signed char
MPI_SHORT signed short int MPI_FLOAT float
.....
7
© J. A. de Frutos Redondo 2013
Arq
uite
ctur
a e
Inge
nier
ía d
e C
ompu
tado
res
MPI 13
Funciones elementales MPI
n La función de MPI_Recv tiene el siguiente prototipo: MPI_Recv(void *mensaje, /* è */
int cuenta, /* ç */
MPI_Datatype tipodato, /* ç */
int remitente, /* ç */
int etiqueta, /* ç */
MPI_Comm grupo_com, /* ç */
MPI_Status *status); /* è */
n Atención: el parámetro cuenta especifica el número máximo de elementos de tipo tipodato que caben en el buffer mensaje. n Si se envía un mensaje más largo, se produce un error de
desbordamiento.
© J. A. de Frutos Redondo 2013
Arq
uite
ctur
a e
Inge
nier
ía d
e C
ompu
tado
res
MPI 14
Funciones elementales MPI
n La variable de tipo MPI_Status tiene, al menos, los siguientes campos: MPI_SOURCE
MPI_TAG MPI_ERROR
n También contiene información acerca del tamaño del mensaje recibido, que se obtiene mediante la función: MPI_Get_count(MPI_Status *status, /* ç */
MPI_Datatype datatype, /* ç */
int *cuenta); /* è */
n Atención: cuenta obtendrá el número de elementos de tipo datatype (y no el número de bytes).
8
© J. A. de Frutos Redondo 2013
Arq
uite
ctur
a e
Inge
nier
ía d
e C
ompu
tado
res
MPI 15
Funciones elementales MPI
n Hemos usado también las funciones MPI_Comm_rank y MPI_Comm_size:
MPI_Comm_rank(MPI_Comm comunicador, /* ç */
int *rango); /* è */
n Devuelve al proceso que la llama (en la variable rango) su rango dentro del comunicador comunicador.
n Como ya veremos, el comunicador es una estructura que, dicho de modo sencillo, agrupa los procesos que pueden intercambiar mensajes.
MPI_Comm_size(MPI_Comm comunicador, /* ç */
int *tamanyo); /* è */
n Devuelve en la variable tamanyo el número de procesos enganchados al comunicador comunicador.
© J. A. de Frutos Redondo 2013
Arq
uite
ctur
a e
Inge
nier
ía d
e C
ompu
tado
res
MPI 16
Comunicación colectiva
n Función MPI_Bcast y tiene el siguiente prototipo:
MPI_Bcast(void *mensaje, /* çè */
int cuenta, /* ç */
MPI_Datatype tipodato, /* ç */
int raiz, /* ç */
MPI_Comm grupo_com); /* ç */
9
© J. A. de Frutos Redondo 2013
Arq
uite
ctur
a e
Inge
nier
ía d
e C
ompu
tado
res
MPI 17
Comunicación colectiva
n La llamada a la función MPI_Bcast puede resultar en n recepción de datos, si el rango del proceso es distinto de raiz. n envío de datos, si el rango del proceso es igual a raiz.
n El valor de tipodato y cuenta ha de ser igual para todos. n Los procesos afectados serán todos los que se encuentren
en el grupo de comunicaciones grupo_com. n El sistema MPI garantiza que si un proceso difunde varios
mensajes (varias llamadas a MPI_Bcast), éstos serán recibidos por los demás procesos en el mismo orden en que fueron emitidos.
© J. A. de Frutos Redondo 2013
Arq
uite
ctur
a e
Inge
nier
ía d
e C
ompu
tado
res
MPI 18
Ejemplo de integración con trapecios
/* trap.c – Integración mediante trapecios. Algoritmo: 1. Cada proceso se autoasigna su propio intervalo de integración. 2. Cada proceso integra f(x) en su propio intervalo con el método de los trapecios.
3a. Cada proceso con rango != 0 envía su resultado al proceso 0. 3b. El proceso 0 suma los resultados de los cálculos realizados por los demás e imprime el resultado.
*/ #include <stdio.h> #include "mpi.h" /* Prototipo de la función que integra */ float Trap(float local_a, float local_b, int local_n, float h);
10
© J. A. de Frutos Redondo 2013
Arq
uite
ctur
a e
Inge
nier
ía d
e C
ompu
tado
res
MPI 19
Ejemplo de integración con trapecios
main(int argc, char *argv[]) { int mi_rango; /* El rango de mi proceso */ int p; /* Número total de procesos */
float a = 0.0; /* Extremo izquierdo */ float b = 1.0; /* Extremo derecho */ int n = 1024; /* Número de trapecios */ float h; /* Base de cada trapecio */ float local_a; /* Extremo izdo. de mi proceso */ float local_b; /* Extermo dcho. de mi proceso */
int local_n; /* Número de trapecios para mi cálculo */ float integral; /* Resultado de la integral en mi intervalo */ float total; /* Integral total */ int fuente; /* Proceso que remite el resultado */ int dest = 0; /* Todos los resultados van al proceso 0 */ int tag = 0;
MPI_Status status; MPI_Init(&argc, &argv); /* Arrancamos MPI */ MPI_Comm_rank(MPI_COMM_WORLD, &mi_rango); /* Obtengo mi propio rango */ MPI_Comm_size(MPI_COMM_WORLD, &p); /* Obtengo nº total de procesos */
© J. A. de Frutos Redondo 2013
Arq
uite
ctur
a e
Inge
nier
ía d
e C
ompu
tado
res
MPI 20
Ejemplo de integración con trapecios
h = (b-a)/n; /* h es el mismo para todos los procesos */ local_n = n/p; /* igual que el número de trapecios */
/* La longitud del intervalo de integración de cada proceso es igual a local_n*h. Así pues, mi intervalo empieza y acaba en: */
local_a = a + mi_rango*local_n*h; local_b = local_a + local_n*h; /* Calculo la integral en mi intervalo */ integral = Trap(local_a, local_b, local_n, h);
11
© J. A. de Frutos Redondo 2013
Arq
uite
ctur
a e
Inge
nier
ía d
e C
ompu
tado
res
MPI 21
Ejemplo de integración con trapecios
if (mi_rango == 0) { /* Sumo los cálculos de cada proceso, que me envían los demás */ total = integral;
for (fuente = 1; fuente < p; fuente++) { MPI_Recv(&integral, 1, MPI_FLOAT, fuente, tag, MPI_COMM_WORLD, &status); total = total + integral; } } else { /* Envío mi resultado al proceso 0 */
MPI_Send(&integral, 1, MPI_FLOAT, dest, tag, MPI_COMM_WORLD); } if (mi_rango == 0) { /* Imprimo resultados */ printf(“Con n = %d trapecios, la integral de f(x) ", n);
printf(“desde %f a %f = %f\n", a, b, total); } /* Cerrar MPI */ MPI_Finalize(); }
© J. A. de Frutos Redondo 2013
Arq
uite
ctur
a e
Inge
nier
ía d
e C
ompu
tado
res
MPI 22
Ejemplo de integración con trapecios
float Trap(float local_a, /* ç */ float local_b, /* ç */ int local_n, /* ç */ float h) { /* ç */ float integral; /* Para almacenar el resultado */ float x; int i; float f(float x); /* Función a integrar */ integral = (f(local_a) + f(local_b))/2.0; x = local_a; for (i = 1; i <= local_n-1; i++) { x = x + h; integral = integral + f(x); } integral = integral*h; return integral; }
12
© J. A. de Frutos Redondo 2013
Arq
uite
ctur
a e
Inge
nier
ía d
e C
ompu
tado
res
MPI 23
Ejemplo de integración con trapecios
/* Función que vamos a integrar. Metemos el código que corresponda a la función que deseamos integrar
*/ float f(float x) { float return_val; /* Calculamos f(x) y lo almacenamos en return_val */ ... return return_val; }
© J. A. de Frutos Redondo 2013
Arq
uite
ctur
a e
Inge
nier
ía d
e C
ompu
tado
res
MPI 24
Comunicación colectiva
n El programa de la integración con trapecios tiene dos fases: n Cálculo de las integrales parciales n Suma de los resultados
n La primera fase está equilibradamente distribuida entre los distintos procesos.
n La fase de suma la realiza exclusivamente el proceso 0. n Podríamos redistribuir el trabajo de suma entre los distintos
procesos para equilibrar este trabajo.
13
© J. A. de Frutos Redondo 2013
Arq
uite
ctur
a e
Inge
nier
ía d
e C
ompu
tado
res
MPI 25
Comunicación colectiva
n Para resolver este problema, MPI proporciona la función MPI_Reduce con el siguiente prototipo: MPI_Reduce(void *operando, /* ç */
void *resultado, /* è */
int cuenta, /* ç */
MPI_Datatype tipodato, /* ç */
MPI_Op operacion, /* ç */
int raiz, /* ç */
MPI_Comm grupo_com); /* ç */
n MPI_Reduce combina los operandos almacenados en operando usando la operación operacion y almacena el resultado en resultado en el proceso raiz. Tanto operando como resultado se refieren a cuenta elementos de tipo tipodato.
© J. A. de Frutos Redondo 2013
Arq
uite
ctur
a e
Inge
nier
ía d
e C
ompu
tado
res
MPI 26
Comunicación colectiva
n MPI_Reduce ha de ser llamado en todos los procesos del grupo de comunicación grupo_com y cuenta, tipodato y operacion han de valer lo mismo en todos los procesos.
n El argumento operacion puede valer n MPI_SUM
n MPI_PROD
n MPI_MAX
n MPI_MIN
n ...
n Obsérvese que la variable resultado sólo tiene sentido en el proceso raiz. Aun así, los demás procesos también han de especificarla.
14
© J. A. de Frutos Redondo 2013
Arq
uite
ctur
a e
Inge
nier
ía d
e C
ompu
tado
res
MPI 27
Comunicación colectiva
n Podemos, entonces, sustituir if (mi_rango == 0) { /* Sumo los cálculos de cada proceso, que me envían los demás */ total = integral; for (fuente = 1; fuente < p; fuente++) { MPI_Recv(&integral, 1, MPI_FLOAT, fuente, tag, MPI_COMM_WORLD, &status); total = total + integral; } } else { /* Envío mi resultado al proceso 0 */ MPI_Send(&integral, 1, MPI_FLOAT, dest, tag, MPI_COMM_WORLD); }
por
MPI_Reduce(&integral, &total, 1, MPI_FLOAT, MPI_SUM, 0, MPI_COMM_WORLD);
© J. A. de Frutos Redondo 2013
Arq
uite
ctur
a e
Inge
nier
ía d
e C
ompu
tado
res
MPI 28
Comunicación colectiva
n En algunos casos nos interesa que la reducción se efectúa en todos los procesos. Para ello existe la función MPI_Allreduce cuyo prototipo es:
MPI_Allreduce(void *operando, /* ç */
void *resultado, /* è */
int cuenta, /* ç */
MPI_Datatype tipodato, /* ç */
MPI_Op operacion, /* ç */
MPI_Comm grupo_com); /* ç */
n Se usa exactamente igual que MPI_Reduce, pero el resultado de la reducción se acumula en resultado en todos los procesos pertenecientes al grupo de comunicación grupo_com. Por ello no es necesario el parámetro raiz, como en el otro caso.
15
© J. A. de Frutos Redondo 2013
Arq
uite
ctur
a e
Inge
nier
ía d
e C
ompu
tado
res
MPI 29
Comunicación colectiva
n Las barreras están directamente implementadas en MPI: MPI_Barrier(MPI_Comm grupo_com); /* ç */
n Cada proceso del grupo de comunicación grupo_com se quedará bloqueado hasta que todos ellos hayan llamado a esta función.
n Cuando el último de ellos la llame, todos se desbloquean simultáneamente.
n Es un mecanismo de sincronización.
© J. A. de Frutos Redondo 2013
Arq
uite
ctur
a e
Inge
nier
ía d
e C
ompu
tado
res
MPI 30
Comunicación colectiva
n Otras funciones de comunicación colectiva son las siguientes: MPI_Gather(void *buffer_envio, /* ç */
int cuenta_envio, /* ç */
MPI_Datatype tipo_envio, /* ç */
void *buffer_recepcion, /* è */
int cuenta_recepcion, /* ç */
MPI_Datatype tipo_recepcion, /* ç */
int raiz, /* ç */
MPI_Comm grupo_com); /* ç */
n Cada proceso del grupo de comunicación grupo_com envía los contenidos de buffer_envio al proceso raiz.
n El proceso raiz concatena los datos recibidos por orden de rango en buffer_recepcion, es decir, los datos del proceso 0, a continuación los del 1, etc.
16
© J. A. de Frutos Redondo 2013
Arq
uite
ctur
a e
Inge
nier
ía d
e C
ompu
tado
res
MPI 31
Comunicación colectiva
n Los argumentos de recepción sólo son significativos en el proceso raiz.
n El argumento cuenta_recepcion indica el número de items recibidos de cada proceso (no el total).
© J. A. de Frutos Redondo 2013
Arq
uite
ctur
a e
Inge
nier
ía d
e C
ompu
tado
res
MPI 32
Comunicación colectiva
MPI_Scatter(void *buffer_envio, /* ç */
int cuenta_envio, /* ç */
MPI_Datatype tipo_envio, /* ç */
void *buffer_recepcion, /* è */
int cuenta_recepcion, /* ç */
MPI_Datatype tipo_recepcion, /* ç */
int raiz, /* ç */
MPI_Comm grupo_com); /* ç */
n El proceso con rango raiz distribuye los contenidos del buffer buffer_envio en tantos segmentos como procesos haya, cada uno con un tamaño de cuenta_envio items.
n Los argumentos de envío son significativos sólo en el proceso raiz.
17
© J. A. de Frutos Redondo 2013
Arq
uite
ctur
a e
Inge
nier
ía d
e C
ompu
tado
res
MPI 33
Comunicación colectiva
MPI_Allgather(void *buffer_envio, /* ç */ int cuenta_envio, /* ç */
MPI_Datatype tipo_envio, /* ç */
void *buffer_recepcion, /* è */
int cuenta_recepcion, /* ç */
MPI_Datatype tipo_recepcion, /* ç */
MPI_Comm grupo_com); /* ç */
n Cada proceso del grupo de comunicación grupo_com envía los contenidos de buffer_envio a todos los demás procesos.
n El efecto es equivalente a llamar a MPI_Gather tantas veces como procesos haya, actuando sucesivamente cada uno de ellos como raiz.
© J. A. de Frutos Redondo 2013
Arq
uite
ctur
a e
Inge
nier
ía d
e C
ompu
tado
res
MPI 34
Agrupación de datos
n Enviar mensajes es una operación costosa. n Hay que tratar de enviar el mínimo número posible.
n La solución obvia es agrupar los mensajes. n Existen tres mecanismos para agrupar mensajes:
n Parámetro cuenta. n Tipos de datos derivados. n Las rutinas MPI_Pack/MPI_Unpack.
18
© J. A. de Frutos Redondo 2013
Arq
uite
ctur
a e
Inge
nier
ía d
e C
ompu
tado
res
MPI 35
Agrupación de datos
n Recordemos que las funciones MPI_Send, MPI_Receive, MPI_Bcast, MPI_Reduce tienen todas el parámetro cuenta y el parámetro tipodato.
n Con ellos, el usuario puede agrupar datos que sean del mismo tipo básico en un solo mensaje.
n Condición imprescindible: n los datos han de estar almacenados en memoria contigua. n Esto es útil para los vectores o matrices.
© J. A. de Frutos Redondo 2013
Arq
uite
ctur
a e
Inge
nier
ía d
e C
ompu
tado
res
MPI 36
Agrupación de datos
n Ejemplo: enviar la segunda mitad de un vector de 100 flotantes desde el proceso 0 al 1.
float vector[100]; MPI_Status status; int p; int mi_rango; ... /* Inicializar vector y enviar */ if (mi_rango == 0) { ... MPI_Send(vector+50, 50, MPI_FLOAT, 1, 0, MPI_COMM_WORLD); } else if (mi_rango == 1) { MPI_Recv(vector+50, 50, MPI_FLOAT, 0, 0, MPI_COMM_WORLD,
&status); ... }
19
© J. A. de Frutos Redondo 2013
Arq
uite
ctur
a e
Inge
nier
ía d
e C
ompu
tado
res
MPI 37
Agrupación de datos
n Si los datos no son de igual tipo, hemos de construir tipos derivados a partir de los primitivos.
n Un tipo MPI derivado es una sucesión de n pares {(t0, d0), (t1, d1), ..., (tn−1,dn−1)}
donde cada ti es un tipo básico y cada di es un desplazamiento en bytes.
n Un ejemplo podría ser: {(MPI_FLOAT, 0),(MPI_FLOAT, 16),(MPI_INT, 24)}
© J. A. de Frutos Redondo 2013
Arq
uite
ctur
a e
Inge
nier
ía d
e C
ompu
tado
res
MPI 38
Agrupación de datos
n La función para construir un tipo nuevo es: MPI_Type_struct(int cuenta, /* ç */
int long_bloque[], /* ç */
MPI_Aint desplazamiento[], /* ç */
MPI_Datatype lista_de_tipos[], /* ç */
MPI_Datatype *nuevo_tipo); /* è */
n El parámetro cuenta es el número de elementos del tipo derivado y el tamaño de los vectores long_bloque, desplazamiento y lista_de_tipos.
n El vector lista_de_tipos contiene el tipo de dato MPI para cada entrada.
n El vector desplazamiento contiene el desplazamiento con respecto al comienzo del mensaje de cada entrada.
n El vector long_bloque indica cuántos elementos de cada tipo hay en cada entrada.
20
© J. A. de Frutos Redondo 2013
Arq
uite
ctur
a e
Inge
nier
ía d
e C
ompu
tado
res
MPI 39
Agrupación de datos
n Ejemplo de construir un nuevo tipo. n Queremos construir un mensaje con las variables
float a; float b; int n;
int long_bloque[3]; MPI_Aint desplazamientos[3]; MPI_Datatype lista_de_tipos[3];
/* Para los cálculos de direcciones */ MPI_Aint start_address; MPI_Aint address; /* Nuevo tipo */
MPI_Datatype nuevo_tipo;
© J. A. de Frutos Redondo 2013
Arq
uite
ctur
a e
Inge
nier
ía d
e C
ompu
tado
res
MPI 40
Agrupación de datos
/* Nuestros datos son de un solo elemento cada uno */ long_bloque[0] = long_bloque[1] = long_bloque[2] = 1; /* Nuestras variables son dos flotantes y un entero */ typelist[0] = typelist[1] = MPI_FLOAT; typelist[2] = MPI_INT;
/* El primer elemento a lo ponemos a desplazamiento 0 */ desplazamientos[0] = 0;
/* Calculamos los otros desplazamientos respecto de a */ MPI_Address(&a, &start_address); MPI_Address(&b, &address); desplazamientos[1] = address - start_address; MPI_Address(&n, &address); desplazamientos[2] = address - start_address;
21
© J. A. de Frutos Redondo 2013
Arq
uite
ctur
a e
Inge
nier
ía d
e C
ompu
tado
res
MPI 41
Agrupación de datos
/* Construimos el tipo derivado */ MPI_Type_struct(3, long_bloque, desplazamientos, lista_de_tipos, &nuevo_tipo); /* Informamos al sistema del nuevo tipo de datos */ MPI_Type_commit(&nuevo_tipo);
© J. A. de Frutos Redondo 2013
Arq
uite
ctur
a e
Inge
nier
ía d
e C
ompu
tado
res
MPI 42
Agrupación de datos
n Observemos dos funciones que hemos introducido: MPI_Address(void *variable, /* ç */
MPI_Aint *direccion); /* è */
n En principio es equivalente a la sentencia: direccion = &variable;
n pero nos permite asegurar la portabilidad.
MPI_Type_commit(MPI_Datatype *nuevo_tipo); /* çè */
n Mediante este mecanismo, el sistema realiza unos cambios internos en la representación de nuevo_tipo para mejorar el rendimiento.
n Estos cambios no son necesarios si nuevo_tipo es usado solo como paso intermedio para construir un tipo más complicado. Por eso esta función va aparte.
22
© J. A. de Frutos Redondo 2013
Arq
uite
ctur
a e
Inge
nier
ía d
e C
ompu
tado
res
MPI 43
Agrupación de datos
n Tenemos otros constructores más sencillos: MPI_Type_contiguous(int cuenta, /* ç */
MPI_Datatype tipo_viejo, /* ç */
MPI_Datatype *tipo_nuevo); /* è */
n El nuevo tipo consiste en cuenta elementos contiguos de un vector de elementos de tipo tipo_viejo.
© J. A. de Frutos Redondo 2013
Arq
uite
ctur
a e
Inge
nier
ía d
e C
ompu
tado
res
MPI 44
Agrupación de datos
n Ejemplo: queremos mandar una fila una matriz de flotantes de tamaño 10×10:
float A[10][10]; MPI_Datatype tipo_fila_10; ... MPI_Type_contiguous(10, MPI_FLOAT, &tipo_fila_10); MPI_Type_commit(&tipo_fila_10); if (mi_rango == 0) { MPI_Send(&(A[2][0]), 1, tipo_fila_10, 1, 0, MPI_COMM_WORLD); } else { /* mi_rango == 1 */ MPI_Recv(&(A[2][0]), 1, tipo_fila_10, 0, 0, MPI_COMM_WORLD, &status); }
23
© J. A. de Frutos Redondo 2013
Arq
uite
ctur
a e
Inge
nier
ía d
e C
ompu
tado
res
MPI 45
Agrupación de datos
n Otro constructor: MPI_Type_vector(int cuenta, /* ç */
int long_bloque, /* ç */
int espaciado, /* ç */
MPI_Datatype tipo_elem, /* ç */
MPI_Datatype *tipo_nuevo); /* è */
n El nuevo tipo consiste en elementos igualmente espaciados de un vector.
n El parámetro cuenta es el número de elementos del nuevo tipo, long_bloque es el número de entradas en cada elemento, espaciado es el número de elementos de tipo tipo_elem entre sucesivos elementos del tipo tipo_nuevo.
© J. A. de Frutos Redondo 2013
Arq
uite
ctur
a e
Inge
nier
ía d
e C
ompu
tado
res
MPI 46
Agrupación de datos
n Ejemplo: queremos mandar una columna de una matriz de flotantes de tamaño 10×10:
float A[10][10]; MPI_Datatype tipo_columna_10; ... MPI_Type_vector(10, 1, 10, MPI_FLOAT, &tipo_columna_10); MPI_Type_commit(&tipo_columna_10); if (mi_rango == 0) { MPI_Send(&(A[0][2]), 1, tipo_columna_10, 1, 0, MPI_COMM_WORLD); } else { /* mi_rango == 1 */ MPI_Recv(&(A[0][2]), 1, tipo_columna_10, 0, 0, MPI_COMM_WORLD, &status);
}
24
© J. A. de Frutos Redondo 2013
Arq
uite
ctur
a e
Inge
nier
ía d
e C
ompu
tado
res
MPI 47
Agrupación de datos
n Otro constructor más: MPI_Type_indexed(int cuenta, /* ç */
int long_bloques[], /* ç */
int desplazamientos[], /* ç */
MPI_Datatype tipo_elem, /* ç */
MPI_Datatype *tipo_nuevo); /* è */
n El nuevo tipo consiste en cuenta elementos de tipo tipo_elem. n El i-ésimo elemento consta de long_bloques[i] entradas y está
desplazado desplazamientos[i] elementos de tipo tipo_elem respecto del principio.
© J. A. de Frutos Redondo 2013
Arq
uite
ctur
a e
Inge
nier
ía d
e C
ompu
tado
res
MPI 48
Agrupación de datos
n Ejemplo: queremos mandar la porción triangular superior de una matriz de n×n elementos:
float A[n][n]; /* Matriz completa */ float T[n][n]; /* Triángulo superior */ int desplazamientos[n]; int long_bloques[n]; MPI_Datatype tipo_triang; ... for (i = 0; i < n; i++) { long_bloques[i] = n - i; desplazamientos[i] = (n + 1)*i; } MPI_Type_indexed(n, long_bloques, desplazamientos,
MPI_FLOAT, &tipo_triang); MPI_Type_commit(&index_mpi_t); /* ... Se envía como antes ... */
25
© J. A. de Frutos Redondo 2013
Arq
uite
ctur
a e
Inge
nier
ía d
e C
ompu
tado
res
MPI 49
Agrupación de datos
n Por último, podemos empaquetar los datos explícitamente y desempaquetarlos al recibir. Tenemos:
MPI_Pack(void *paquete, /* ç */
int cuenta, /* ç */
MPI_Datatype tipo_dato, /* ç */
void *buffer, /* è */
int tamanyo_buffer, /* ç */
int *posicion, /* çè */
MPI_Comm grupo_com); /* ç */
MPI_Unpack(void *buffer, /* ç */
int tamanyo_buffer, /* ç */
int *posicion, /* çè */
void *desempaquetado, /* è */
int cuenta, /* ç */
MPI_Datatype tipo_dato, /* ç */
MPI_Comm grupo_com); /* ç */
© J. A. de Frutos Redondo 2013
Arq
uite
ctur
a e
Inge
nier
ía d
e C
ompu
tado
res
MPI 50
Agrupación de datos
n Veamos con un ejemplo su uso: float a; float b; int n; char buffer[100]; int posicion = 0;
if (mi_rango == 0) { /* posicion se incre- */ MPI_Pack(&a, 1, MPI_FLOAT, buffer, 100, /* menta hasta la si- */ &posicion, MPI_COMM_WORLD); /* guiente posición */ /* libre del buffer. */ MPI_Pack(&b, 1, MPI_FLOAT, buffer, 100, /* posicion se incre- */ &posicion, MPI_COMM_WORLD); /* menta de nuevo. */ MPI_Pack(n, 1, MPI_INT, buffer, 100, &posicion, MPI_COMM_WORLD);
26
© J. A. de Frutos Redondo 2013
Arq
uite
ctur
a e
Inge
nier
ía d
e C
ompu
tado
res
MPI 51
Agrupación de datos
... /* Ahora difundimos el contenido del buffer */ MPI_Bcast(buffer, 100, MPI_PACKED, 0, MPI_COMM_WORLD); } else { MPI_Bcast(buffer, 100, MPI_PACKED, 0, MPI_COMM_WORLD); /* Desempaquetamos */ MPI_Unpack(buffer, 100, &posicion, &a, 1, /* posicion se in- */ MPI_FLOAT, MPI_COMM_WORLD); /* menta también de */ /* manera automática */ MPI_Unpack(buffer, 100, &posicion, &b, 1, MPI_FLOAT, MPI_COMM_WORLD); MPI_Unpack(buffer, 100, &position, &n, 1, MPI_INT, MPI_COMM_WORLD); }
© J. A. de Frutos Redondo 2013
Arq
uite
ctur
a e
Inge
nier
ía d
e C
ompu
tado
res
MPI 52
Ejemplo del algoritmo de Gauss-Seidel
/* Integración de un sistema por el algoritmo de Gauss-Seidel. Algoritmo: 1. Se realiza una división por bloques. El número de procesos ha de ser un divisor de la constante MATRIZ.
2. Cada proceso inicializa su bloque. A cada bloque se le añaden dos filas “fantasma” para intercambiar datos con los procesos asociados a los bloques superior e inferior.
3a. Cada proceso realiza el cómputo del promedio, intercambiando los resultados con sus vecinos.
3b. El proceso 0 “reduce” las diferencias de todos, para ver si se ha de terminar. En tal caso, difunde el valor done=0 a todos los demás.
4. Cada proceso imprime su bloque en un fichero. */
27
© J. A. de Frutos Redondo 2013
Arq
uite
ctur
a e
Inge
nier
ía d
e C
ompu
tado
res
MPI 53
Ejemplo del algoritmo de Gauss-Seidel
# include <stdlib.h> # include <stdio.h> # include <math.h>
# include "mpi.h" # define MATRIZ (128) # define LAMBDA 0.2 # define LADO_I 30 # define LADO_D 30
# define ARRIBA 50 # define ABAJO 50 # define INTERNO 15 # define FILA 1 # define TOL 0.001
© J. A. de Frutos Redondo 2013
Arq
uite
ctur
a e
Inge
nier
ía d
e C
ompu
tado
res
MPI 54
Ejemplo del algoritmo de Gauss-Seidel
void Resuelve(float myA[][MATRIZ+2], int pid, int nprocs) { int i,j, n1 = 2 + MATRIZ, n2 = 2 + MATRIZ/nprocs, done = 0; float temp, diff, mydiff = 0;
MPI_Status status; while (!done) { mydiff = 0; if (pid != 0) MPI_Send(&myA[1][0], n1, MPI_FLOAT, pid - 1, FILA, MPI_COMM_WORLD);
if (pid != nprocs-1) MPI_Send(&myA[n2 - 2][0], n1, MPI_FLOAT, pid + 1, FILA, MPI_COMM_WORLD); if (pid != 0) MPI_Recv(&myA[0][0], n1, MPI_FLOAT, pid - 1, FILA, MPI_COMM_WORLD, &status);
if (pid != nprocs-1) MPI_Recv(&myA[n2 - 1][0], n1, MPI_FLOAT, pid + 1, FILA, MPI_COMM_WORLD, &status);
28
© J. A. de Frutos Redondo 2013
Arq
uite
ctur
a e
Inge
nier
ía d
e C
ompu
tado
res
MPI 55
Ejemplo del algoritmo de Gauss-Seidel
for (i = 1; i < n2 - 1; i++) { for (j = 1; j < n1 - 1; j++) { temp = myA[i][j];
myA[i][j] = LAMBDA*(myA[i][j] + myA[i][j-1] + myA[i-1][j] + myA[i][j+1] + myA[i+1][j]); mydiff += fabs(myA[i][j] - temp); } }
MPI_Reduce(&mydiff, &diff, 1, MPI_FLOAT, MPI_SUM, 0, MPI_COMM_WORLD); if (pid == 0) { if (diff/(MATRIZ*MATRIZ) < TOL) { done = 1; }
} MPI_Bcast(&done, 1, MPI_INT, 0, MPI_COMM_WORLD); } }
© J. A. de Frutos Redondo 2013
Arq
uite
ctur
a e
Inge
nier
ía d
e C
ompu
tado
res
MPI 56
Ejemplo del algoritmo de Gauss-Seidel
void Inicializa(float myA[][MATRIZ+2], int pid, int nprocs) { int i,j; int n1 = 2 + MATRIZ, n2 = 2 + MATRIZ/nprocs;
for (i = 0; i < n2; i++) { for (j = 0; j < n1; j++) myA[i][j] = INTERNO; }
for (i = 0; i < n2; i++) { myA[i][0] = LADO_I; myA[i][n1 - 1] = LADO_D; }
29
© J. A. de Frutos Redondo 2013
Arq
uite
ctur
a e
Inge
nier
ía d
e C
ompu
tado
res
MPI 57
Ejemplo del algoritmo de Gauss-Seidel
if (pid == 0) { for (j = 0; j < n1; j++) { myA[0][j] = ARRIBA;
} } if (pid == nprocs - 1) { for (j = 0; j < n1; j++) { myA[n2 - 1][j] = ABAJO;
} } }
© J. A. de Frutos Redondo 2013
Arq
uite
ctur
a e
Inge
nier
ía d
e C
ompu
tado
res
MPI 58
Ejemplo del algoritmo de Gauss-Seidel
void PrintData(float myA[][MATRIZ+2], int pid, int nprocs) { int i, j;
int n1 = 2 + MATRIZ; int n2 = 2 + MATRIZ/nprocs; FILE *fpc = NULL; char name[256] = ""; sprintf(name, "out%d.dat", pid);
if ((fpc = fopen(name, "w")) != NULL) { for (i = 1; i < n2 - 1 ; i++) { for (j = 1; j < n1 - 1; j++) fprintf(fpc, "%.3f ", myA[i][j]);
fprintf(fpc, "\n"); } fclose(fpc); } }
30
© J. A. de Frutos Redondo 2013
Arq
uite
ctur
a e
Inge
nier
ía d
e C
ompu
tado
res
MPI 59
Ejemplo del algoritmo de Gauss-Seidel
main(int argc, char *argv[]) { float *myA = NULL; /* Matriz en este proceso */ int pid = 0; /* Rango del proceso */
int nprocs = 0; /* Número de procesos usados */ MPI_Init(&argc, &argv); MPI_Comm_rank(MPI_COMM_WORLD, &pid); MPI_Comm_size(MPI_COMM_WORLD, &nprocs); myA = (float *)malloc(sizeof(float)*(2 + MATRIZ)*(2 + MATRIZ/nprocs));
Inicializa(myA, pid, nprocs); /* Inicializamos la matriz */ MPI_Barrier(MPI_COMM_WORLD); /* Espera que se inicialicen todos */ Resuelve(myA, pid, nprocs); /* Resolvemos */ MPI_Barrier(MPI_COMM_WORLD); /* Espera que acaben todos */ PrintData(myA, pid, nprocs); /* Imprimimos los resultados en ficheros */ MPI_Finalize();
return 0; }
© J. A. de Frutos Redondo 2013
Arq
uite
ctur
a e
Inge
nier
ía d
e C
ompu
tado
res
MPI 60
Resultado de la ejecución serie
Matriz de 32 × 32 puntos
31
© J. A. de Frutos Redondo 2013
Arq
uite
ctur
a e
Inge
nier
ía d
e C
ompu
tado
res
MPI 61
Resultado usando MPI
Matriz de 32 × 32 puntos
top related