LP Mpi

Laboratorio de Paralelismo
IF - EHU
. 3 .

PROGRAMACIN DE SISTEMAS DE
MEMORIA DISTRIBUIDA:
MPI
IF - EHU
1. Introduccin.
2. Funciones MPI bsicas.
3. Otros modos de envo y recepcin.
4. Comunicacin en grupo.
5. Tipos de datos derivados.
6. Comunicadores y topologas.
7. Entrada/salida paralela (introd.).
8. Performance, debugging, profiling...

ndice
IF - EHU
MPI
3 3
Paralelizar una aplicacin para que se ejecute en un
sistema de memoria compartida SMP no es muy
complejo.
El uso de variables compartidas facilita la
comunicacin entre procesos, aunque implica:
analizar detalladamente el tipo de variables.
sincronizar correctamente el acceso a las
variables compartidas.
Sin embargo, el nmero de procesadores de un
sistema SMP no suele ser muy grande, por lo que no
es fcil conseguir altos niveles de paralelismo.
Introduccin
IF - EHU
MPI
4 3
Es relativamente sencillo conseguir una mquina
paralela tipo cluster con muchos procesadores,
uniendo P mquinas independientes mediante una
red de conexin estndar.
Por ejemplo, nosotros vamos a utilizar una mquina
de 32 + 3 nodos (32 + 3x4 = 44 pr.), unidos
mediante una red gigabit ethernet.
No es una mquina de alto rendimiento, pero es
barata y sencilla de ampliar (en nodos de clculo y
en comunicacin).
Introduccin
IF - EHU
MPI
5 3
Sin embargo, programar aplicaciones para sistemas
de memoria distribuida es ms complejo.
Recuerda:
la memoria de cada procesador es de uso
privado, por lo que todas las variables son, por
definicin, privadas.
la comunicacin entre procesos debe hacerse a
travs de paso explcito de mensajes.
la red de comunicacin juega un papel
importante en el rendimiento del sistema.
Introduccin
IF - EHU
MPI
6 3
Diferentes alternativas para programar aplicaciones:
utilizar lenguajes diseados especficamente para
sistemas paralelos (OCCAM).
ampliar la sintaxis de un lenguaje estndar para
gestionar el paso de mensajes (Fortran M).
utilizar un lenguaje estndar y una librera de
funciones de comunicacin.
Introduccin
IF - EHU
MPI
7 3
El estndar actual de programacin de los sistemas
de memoria distribuida, mediante paso de
mensajes, es MPI (message-passing interface).

PVM MPI 1.0 (94) MPI 2.0 (97)
Necesitamos:
- un mtodo para crear procesos: esttico / dinmico.
- un mtodo para enviar y recibir mensajes,
punto a punto y de manera global.
Introduccin
IF - EHU
MPI
8 3
MPI es, bsicamente, una librera (grande) de
funciones de comunicacin para el envo y
recepcin de mensajes entre procesos.
Para Fortran y C.
Se busca: portabilidad, eficiencia...
El objetivo de MPI es explicitar la comunicacin entre
procesos, es decir:
> el movimiento de datos entre procesadores
> la sincronizacin de procesos
Introduccin
IF - EHU
MPI
9 3
El modelo de paralelismo que implementa MPI es
SPMD (Single Program Multiple Data).
if (pid==1) ENVIAR_a_pid2
else if (pid==2) RECIBIR_de_pid1

Recuerda que cada proceso dispone de su propio espacio
de direcciones.
Tambin se puede trabajar con un modelo MPMD
(Multiple Program Multiple Data): se ejecutan
programas diferentes en los nodos.
Introduccin
IF - EHU
MPI
10 3
MPI gestiona los procesos (nmero y asignacin) de
manera esttica (MPI2 permite gestin dinmica de
procesos).
La comunicacin entre procesos puede hacerse de
formas muy diferentes.
Elegiremos una determinada estrategia en funcin de
la longitud de los mensajes, de la estructura del
programa...
Introduccin
IF - EHU
MPI
11 3
En todo caso, ten en cuenta que la eficiencia en la
comunicacin va a ser determinante en el
rendimiento del sistema paralelo, sobre todo en
aquellas aplicaciones en las que la comunicacin
juega un papel importante (paralelismo de grano
medio / fino).
Adems de implementaciones especficas, dos imple-
mentaciones libres de uso muy extendido: LAM y
MPICH.
Nosotros vamos a usar MPICH.
Introduccin
IF - EHU
MPI
12 3
gigabit ethernet
g000002.gi.ehu.es
nodo00
nodoxx
Recuerda: ethernet
- switch / conmutacin de paquetes
- formato de paquetes

- direcciones IP: 32 bits (4 8)
- direcciones del NIC (MAC, 48 bits)
check datos tipo @orig @dest cabecera
4 bytes < 1,5 Kbytes 2 bytes 6 bytes 6 bytes 8 bytes
Introduccin: el cluster
IF - EHU
MPI
13 3
Para poder ejecutar MPI en el cluster:
1. Generar fichero de claves para ssh
> ssh-keygen t rsa
(pasar al directorio .ssh)
> cp id_rsa.pub authorized_keys
> chmod go-rw authorized_keys
(salir del directorio .ssh)
Entrar la primera vez en cada mquina:
> ssh nodo01 ..... yes .... exit
2. Crear en el directorio principal el fichero .mpd.conf
con una lnea que ponga: secretword=xxxxx
> chmod 600 .mpd.conf
IF - EHU
MPI
14 3
El proceso de compilacin/ejecucin de programas
MPI depende de la implementacin concreta. En el
caso de MPICH2:
1. Lanzar daemons en cada procesador:
> mpdboot v n zz f fichero_maquinas
2. Tras compilar (mpicc ), ejecutar el programa (spmd):
> mpiexec n xx programa
2. En su caso (mpmd), indicar qu ejecutar en cada nodo:
> mpiexec n 1 host nodo00 p1 : -n 1 host nodo01 p2
(o en un fichero)
IF - EHU
MPI
15 3
Algunas herramientas para gestionar el cluster
como si fuera una mquina nica. Una muy sencilla
es C3 (Cluster Command and Control suite).
http://www.csm.ornl.gov/torc/C3
Fichero de configuracin

cluster cluster32
{
g000002:nodo00 #head node
dead 0
nodo0[1-9]
nodo[10-31]
acpt48
acpt49
acpt51
}
Algunos comandos
cshutdown
clist, cname, cnum
cget, cpush, cpushimage
crm
ckill, cexec
IF - EHU
1. Introduccin.
2. Funciones MPI bsicas
inicio y control de procesos
envo y recepcin de mensajes
3. Otros modos de envo y recepcin.
ndice
IF - EHU
MPI
17 3
Aunque MPI consta de ms de 320 funciones, el
ncleo bsico lo forman slo 6:

2 de inicio y finalizacin del programa.
2 de control del nmero de procesos.
2 de comunicacin.

Sintaxis: MPI_Funcion()

#include <mpi.h>
Funciones bsicas
IF - EHU
MPI
18 3
Los parmetros de las funciones MPI son de tres
tipos:
IN: la funcin lee el argumento
OUT: la funcin modifica el argumento
IN/OUT: la funcin lee y modifica el argumento
Las funciones MPI (casi todas) devuelven un entero como
cdigo de error.
error = MPI_Funcion(...)

Si no ha habido problemas, MPI_SUCCESS (0 en esta
implementacin); en caso de errores, el valor que indica el tipo
de error depende de la implementacin.
Funciones bsicas
IF - EHU
MPI
19 3
1. Comienzo y final del programa:

> MPI_Init(&argc, &argv);

> MPI_Finalize();

Estas dos funciones son la primera y ltima funcin MPI
que deben ejecutarse en un programa.

No se pueden utilizar funciones MPI antes de _Init, y si
un proceso no ejecuta _Finalize el programa queda
como colgado.
F. bsicas: Init / Finalize
IF - EHU
MPI
20 3
Los procesos que se van a ejecutar se agrupan en
conjuntos denominados comunicadores.
Cada proceso tiene un identificador o pid en cada
comunicador.

El comunicador MPI_COMM_WORLD (un objeto de
tipo MPI_COMM) se crea por defecto y engloba a
todos los procesos.
Funciones bsicas
IF - EHU
MPI
21 3
2. Identificacin de procesos
> MPI_Comm_rank(comm, &pid);
Devuelve en pid (int) el identificador del proceso
dentro del grupo de procesos, comunicador comm,
especificado.
Recuerda que un proceso se identifica mediante dos
parmetros: identificador (pid) y grupo (comm).
> MPI_Comm_size(comm, &npr);
Devuelve en npr (int) el nmero de procesos del
comunicador especificado.
F. bsicas: Comm_rank / _size
IF - EHU
MPI
22 3
Un ejemplo simple

#include <stdio.h>
#include <mpi.h>
main (int argc, char *argv[])
{
int pid, npr, A = 2;
MPI_Init(&argc, &argv);

MPI_Comm_rank(MPI_COMM_WORLD, &pid);
MPI_Comm_size(MPI_COMM_WORLD, &npr);
A = A + 1;
printf(Proceso %d de %d activado. A = %d \n, pid, npr, A);

MPI_Finalize();
}
Funciones bsicas
IF - EHU
MPI
23 3
Otro ejemplo: planificacin de un bucle

...
main (int argc, char *argv[])
{
...

MPI_Comm_rank(MPI_COMM_WORLD, &pid);
MPI_Comm_size(MPI_COMM_WORLD, &npr);

for (i=pid; i<N; i=i+npr) func(i);

MPI_Finalize();
}
Funciones bsicas
IF - EHU
MPI
24 3
3. Envo y recepcin de mensajes
MPI ofrece dos (tres) tipos de comunicacin:

punto a punto, del proceso i al j (participan ambos).
en grupo (colectiva): entre un grupo de procesos, de
uno a todos, de todos a uno, o de todos a todos.
one-sided: del proceso i al j (participa uno solo).
F. bsicas: comunicacin
Adems, bsicamente en el caso de comunicacin entre
dos procesos, hay mltiples variantes en funcin de cmo
se implementa el proceso de envo y de espera.
IF - EHU
MPI
25 3
3. Envo y recepcin de mensajes entre dos procesos
La comunicacin entre procesos requiere (al menos) de
dos participantes: emisor y receptor.
El emisor ejecuta una funcin de envo y el receptor otra
de recepcin.
A
B
enviar recibir
La comunicacin es un proceso cooperativo: si una de
las dos funciones no se ejecuta, no se produce la
comunicacin (y podra generarse un deadlock).
IF - EHU
MPI
26 3
MPI ofrece diferentes modo de comunicacin. Veamos un
resumen.
EMI
REC
sncrona: la comunicacin no se
produce hasta que emisor y receptor
se ponen de acuerdo (sin bfer
intermedio).
RTS
- peticin de transmisin (espera)
RTR
- aceptacin de transmisin
D
- envo de datos (de usuario a usuario)
Modos de comunicacin (1)
IF - EHU
MPI
27 3
con bfer (buffered): el emisor deja el mensaje en un bfer
y retorna. La comunicacin se produce cuando el receptor est
dispuesto a ello. El bfer no se puede reutilizar hasta que se
vace.
EMI
REC
usuario s.o. s.o. usuario
Ojo con el tamao del bfer!
IF - EHU
MPI
28 3
bloqueante
Se espera a que la comunicacin se produzca, antes de
continuar con la ejecucin del programa.
La comunicacin sncrona es bloqueante. La comunica-
cin con bfer tambin, si el mensaje no cabe en el bfer.
no bloqueante
Se retorna inmediatamente de la funcin de comunica-
cin, y se contina con la ejecucin.
Se comprueba ms tarde si la comunicacin se ha
efectuado.
IF - EHU
MPI
29 3
Cada estrategia tiene sus ventajas e inconvenien-
tes:
> sncrona: es ms rpida si el receptor est dispuesto
a recibir; nos ahorramos la copia en el bfer.
Adems del intercambio de datos, sirve para sincronizar
los procesos.
Ojo: al ser bloqueante es posible un deadlock!
> con bfer: el emisor no se bloquea si el receptor no
est disponible, pero hay que hacer copia(s) del
mensaje (ms lento).
IF - EHU
MPI
30 3
Para enviar o recibir un mensaje es necesario
especificar:
a quin se enva (o de quin se recibe)
los datos a enviar (direccin de comienzo y cantidad)
el tipo de los datos
la clase de mensaje (tag)
Las dos funciones estndar para enviar y recibir
mensajes son:
Todo lo que no son los datos forma el sobre del mensaje
(que se puede procesar).
IF - EHU
MPI
31 3
> MPI_Send(&mess, count, type, dest,
tag, comm);
- mensaje a enviar: [mess (@comienzo), count (tamao), type]
- receptor: [dest (@destino), comm (comunicador)]
- tag: 0..32767 (clase de mensajes, orden...)
Funcin estndar para enviar un mensaje:
Tipos : MPI_CHAR, INT, LONG, FLOAT, DOUBLE, BYTE...
Send utiliza la capacidad de buffering del sistema; es
decir, retorna una vez copiado en el bfer el mensaje a
enviar siempre que quepa!
F. bsicas: Send y Recv
IF - EHU
MPI
32 3
> MPI_Recv(&mess, count, type, source,
tag, comm, &status);
- mensaje a recibir: [mess, count, type]
- emisor: [source, comm]
- tag: clase de mensaje
- status: devuelve informacin sobre el mensaje recibido
Funcin bsica para recibir un mensaje:
Recv se bloquea hasta que se efecta la recepcin.
IF - EHU
MPI
33 3
Algunas precisiones:
source, dest, count y tag son enteros (int); comm
y status son de tipo MPI_Comm y MPI_Status.
para que la comunicacin se efecte tienen que
coincidir las direcciones de emisor y receptor, y el
tag del mensaje.
el tamao del mensaje (count) definido en la funcin
Recv debe ser igual o mayor al definido en Send.
el origen de un mensaje en la funcin Recv puede ser
MPI_ANY_SOURCE, y el tipo de mensaje puede ser
MPI_ANY_TAG.
IF - EHU
MPI
34 3
status es un struct con tres campos, en el que se
devuelve informacin sobre el mensaje recibido:
status.MPI_SOURCE: indica el emisor del mensaje
status.MPI_TAG: devuelve el tag del mensaje recibido
status.MPI_ERROR: devuelve un cdigo de error
(aunque lo ms habitual es abortar en caso de error)
tambin puede obtenerse el tamao del mensaje
recibido ejecutando:
> MPI_Get_count(&status, type, &count);
IF - EHU
MPI
35 3
si un proceso tiene varios mensajes pendientes de
recibir, no se reciben en el orden en que se enviaron
sino en el que se indica en la recepcin mediante los
parmetros de origen y tag del mensaje.

si el tag del mensaje que se recibe puede ser
cualquiera, los mensajes que provienen del mismo
origen se reciben en el orden en que se enviaron.
IF - EHU
MPI
36 3
...
#define N 10
int main (int argc, char **argv)
{
int pid, npr, orig, dest, ndat, tag;
int i, VA[N];
MPI_Status info;

MPI_Comm_rank(MPI_COMM_WORLD,&pid);

for (i=0;i<N;i++) VA[i] = 0;

if (pid == 0)
{
for (i=0;i<N;i++) VA[i] = i;

dest = 1; tag = 0;
MPI_Send(&VA[0], N, MPI_INT, dest,
tag, MPI_COMM_WORLD);
}
else if (pid == 1)
{
for (i=0;i<N;i++) printf(%4d,VA[i]);

orig = 0; tag = 0;
MPI_Recv(&VA[0], N, MPI_INT, orig,
tag, MPI_COMM_WORLD, &info);

MPI_Get_count(&info, MPI_INT, &ndat);

printf(Datos desde pr %d; tag = %d,
ndat = %d \n, info.MPI_SOURCE,
info.MPI_TAG, ndat);

for (i=0;i<ndat;i++)
printf(%4d,VA[i]);
}

MPI_Finalize();
}
Ejemplo
IF - EHU
MPI
37 3
Lo ms sencillo, mandar primero un mensaje con la
longitud del segundo mensaje.
Tras ello, puede asignarse la memoria correspondiente para el
mensaje que se va a recibir.
Y si se desconoce el tamao del mensaje que hay
que recibir (p.e., se calcula dinmicamente)?
MPI_Probe(source, tag, comm, &status)
permite obtener informacin (fuente, tamao y tag) de
un mensaje que est a la espera de ser recibido.
Podemos as reservar espacio en memoria, decidir cmo recibir el
mensaje en funcin de quin lo enva, o incluso no recibirlo si nos
basta con el tag (p.e., es un mensaje vaco, un aviso).
F. bsicas: Probe
IF - EHU
MPI
38 3
Un par de funciones MPI para obtener tiempos de
ejecucin:

double MPI_Wtime();
tiempo (s) transcurrido desde algn instante anterior

double MPI_Wtick();
devuelve la precisin de la medida de tiempo
t1 = MPI_Wtime();
...
t2 = MPI_Wtime();
printf(T = %f\n, t2-t1);
F. bsicas: temporizacin
IF - EHU
MPI
39 3
Una cuestin previa sobre las operaciones de
entrada/salida.
Lo habitual es que slo un proceso tenga acceso a
teclado y pantalla; ese proceso se encargar de leer los
datos y distribuirlos, as como de recoger resultados e
imprimirlos.
if (pid==0)
{ leer_datos();
distribuir_datos();
}
else
recibir_datos();
Un procedimiento simple para hacerlo podra ser:
F. bsicas: entrada/salida
IF - EHU
1. Introduccin.
3. Otros modos de envo/recepcin
comunicacin sncrona, inmediata...
ndice
IF - EHU
MPI
41 3
Aparte de las funciones estndar de envo y
recepcin, MPI ofrece varias alternativas con el
objetivo de lograr el mximo rendimiento.
Aunque bastara con un solo modo, cada alternativa
est pensada para determinado tipo de situacin.
Las principales alternativas al modo estndar son:
- comunicacin sncrona
- comunicacin inmediata
Otros modos de comunicacin
IF - EHU
MPI
42 3
1. Comunicacin sncrona
En modo sncrono, la funcin de envo no retorna hasta
que se produce la comunicacin.
En principio, no se necesita un bfer intermedio.

> MPI_Ssend (mismos parmetros que Send);
La funcin sncrona es bloqueante; si no se produce el
correspondiente matching, habr un deadlock.
Comunicacin sncrona
IF - EHU
MPI
43 3
Obviamente, hay que cambiar el orden.
Deadlock
P1 P2
Ssend_to_2; Ssend_to_1;
Recv_from_2; Recv_from_1;
Y con el Send estndar?
P1 P2
Send_to_2; Send_to_1;
Recv_from_2; Recv_from_1;
Comunicacin sncrona
IF - EHU
MPI
44 3
2. Comunicacin inmediata
La funcin de comunicacin retorna sin esperar a que
se produzca una determinada accin (es una especie de
post/signal).
Es, por definicin, no bloqueante y se busca solapar las
latencias de clculo y comunicacin.
La comunicacin se divide en dos fases: un aviso de
envo/recepcin, y una verificacin de que se ha
producido.
Se utiliza un handle para obtener informacin sobre el
estado de la comunicacin.
Comunicacin sncrona
IF - EHU
MPI
45 3
Funciones de envo y recepcin
> MPI_Isend(..., &request);
> MPI_Irecv(..., &request);

request debe ser una variable de tipo MPI_Request, y se utiliza
para preguntar sobre el estado de la funcin.
El bfer no se puede acceder hasta que la comunicacin se produce.
Funciones de test (status debe ser de tipo MPI_Status)

> MPI_Test(&request, &flag, &status);
devuelve en flag un 0 si la operacin no se ha completado
> MPI_Wait(&request, &status);
espera hasta que la comunicacin se haya efectuado
Comunicacin inmediata
IF - EHU
MPI
46 3
Ejemplo
int flag = 0; // slo parte del cdigo
MPI_Status status;
int bufer[grande];
MPI_Request info;
...
MPI_Isend(bufer, grande, MPI_INT, dest, tag,
MPI_COMM_WORLD, &info);
while(!flag && hay_tareas)
{ ... /* realizar una tarea */
MPI_Test(&info, &flag, &status);
}
if (!flag) MPI_Wait(&info, &status);
...
Comunicacin inmediata
IF - EHU
MPI
47 3
Hay ms opciones (muchas):
- MPI_Sendrecv();
Por ejemplo, en una comunicacin en anillo, recibe del
anterior y enva al siguiente, asegurando que no se
produce deadlock.
- Comunicacin con buffering
Obligamos a que la comunicacin se haga mediante un
bfer definido por el usuario.
Hay un conjunto de funciones con esas caractersticas
(Bsend, ), ms otras funciones para gestionar los
bferes.
IF - EHU
MPI
48 3
- Comunicacin persistente
Si se van a enviar repetidamente mensajes con los mismos
argumentos (por ejemplo, dentro de un bucle), dividimos la
comunicacin en dos partes: (1) crear el contexto, una
sola vez, y (2) enviar el mensaje (las veces que haga
falta).
> MPI_Send_init(, &request);
> MPI_Recv_init(, &request);
> MPI_Start(&request);
(Isend = Send_init + Start)
- Mezclas de todas ellas
Hay ms opciones (muchas):
IF - EHU
MPI
49 3
La comunicacin es uno de los puntos clave en el
rendimiento de un sistema paralelo de memoria
distribuida. Por ello, MPI ofrece una gran variedad de
estrategias de comunicacin.
Resumen de modos de envo / recepcin
Modo Fun. bloq. Func. no bloq.

estndar MPI_Send MPI_Isend
sncrono MPI_Ssend MPI_Issend
buffered MPI_Bsend MPI_Ibsend
(ready MPI_Rsend MPI_Irsend)
Resumen
En todos los casos: Recv / Probe Irecv / Iprobe
IF - EHU
MPI
50 3
El uso recomendado sera el siguiente:

MPI_Ssend: cuando es posible, ofrece los mejores
resultados, puesto que no se utilizan bferes intermedios
(ojo con los deadlocks).

MPI_Send: la alternativa ms habitual.

MPI_Isend: si, por cuestiones de rendimiento, se
necesitan rutinas no bloqueantes.
(p.e., en clusters en los que la comunicacin sea cara, para
solapar clculo y comunicacin).

El resto de opciones, para casos especiales.
Resumen
IF - EHU
1. Introduccin.
3. Otros modos de envo/recepcin.
4. Comunicacin en grupo: broadcast,
gather, scatter / reduce / barrier
ndice
IF - EHU
MPI
52 3
Muchas aplicaciones requieren de operaciones de
comunicacin en las que participan muchos procesos.
La comunicacin es en grupo o colectiva si partici-
pan en ella todos los procesos del comunicador.
Ejemplo: un broadcast, envo de datos desde un
proceso a todos los dems.
En general, podra ejecutarse mediante un bucle de
funciones tipo send/receive, pero no sera muy
eficiente.
Comunicacin en grupo
IF - EHU
MPI
53 3
Todos los procesos del comunicador deben ejecutar
la funcin. Las funciones de comunicacin en grupo
son bloqueantes en el mismo sentido que la funcin
Send.
Tres tipos: 1 Movimiento de datos
2 Clculo en grupo
3 Sincronizacin
Las principales funciones de comunicacin en grupo
que ofrece MPI son las siguientes:
IF - EHU
MPI
54 3
1a BROADCAST: envo de datos desde un proceso
(root) a todos los dems.
A P0
P2 P3
P1
A
A
A
(La implementacin suele ser en rbol)
A P0
P2 P3
P1
> MPI_Bcast(&mess, count, type, root, comm);
Mov. de datos: broadcast
IF - EHU
MPI
55 3
ABCD
P0
P2 P3
P1
A B C D
P0
P2 P3
P1
1b SCATTER: reparto de datos desde un proceso al
resto de procesos del comunicador.
C
B
D
A
CG: mov. de datos, scatter
IF - EHU
MPI
56 3
> MPI_Scatter(&send_data, send_count, send_type,
&recv_data, recv_count, recv_type,
root, comm);
- el proceso root distribuye send_data en P trozos,
uno por procesador, de tamao send_count.
- los datos se reciben en recv_data (tambin en root).
- lo lgico es que el tamao y tipo de los datos que se
envan y se reciben sean iguales.
Ejemplo: A = (0, 1, 2, 3, 4, 5, 6, 7) en P0
MPI_Scatter(A, 2, MPI_INT, B, 2, MPI_INT, 0, comm);
(P0) B = 0, 1 (P1) B = 2, 3 (P2) B = 4, 5 (P3) B = 6, 7
CG: mov. de datos, scatter
IF - EHU
MPI
57 3
A P0
P2 P3
P1
C D
B A P0
P2 P3
P1
C D
B ABCD
1c GATHER: recoleccin de datos de todos los procesos
en uno de ellos (orden estricto de pid).
CG: mov. de datos, gather
IF - EHU
MPI
58 3
> MPI_Gather(&send_data, send_count, send_type,
&recv_data, recv_count, recv_type,
root, comm);
- el proceso root recolecta en recv_data los datos
enviados en send_data por cada proceso del comunicador.
- los datos se guardan en el orden marcado por el pid.
- recv_count indica el tamao de los datos recibidos de
cada proceso, no el total; lo lgico es que tamao y tipo de
los datos que se envan y se reciben sean iguales.
Ejemplo: (P0) B = 0, 1 (P1) B = 2, 3 (P2) B = 4, 5 (P3) B = 6, 7
MPI_Gather(B, 2, MPI_INT, C, 2, MPI_INT, 0, comm);
en P0: C = 0, 1, 2, 3, 4, 5, 6, 7
CG: mov. de datos, gather
IF - EHU
MPI
59 3
Otras versiones de estas funciones
> MPI_Allgather(); al final, todos los procesos disponen
de todos los datos.
> MPI_Gatherv(); la informacin que se recolecta es de
tamao variable.
> MPI_Allgatherv(); suma de las dos anteriores.
> MPI_Alltoall(); todos los procesos distribuyen datos a
todos los procesos.
> MPI_Scatterv(); la informacin que se distribuye es de
tamao variable.
> MPI_Alltoallv(); suma de las dos anteriores.
CG: movimiento de datos
IF - EHU
MPI
60 3
Ejemplo: reparto de trozos de un vector A, de
tamaos diferentes y no consecutivos:
- Tam: vector (int) que contiene un elemento por proceso, e
indica el nmero de datos del trozo a enviar a cada uno.
- Desp: vector (int) que contiene un elemento por proceso, e
indica la distancia desde el comienzo de A al comienzo de
cada trozo que hay que repartir.
- Tamrec: entero que indica el nmero de elementos a recibir
en buf en el procesador local.
No se admite solapamiento fisico de los trozos a enviar.
> MPI_Scatterv(A, tam, desp, tipo,
buf, tamrec, tipo, root, comm);
CG: movimiento de datos
IF - EHU
MPI
61 3
2 REDUCE: una operacin de reduccin con los
datos de cada procesador, dejando el resultado en
uno de ellos (root).

> MPI_Reduce(&operand, &result, count, datatype,
operator, root, comm);
A P0
P2 P3
P1
C D
B
A
P0
P2 P3
P1
C D
B
A+B+C+D
CG: clculo en grupo, reduce
IF - EHU
MPI
62 3
Algunos comentarios
Operacin: result = result operator operand

result es una variable del proceso destino, de nombre
diferente a operand (no aliasing).

Funciones tpicas de reduccin: MPI_MAX, _MIN,
_SUM, _PROD, _BAND, _BOR, _BXOR, _LAND, _LOR,
_LXOR, _MAXLOC, _MINLOC

Pueden definirse otras operaciones de reduccin:
MPI_Op_create(); MPI_Op_free();
IF - EHU
MPI
63 3
Otras funciones del mismo tipo:

> MPI_Allreduce();
> MPI_Reduce_scatter();
> MPI_Scan();
ALLREDUCE
3 pasos (log P)
IF - EHU
MPI
64 3
3 BARRIER: sincronizacin global entre los procesos
del comunicador.

> MPI_Barrier(comm);

La funcin se bloquea hasta que todos los procesos del
comunicador la ejecutan.
CG: sincronizacin
IF - EHU
MPI
65 3
Ejemplo: V(i) = V(i) * EV(j)

(Leer N; sum = 0);
for (j=0; j<N; j++) sum = sum + V[j];
for (i=0; i<N; i++) V[i] = V[i] * sum;

1. Leer N (el pid = 0)
2. Broadcast de N/npr (tamao del vector local)
3. Scatter del vector V (trozo correspondiente)
4. Clculo local de la suma parcial
5. Allreduce de sumas parciales (todos obtienen suma total)
6. Clculo local de V(i)*sum
7. Gather de resultados
8. Imprimir el resultado (el pid = 0)
IF - EHU
1. Introduccin.
5. Tipos de datos derivados
vector, indexed, struct / packed
ndice
IF - EHU
MPI
67 3
La comunicacin entre procesos es costosa (en
funcin de la red). Por ello, es mejor enviar un
paquete con 3 datos que 3 paquetes con un dato
cada uno.
Las funciones Send y Recv indican explcitamente la
direccin de comienzo del mensaje y el nmero de
elementos que lo componen, pero hay una
restriccin: deben ser elementos consecutivos y
del mismo tipo.
Tipos de datos derivados
IF - EHU
MPI
68 3
Ejemplo: enviar la fila 2 de la matriz A, de P0 a P1
Pero, cmo se enva una columna en un solo mensaje?
cmo se envan en un mensaje datos de tipos diferentes?
int A[N][M];
...
orig = 0; dest = 1;
if (pid == orig)
MPI_Send(&A[2][0], M, MPI_INT, dest, 0,
MPI_COMM_WORLD);
else if (pid == dest)
MPI_Recv(&A[2][0], M, MPI_INT, orig, 0,
MPI_COMM_WORLD, &info);
IF - EHU
MPI
69 3
Tenemos dos soluciones:
1. Definir nuevos tipos de datos, en los que se
permita agrupar datos de diferente tipo, tamao...
para formar un mensaje con cierta estructura.

2. Empaquetar los datos que hay enviar (que en
general sern de diferente tipo, tamao y
estructura) en un nico paquete, que el receptor
deber desempaquetar de manera adecuada.
IF - EHU
MPI
70 3
1. Definicin de tipos derivados
La generacin de tipos de datos derivados se
efecta mediante dos funciones:
1. definicin del tipo de datos derivado
2. creacin del tipo (commit)
Los nuevos tipos de datos que se crean se declaran
como MPI_Datatype.
Veamos la opciones que disponemos.
IF - EHU
MPI
71 3
1a. Tipo vector
Se define un vector de n elementos, del mismo tipo y
tamao, a distancia (stride) constante.
(normalmente un subconjunto de un array mayor).
> MPI_Type_vector(num_elem, tam, stride, tipo,
&nuevo_tipo);

El nuevo tipo contiene num_elem elementos de tamao tam, a
distancia stride uno de otro.
[ - MPI_Type_contiguous(num_elem, tipo, &nuevo_tipo); ]
TDD: vector
IF - EHU
MPI
72 3
Ejemplo: enviar la columna 2 de la matriz A, de P0 a P1.
int A[N][M];
MPI_Datatype Columna;
...
MPI_Type_vector(N, 1, M, MPI_INT, &Columna);
MPI_Type_commit(&Columna);

orig = 0; dest = 1;

if (pid == orig)
MPI_Send(&A[0][2], 1, Columna, dest, 0, MPI_COMM_WORLD);
else if (pid == dest)
MPI_Recv(&A[0][2], 1, Columna, orig, 0, MPI_COMM_WORLD, &info);

TDD: vector
OJO: 1 columna
IF - EHU
MPI
73 3
1b. Tipo indexed
Se define un vector de n elementos, del mismo tipo,
con tamao y stride variable.
> MPI_Type_indexed(num_elem, tam, desp, tipo,
&nuevo_tipo);
tam[]: array que contiene el nmero de componentes de cada
elemento que forma el nuevo tipo.
desp[]: array que contiene el desplazamiento necesario para
acceder desde el comienzo del nuevo tipo a cada
elemento (de tipo MPI_Aint).
TDD: indexed
IF - EHU
MPI
74 3
Ejemplo: enviar de P0 a P1 el tringulo superior de
la matriz A.
int A[N][M], T[N][M];
MPI_Datatype Mtri;
...

for(i=0; i<N; i++) {
long_bl[i] = M - i;
desp[i] = (M+1) * i;
}

MPI_Type_indexed (N, long_bl, desp, MPI_INT, &Mtri);
MPI_Type_commit (&Mtri);

if (pid == 0) MPI_Send(A, 1, Mtri, 1, 0, MPI_COMM_WORLD);
else if (pid == 1) MPI_Recv(T, 1, Mtri, 0, 0, MPI_COMM_WORLD, &info);
N
M
TDD: indexed
IF - EHU
MPI
75 3
1c. Tipo struct
Es un caso ms general, en el que se agrupan n
elementos de tamao y tipo diferente.
Por ejemplo, P0 tiene que enviar a todos los procesadores
tres parmetros: A y B, flotantes, y C, entero. Podemos
formar un paquete con los tres parmetros y efectuar un
nico envo (BC).
Para ello construimos un struct con:
- nmero de elementos
- tipo de cada elemento
- desplazamiento de cada elemento
desde el origen
6
2
f f i
A
B C
TDD: struct
IF - EHU
MPI
76 3
1c. Tipo struct
La funcin para definir el tipo es:
> MPI_Type_create_struct(num_elem, tam, desp,
tipo, &nuevo_tipo);

tam[]: nmero de componentes de cada elemento que
forma el nuevo tipo.
desp[]: desplazamiento necesario para acceder desde el
comienzo del nuevo tipo a cada elemento (MPI_Aint).
tipo[]: tipo de cada elemento (MPI_Datatype).
TDD: struct
> MPI_Get_address (&A, &dirA)
Devuelve la direccin de A en dirA (de tipo MPI_Aint)
IF - EHU
MPI
77 3
void Crear_Tipo (float* A, B; int* C; MPI_Datatype* Mensaje) {
int tam[3];
MPI_Aint desp[3], dir1, dir2; // address int
MPI_Dataype tipo[3];
tam[0] = tam[1] = tam[2] = 1;
tipo[0] = tipo[1] = MPI_FLOAT;
tipo[2] = MPI_INT;

despl[0] = 0;
MPI_Get_address (A, &dir1);
MPI_Get_address (B, &dir2);
despl[1] = dir2 - dir1;
MPI_Get_address (C, &dir2);
despl[2] = dir2 - dir1;

MPI_Type_create_struct(3, tam, desp, tipo, Mensaje);
MPI_Type_commit(Mensaje);
}
... (A, B, C, punteros a las variables)

Crear_Tipo(A, B, C, &Mensaje);
MPI_Bcast(A, 1, Mensaje, 0, MPI_COMM_WORLD);
...
TDD: struct
IF - EHU
MPI
78 3
1d. Subarrays

Una submatriz de N dimensiones a partir de una de N
dimensiones. Por ejemplo, un bloque 2D de una
matriz 2D:
TDD: subarrays
> MPI_Type_create_subarray(...);
> MPI_Type_create_darray(...);
IF - EHU
MPI
79 3
1d. Subarrays

Una submatriz de N dimensiones a partir de una de N
dimensiones. Por ejemplo, un bloque 2D de una
matriz 2D;
TDD: subarrays
> MPI_Type_create_subarray(ndims, tam_a, tam_sa,
dir_sa, orden, tipo, &nuevo_tipo);

ndims: dimensiones del array original
tam_a[], tam_sa[]: elementos en cada dimensin
dir_sa[]: comienzo del subarray
orden: MPI_ORDER_C, _FORTRAN
IF - EHU
MPI
80 3
TDD: subarrays
Tamao y extensin del tipo:
1. Tamao: nmero de bytes que se transmiten (sin
incluir huecos).

2. Extensin: Distancia entre el primer y el ltimo
byte (incluyendo huecos).

Un par de funciones MPI devuelven estos
parmetros del tipo de datos.
IF - EHU
MPI
81 3
2. Empaquetamiento

Alternativa a la definicin de tipos: empaquetar los
datos que hay que enviar en posiciones consecutivas
de memoria.
La comunicacin se efecta en tres fases:
Antes de enviar el mensaje, se van aadiendo los datos a un
bfer (vector) mediante la funcin MPI de empaquetamiento.

Se enva el vector, que es de tipo MPI_PACKED.

El receptor desempaqueta los datos recibidos mediante
la funcin MPI de desempaquetamiento.
TDD: packed
IF - EHU
MPI
82 3
2. Empaquetamiento
La funcin para empaquetar datos es:
> MPI_Pack(&dat, tam, tipo, bufer, tambuf,
&pos, comm);

Aade a bufer (char, de tamao tambuf) la variable dat,
a partir de la posicin marcada por el puntero pos.
El puntero queda apuntando a la primera posicin libre de
bufer. Al final de las operaciones de empaquetamiento,
indica el tamao del paquete.
La funcin MPI_Pack_size (ver manual) devuelve el tamao mnimo
necesario para empaquetar un objeto. Se puede usar para calcular el
tamao final del paquete y reservar memoria para el mismo.
TDD: packed
IF - EHU
MPI
83 3
2. Empaquetamiento
La funcin para desempaquetar datos es:
> MPI_Unpack(bufer, tambuf, &pos, &dat, tam,
tipo, comm);

Recupera de bufer (apuntado por pos) la variable dat
del tamao y tipo indicado (pos queda apuntando a la
siguiente variable).

Tambuf debe ser suficiente para que quepa el mensaje
recibido.
TDD: packed
IF - EHU
MPI
84 3
void Leer_Datos (float* A, B; int* C; int pid) {
char bufer[100]; int pos;
if (pid == 0) {
printf(-> A, B y C\n);
scanf(%f %f %d, A, B, C); // A, B, C, punteros a las vbles.
pos = 0;
MPI_Pack(A, 1, MPI_FLOAT, bufer, 100, &pos, MPI_COMM_WORLD);
MPI_Pack(B, 1, MPI_FLOAT, bufer, 100, &pos, MPI_COMM_WORLD);
MPI_Pack(C, 1, MPI_INT, bufer, 100, &pos, MPI_COMM_WORLD);
MPI_Bcast(bufer, pos, MPI_PACKED, 0, MPI_COMM_WORLD);
} else {
MPI_Bcast(bufer, 100, MPI_PACKED, 0, MPI_COMM_WORLD);
pos = 0;
MPI_Unpack(bufer, 100, &pos, A, 1, MPI_FLOAT, MPI_COMM_WORLD);
MPI_Unpack(bufer, 100, &pos, B, 1, MPI_FLOAT, MPI_COMM_WORLD);
MPI_Unpack(bufer, 100, &pos, C, 1, MPI_INT, MPI_COMM_WORLD);
}
}
TDD: packed
IF - EHU
MPI
85 3
Para reducir el overhead de la comunicacin se pueden
definir tipos de datos que agrupen los datos a enviar en
posiciones consecutivas de memoria.
Especialmente til cuando se repite el mismo tipo de
comunicacin una y otra vez.
Un tipo derivado es bsicamente un struct que se crea en
ejecucin y que puede pasarse como argumento a una
funcin de comunicacin.
Tipos: MPI_Type_vector, _indexed, _struct
Otra alternativa es empaquetar datos y desempaque-tarlos
tras recibirlos (MPI_PACKED).
TDD: resumen
IF - EHU
MPI
86 3
Lo ms habitual es utilizar el mecanismo estndar de
transmisin: datos consecutivos de un array.
Si los datos a enviar son muchos y no consecutivos, y se
envan repetidamente, lo mejor sera definir un tipo
especfico:
- datos homogneos: contiguous, vector, indexed
- datos heterogneos: struct
Si se envan datos heterogneos una sola vez (o pocas), lo
ms adecuado sera empaquetar.
TDD: resumen
IF - EHU
MPI
87 3
Matching de tipos
Send y Recv especifican el tipo de los datos que se envan
y reciben. Se llama firma (signature) de tipos a la
secuencia {t
0
, t
1
..., t
n-1
}, donde t
i
es el tipo del elemento i.

El tipo no tiene por qu ser el mismo en ambas funciones,
pero la firma de tipos del tipo de datos especificado en
Recv tiene que tener al menos tantos elementos como la
de Send, y los tipos han de ser iguales: es decir, se
deben recibir al menos tantos datos como se envan
y del mismo tipo.

Ojo: en las funciones colectivas el tipo debe ser el mismo!
TDD: resumen
IF - EHU
MPI
88 3
Matching de tipos
El paquete de datos lleva los datos sin estructura. La
estructura se recompone, si se desea, al recibirlos.
Por ejemplo, enviamos N elementos de una columna de
una matriz utilizando el tipo columna.
Si recibimos los datos con el tipo columna, se cargarn en
la columna de la matriz que indiquemos.
Si los recibimos como N enteros, se cargarn uno tras otro
a partir de la direccin que indiquemos; si los recibimos
con tipo diagonal, se cargarn en la diagonal; etc.
TDD: resumen
IF - EHU
1. Introduccin.
ndice
IF - EHU
MPI
90 3
Un comunicador MPI define un grupo de procesos
entre los cuales es posible el intercambio de mensajes.
Cada proceso se identifica en el comunicador mediante
su pid.
El comunicador predefinido MPI_COMM_WORLD
engloba a todos los procesos de la aplicacin paralela.
En muchos casos es til definir otros grupos de
procesos o comunicadores para hacer ms simple la
comunicacin.
As, un proceso puede tener ms de un pid: uno por
cada grupo del que forme parte.
Comunicadores
IF - EHU
MPI
91 3
Un comunicador est formado, al menos, por un
grupo de procesos y un contexto.
El contexto define un espacio propio e identificado de
comunicacin.
Un comunicador puede incluir ms datos asociados,
tales como una topologa, caractersticas especficas
de los procesadores que lo componen,
entrada/salida, etc.
Para ver la utilidad de definir grupos de procesos,
analicemos un ejemplo sencillo: producto de dos
matrices.
Comunicadores
IF - EHU
MPI
92 3
Ejemplo: C = A B
En el caso de una matriz densa, hay que efectuar O(N
3
)
operaciones. Cmo paralelizar el clculo de manera
eficiente entre P procesadores? Cul es la mejor manera
de distribuir los datos entre los procesos?
Objetivo: minimizar el tiempo asociado a la comunicacin.
C
ij
= A
i,0
B
0,j
+ A
i,1
B
1,j
+ ... + A
i,i
B
i,j
+ ... + A
i,n-1
B
n-1,j
x
=
B A
C
Motivacin
IF - EHU
MPI
93 3
x
=
B A
C
P0
1. Descomposicin unidimensional (filas)
(P procesadores, N/P filas por procesador)
Computacin por procesador (* y +) : O(N
3
/P)
Pero hay que aadir comunicacin: N
2
/P datos desde
cada uno de los P-1 procesadores restantes O(N
2
).
Podra ser un allgather de N
2
/P datos, que se ejecuta
en log P pasos.
Motivacin (A B)
IF - EHU
MPI
94 3
P
P N
t P t t
P
N
w i op
log
log
2
2 3
+ + ~
T
ejec
= T
calc
+ T
com
Eficiente slo si: t
op
>> t
w
o
P es pequeo (<<N)
P
P N
t P t
P
N
t t P T
w i w i com
log
log log
2 2
+ =
|
|
.
|
\
|
+ =
Si T
com
= t
i
+ t
w
N t
i
tiempo de inicio
t
w
tiempo por palabra
Motivacin (A B)
IF - EHU
MPI
95 3
N = 100 t
i
= 100 t
w
t
w
= 100 t
op
P
speed-up = Ts / Tp
0
20
40
60
80
100
20 40 60 80 100
e
f
i
c
i
e
n
c
i
a

=

T
s

/

(
T
p
*
P
)

0
0.2
0.4
0.6
0.8
1
Motivacin
IF - EHU
MPI
96 3
2. Descomposicin bidimensional:
Computacin por procesador: O(N
3
/P)
x
=
B A
C
P0
Pero ahora la necesidad de comunicacin es menor.
Cada procesador necesita los datos de los bloques de su
fila y su columna.
Se necesita recibir 2(P
1/2
-1)(N
2
/P) datos.
Cul es la manera ms eficiente de procesar/enviar esos datos?
Motivacin (A B)
IF - EHU
MPI
97 3
A
00
B
00
+ A
01
B
10
+ A
02
B
20
A
00
B
01
+ A
01
B
11
+ A
02
B
21
A
00
B
02
+ A
01
B
12
+ A
02
B
22

A
20
B
00
+ A
21
B
10
+ A
22
B
20
A
20
B
01
+ A
21
B
11
+ A
22
B
21
A
20
B
02
+ A
21
B
12
+ A
22
B
22

A
10
B
00
+ A
11
B
10
+ A
12
B
20
A
10
B
01
+ A
11
B
11
+ A
12
B
21
A
10
B
02
+ A
11
B
12
+ A
12
B
22

bc
bc
bc
bc
bc
bc
Motivacin (A B)
Algoritmo de multiplicacin (Fox):
IF - EHU
MPI
98 3
Algoritmo de multiplicacin (Fox):
for k = 0 to \P 1
en cada fila i, el proceso (i+k) mod N hace un broadcast
de A (su trozo) al resto de procesos de la fila
operaciones locales de clculo: C
i,j
+= A
i,i+k
B
i+k,j

envo del trozo procesado de B al vecino de arriba
Comunicacin por procesador:
\P veces
broadcast de N
2
/P datos a \P - 1 procesos (se puede
optimizar en log \P pasos)
send de N
2
/P datos
Motivacin (A B)
IF - EHU
MPI
99 3
Coste global (clculo + comunicacin)
( )
w i op
w i op ejec
t N
P
P
t
P P
t
P
N
P
N
t t P P t
P
N
T
2
3
2 3
2
log
2
log 2
1 log
2
+ + ~
|
|
.
|
\
|
+ + + ~
[ y el coste de reorganizar las matrices? ]
Motivacin (A B)
IF - EHU
MPI
100 3
N = 100 t
i
= 100 t
w
t
w
= 100 t
op
e
f
i
c
i
e
n
c
i
a

=

T
s

/

(
T
p
*
P
)

0
0.2
0.4
0.6
0.8
1
0
20
40
60
80
100
20 40 60 80 100
P
speed-up = Ts / Tp
Motivacin
IF - EHU
MPI
101 3
Conclusin: divisin 2D es ms escalable, pero requiere
comunicaciones entre subconjuntos de procesos.
N
N
N
2
/P
Com.: N
2
- N
2
/P =
N
2
(P-1)/P
P
1/2

bloques
Com.: 2 N
2
/P (P
1/2
-1) =
N
2
2(P
1/2
-1)/P
Resumen (NxN datos, P procesadores)
0
0.2
0.4
0.6
0.8
1
1 10 100 1000
C
O
M
P
Motivacin
IF - EHU
MPI
102 3
Para crear grupos de procesos entre los que poder
intercambiar informacin, hay que seguir los
siguientes pasos:
1. Extraer de un comunicador inicial, com1, el grupo de
procesos asociados, gr1:

> MPI_Comm_group(com1, &gr1);

Si com1 es MPI_COMM_WORLD, gr1 contendr a
todos los procesos.
Creacin de comunicadores
IF - EHU
MPI
103 3
3. Finalmente, se crea el comunicador com2 con los
procesos del grupo gr2 extrados del comunicador com1:

> MPI_Comm_create(com1, gr2, &com2);
2. Crear un nuevo grupo de procesos, gr2, eligiendo del
grupo gr1 aquellos que queremos que formen parte del
nuevo comunicador:

> MPI_Group_incl(gr1, npr_gr2, pid_gr1, &gr2);

pid_gr1 es un array de npr_gr2 elementos que indica el pid
de los procesos que se eligen para formar el nuevo grupo.
(tambin se puede hacer por exclusin, con la funcin MPI_Group_excl)
IF - EHU
MPI
104 3
Ejemplo: una matriz est repartida por bloques en n n
procesos. As definiramos el grupo fila 0 de procesos
y haramos un broadcast en esa fila:
MPI_Group gr1, grf0;
MPI_Comm CF0;

for(i=0; i<n; i++) pids[i] = i; /* lista de proc. */

MPI_Comm_group (MPI_COMM_WORLD, &gr1);
MPI_Group_incl (gr1, n, pids, &grf0);
MPI_Comm_create(MPI_COMM_WORLD, grf0, &CF0);
...
if (pid < n) {
MPI_Comm_rank(CF0, &pid_f0);
MPI_Broadcast(&A[0][0], tam, MPI_FLOAT, 0, CF0);
}
IF - EHU
MPI
105 3
Los grupos de procesos son variables de tipo
MPI_Group y los comunicadores son de tipo MPI_Comm.

MPI_Comm_create es una operacin colectiva, que
debe ser llamada por todos los procesos del comunicador
original (aunque no vayan a formar parte del nuevo
comunicador; se les devuelve el valor MPI_COMM_NULL).
Al finalizar su uso hay que deshacer el comunicador,
ejecutando MPI_Comm_free.

Otras funciones para trabajar con grupos:
MPI_Group_rank, size, free, union, intersection...
IF - EHU
MPI
106 3
Si hay que crear comunicadores similares a partir de
uno determinado (por ejemplo filas o columnas de
una estructura 2D), podemos generarlos todos a la
vez, mediante la funcin:

> MPI_Comm_split(com1,split_key,pid_com1,&com2);

Los procesos de com1 se van a agrupar en nuevos
comunicadores en funcin de la clave con la que llamen a
la funcin.
Se crean tantos comunicadores como claves diferentes se
utilicen, todos con el mismo nombre com2.
IF - EHU
MPI
107 3
Ejemplo: crear comunicadores para todas las filas
de un grupo de n n procesos:
// pid = identificador en el comunicador global

mi_fila = pid / n;
MPI_Comm_split(MPI_COMM_WORLD, mi_fila, pid, &CFILA);
Si haba 33 procesos, ahora tendremos un nuevo comunicador en
el que el grupo de procesos es diferente en funcin de quin lo use:
{0,1,2} en P0,P1,P2 / {3,4,5} en P3,P4,P5 / {6,7,8} en P6,P7,P8
Se trata de una funcin colectiva; todos los procesos del comuni-
cador original tienen que ejecutarla. Si un proceso no va a formar
parte de los nuevos comunicadores, llama a la funcin con la clave
MPI_UNDEFINED (formar parte del comunicador MPI_COMM_NULL).
IF - EHU
MPI
108 3
Un comunicador puede incluir, adems del grupo y el
contexto, otro tipo de informacin o atributos; por
ejemplo, una topologa (virtual).

No se refiere a la red de comunicacin, sino a una
manera alternativa de identificar a los procesos de un
comunicador.
Se genera un nuevo comunicador.

Dos tipos: cartesian y graph.
Topologas
IF - EHU
MPI
109 3
Por ejemplo, si queremos trabajar con una distribucin
2D de datos, podemos definir una retcula de
procesos (p.e., de 4x4 si tenemos 16 procesadores).
Para definir un comunicador con una malla global
tenemos que indicar:
nmero de dimensiones (2)
elementos por dimensin (4)
cadenas (0) o anillos (1)?
optimizacin (ajuste a la red fsica)
Topologas
IF - EHU
MPI
110 3
Ejemplo: definir un comunicador con topologa toro
MPI_Comm CTORO
...
opt = 1; ndim = 2;
kdim[0] = kdim[1] = 4;
c_a[0] = c_a[1] = 1;

MPI_Cart_create (MPI_COMM_WORLD, ndim, kdim, c_a,
opt, &CTORO);
kdim: nmero de procesos en cada dimensin.
c_a: 0 malla; 1 toro;
CTORO es un nuevo comunicador que engloba a los mismos
procesos que MPI_COMM_WORLD, pero que aade coordenadas
cartesianas a los procesos.
Topologas
IF - EHU
MPI
111 3
Ahora podemos trabajar con una identificacin doble
de los procesos: el pid en el nuevo comunicador y
las coordenadas cartesianas de la topologa
asociada.
Dos funciones permiten pasar de una a otra:
> MPI_Cart_coords(com2, pid2, dim, coord);

com2: nuevo comunicador con topologa
pid2: identificador del proceso en el nuevo comunicador
dim: nmero de dimensiones
coord: array donde se devuelven las coordenadas

> MPI_Cart_rank(com2, coord, pid);
Topologas
IF - EHU
MPI
112 3
Se pueden obtener las direcciones de los vecinos en
la topologa:
> MPI_Cart_shift(com, direc, desp, &orig, &dest);

dir: dimensin en la que queremos buscar los vecinos
desp: distancia del vecino
&orig,&dest: vecinos segun el despl (orig, yo, dest)
Topologas
IF - EHU
MPI
113 3
Se puede dividir (split) una retcula en otras de menos
dimensiones (p.e., una malla de dos dimensiones en sus
columnas o filas), y crear as nuevos comunicadores:
> MPI_Cart_sub(cart_comm, free_coords, new_comm);

A partir del comunicador que tiene asociada la topologa, se crean
comunicadores en funcin del array booleano free_coords:
0 se considera esa coordenada
1 no se tiene en cuenta (free)

Por ejemplo, de una malla de n n procesos se pueden crear
los comunicadores fila haciendo: free_coord[0] = 0;
free_coord[1] = 1; (al revs, las columnas).
Topologas
IF - EHU
MPI
114 3
Un conjunto de funciones similares permite aadir un
grafo subyacente a un determinado grupo de
procesos.
En resumen.
Un comunicador representa a un grupos de procesos
que se reconocen entre s como posible origen y destino
de sus comunicaciones.
Una topologa es un mecanismo alternativo de
identificacin lgica de procesos dentro de un grupo,
que genera un nuevo comunicador y, en su caso,
subgrupos.
Topologas
IF - EHU
MPI
115 3
Resumen de las funciones prinicipales (hay ms
funciones, mirar manual) que permiten crear
comunicadores y topologas:

> MPI_Comm_group/create/split/free

> MPI_Group_incl/excl/rank/free

> MPI_Cart_create/rank/coords/shift/sub

Topologas
IF - EHU
1. Introduccin.
ndice
IF - EHU
MPI
117 3
Algunas aplicaciones utilizan y generan una gran
cantidad de datos, por lo que el tiempo necesario
para las operaciones de I/O puede ser muy
elevado (comparable o mayor que el tiempo estricto de
ejecucin).
Algunos campos en los que se procesan datos de
manera intensiva:
> minera de datos: grano fino / patrones de acceso no predecibles
> multimedia: grano grueso / predecibles
> clculo cientfico: grano fino - grueso / predecibles o no
Entrada/salida paralela
IF - EHU
MPI
118 3
Estructura tpica serie:
un disco conectado al procesador (servidores, sistema RAID)
datos en diferentes formatos
acceso secuencial / aleatorio
llamadas estndar (fprintf, fscanf...)
sistema de ficheros NFS
El nmero de datos procesados por unidad de tiempo
es mayor en los sistemas paralelos. Si el sistema de
almacenamiento de datos (discos) no responde
adecuadamente, el rendimiento del sistema global
decaer (Amdahl de nuevo).
IF - EHU
MPI
119 3
Resumen RAID (redundant array independent disks)
objetivos: capacidad (+ disc.), rendimiento (entrelaz.),
fiabilidad (paridad, hamming...)
RAID0: entrelazado de los datos (nivel de subbloque)
entre un conjunto de discos (igual que en la MP)
+ capacidad / + rendimiento / no fiabilidad
RAID1/10 (mirroring): replicacin de datos / entrelazado
- capacidad / rendimiento / fiabilidad
RAID5: entrelazado de los datos / paridad
+ capacidad / + rendimiento / tolerancia a fallos
estructura:
IF - EHU
MPI
120 3
La entrada/salida en paralelo hace referencia a dos
cuestiones:
estructura fsica de los ficheros
> un disco local en cada nodo
I/O local -- almacenamiento temporal
los datos se pueden juntar al final
funciones estndar de I/O en C
> nodos especficos de I/O
mejor rendimiento
funciones paralelas de I/O
IF - EHU
MPI
121 3
estructura lgica de los ficheros
> procesadores escribiendo en el mismo fichero
- los datos de cada proceso se intercalan en el fichero
- MPI-2 parallel I/O
> en ficheros diferentes, que se pueden juntar al final
-- en general, un sistema de ficheros tipo PVFS
La entrada/salida en paralelo hace referencia a dos
cuestiones:
IF - EHU
MPI
122 3
MPI-2 aade un interfaz para el uso compartido de
ficheros en operaciones de entrada/salida.

La lectura y escritura de datos se realiza de forma
similar al envo y recepcin de datos.

Los modos de acceso pueden ser bloqueantes (lo ms
habitual) y no bloqueantes, as como individuales (lo
ms habitual) y colectivos.
IF - EHU
MPI
123 3
Cada proceso tiene una vista del fichero, compuesta
por tres elementos:
- desplazamiento: punto base de los accesos.

- tipo elemental (e-type): tipo de las unidades que forman
el fichero, y que representa la unidad de acceso y
desplazamiento, normalmente un byte.
- filetype: una plantilla de repeticiones del e-type que
indica los datos que pueden ser accedidos por cada proceso
(p.e., los elementos pares/impares de un vector).
La vista por defecto tiene desplazamiento 0, y tipo
elemental y filetype MPI_BYTE.
IF - EHU
MPI
124 3
> MPI_File_open(comm, &filename, amode, info, &fh);
comm: comunicador
filename: nombre del fichero (char)
amode: modo de acceso (int)
info: informacin sobre el fichero (MPI_Info)
(MPI_INFO_NULL)
fh: handle para trabajar con el fichero (MPI_File)
Operaciones bsicas con ficheros:
1. Apertura y cierre del fichero
> MPI_File_close(&fh);
IF - EHU
MPI
125 3
Modos de acceso:
MPI_MODE_RDONLY; _RDWR; _WRONLY;

Se pueden aadir (OR, |) otras opciones:
MPI_MODE_CREATE; _EXCL; _DELETE_ON_CLOSE;
UNIQUE_OPEN; _SEQUENTIAL; _APPEND;

IF - EHU
MPI
126 3
Son funciones colectivas; para acceso a ficheros locales (un
solo proceso) se usa el comunicador MPI_COMM_SELF.
> MPI_File_delete(&filename, info);
Permite borrar un fichero que no est abierto (slo un proceso).
IF - EHU
MPI
127 3
> MPI_File_read(fh, &buf, count, datatype, &status);
Lee de fh count elementos de tipo datatype y los deja en buf.
Utiliza el puntero privado de acceso al fichero (que se actualiza
automticamente).
> MPI_File_read_at(fh, offset, &buf, count,
datatype, &status);
Lee comenzando en la direccin marcada por offset, sin utilizar
ni modificar ningn puntero privado.
2. Lectura de datos
IF - EHU
MPI
128 3
> MPI_File_seek(fh, offset, whence);
Desplaza el puntero offset unidades (bytes) en relacin a la
posicin actual en el fichero (whence = MPI_SEEK_CUR), al
comienzo del fichero (MPI_SEEK_SET), o al final (MPI_SEEK_END).
> MPI_File_set_view(fh, disp, etype, filetype,
drepr, info);
Crea una vista del fichero fh para cada proceso (operacin colec-
tiva); posiciona los punteros particulares de cada proceso en disp
(p.e., funcin del pid). drepr indica el modo de representacin de
datos (ver manual).
2. Manejo de punteros
IF - EHU
MPI
129 3
> MPI_File_get_position(fh, offset);
Devuelve en offset la posicin actual del puntero privado.
2. Manejo de punteros
IF - EHU
MPI
130 3
> MPI_File_write(fh, &buf, count, datatype, &status);
> MPI_File_write_at(fh, offset, &buf, count,
datatype, &status);
Escribe en fh count elementos de buf de tipo datatype. Utiliza
el puntero privado de acceso al fichero (que se actualiza
automticamente).
Escribe en fh a partir de la direccin marcada por offset, sin
utilizar ni modificar ningn puntero privado.
3. Escritura de datos
IF - EHU
MPI
131 3
> MPI_File_sync(fh);
Obliga a escribir en fh datos que todava puedan estar sin escribir.
Es una operacin colectiva que deben realizar todos los procesos
del comunicador.
Existen muchas ms funciones para trabajar con ficheros (ver
manual MPI-2), con el objetivo de conseguir el mayor rendi-
miento posible en aplicaciones en las que el punto clave sean
las operaciones de entrada/salida.
4. Flush de datos
IF - EHU
1. Introduccin.
8. Performance, debugging, profiling
ndice
IF - EHU
MPI
133 3
El objetivo de un programa paralelo es resolver
problemas ms grandes y/o en menor tiempo.
Los parmetros tpicos que miden el rendimiento
de una determinada ejecucin en paralelo son
(N = tam. probl., P = nm. proc.):
speed-up S(N,P) = Ts(N) / Tp(N,P)
eficiencia E(N,P) = S(N,P) / P
La comparacin de tiempos hay que hacerla con el
mejor programa serie, y no con el programa paralelo
ejecutado sobre un procesador.
Performance
IF - EHU
MPI
134 3
Factores que limitan el rendimiento
> parte del cdigo se ejecutar en serie (Amdahl)
- a tamao constante S 1 / (1-f)
- a tiempo constante S f * p
S debera estar entre 0 y P (E, entre 0 y 1)
S = P es el caso ideal. En todo caso, lo mejor es que S
sea una funcin lineal de P (escalabilidad).
pero puede ser que S < 1! (peor que el caso serie)
S > P?? Influyen otros factores; por ejemplo, el hecho
de que el sistema de P procesadores tenga P veces ms
memoria que un solo procesador.
Performance
IF - EHU
MPI
135 3
ts + N/B
ts = latencia (start-up)
B = ancho de banda
N = datos a transmitir
Cuando se ejecuta el cdigo en paralelo, hay que hacer ms
cosas que simplemente ejecutar clculo. Lo principal, la
comunicacin entre procesos (y las operaciones de
entrada/salida).

Tp(N,P) = T_calc(N,P) + T_com(N,P) + (T_io)
Performance
IF - EHU
MPI
136 3
Comunicacin
Tc = ts + N/B
0
1000
2000
3000
4000
5000
0
1000 2000 3000 4000 5000
Tc
N
ABreal = N / Tc =
= B / (1 + B*ts/N)
(x 1/B)
0
0.2
0.4
0.6
0.8
1
1 10 100 1000 10
4
10
5
ABreal
N
Performance
IF - EHU
MPI
137 3

> clculo extra (replicado)
> tiempos muertos (load balancing) (+ Tidle)

Tp(N,P) = Tcal(N,P) + Tcom(N,P) + Tidle + (Tio)
Es til/necesario solapar clculo y comunicacin
en cada proceso:
(a) comunicaciones no bloqueantes.
(b) procesadores especficos de comunicacin.
Performance
IF - EHU
MPI
138 3
Hay que elegir el algoritmo adecuado al problema,
teniendo en cuenta el tiempo de respuesta.

Error: cambiar un buen algoritmo secuencial por un
algoritmo paralelo... desastroso!
Hay que analizar con cuidado el reparto de datos a
los procesadores (localidad).

Error: suponer que las operaciones de coma flotante son
asociativas (reducciones).
Performance
IF - EHU
MPI
139 3
Intentar reducir el efecto de la latencia en la
comunicacin:

Agrupar datos en los envos.
Aumentar el tamao de grano de las tareas.

Utilizar las diferentes estrategias de gestin de los
mensajes para reducir los tiempos muertos en la
comunicacin (handshake).
Error: no tomar en consideracin las limitaciones de
buffering del sistema (dep. de la mquina!).
Performance
IF - EHU
MPI
140 3
Algunas ideas sobre debugging de programas
paralelos:
es ms difcil; un error puede no corresponder a un
proceso, sino a una secuencia de acciones en diferentes
procesos.
es imposible predecir el comportamiento de un
programa errneo, ya que los resultados cambian de
ejecucin a ejecucin y de sistema a sistema.
la gran mayora de los errores no tienen nada
que ver con el paralelismo.

Debugging
IF - EHU
MPI
141 3
Procedimiento a seguir:
1. Hacer una versin serie del programa.
Disear previamente el programa antes de escribir
cdigo, seguir un proceso incremental de pruebas,
mejor ser claro que original...
Utilizar las herramientas de depuracin de programas
serie (por ejemplo, gdb).
2. Tras disear el programa paralelo, probarlo en un
solo procesador.
3. Si es correcto, probarlo con ms procesadores.
Debugging
IF - EHU
MPI
142 3
Los problemas especficos estn relacionados casi
siempre con la sincronizacin de los procesos:
Carreras (races)
Los programas paralelos pueden ofrecer resultados no
deterministas, que cambian de ejecucin a ejecucin.
Bloqueos (deadlocks)
Los procesos se bloquean en operaciones de
comunicacin que no se completan. Por ejemplo:
+ intentar recibir datos con Recv pero no enviarlos.
+ parmetros no correctos en las funciones de
comunicacin: direcciones de origen/destino, tags...
Debugging
IF - EHU
MPI
143 3
Ante un determinado problema, tres lneas a seguir:
1. Leer el cdigo detenidamente, e intentar deducir
cmo se comporta el programa paralelo (si es sencillo y
sabemos ms o menos dnde puede estar el error).
2. Tracear el programa mediante (printf); etiquetar los
mensajes con el nodo y hacer flush(stdout);...
Ojo: la introduccin de trazas puede modificar el
comportamiento del programa.
Es til imprimir los parmetros de comunicacin antes de
enviar los mensajes y cuando se reciben.
Debugging
IF - EHU
MPI
144 3
3. Usar un debbuger simblico: TotalView, gdb...
Casi todas las funciones MPI devuelven un cdigo que
puede ayudar a identificar problemas.
Manejadores de errores (error handler, EH)
- MPI_ERRORS_ARE_FATAL: el programa aborta.
- MPI_ERRORS_RETURN: devuelve un cdigo de error.
Los EH estn asociados a los comunicadores (recuerda que un
comunicador puede llevar parmetros cacheados, como, por
ejemplo, una topologa). Un ejemplo:
Debugging
Ante un determinado problema, tres lneas a seguir:
IF - EHU
MPI
145 3
int cod_err;
cod_err = MPI_Errhandler_set (MPI_COMM_WORLD,
MPI_ERRORS_RETURN);

char mens_err[MPI_MAX_ERROR_STRING];
int long_mens;

cod_err = MPI_Broadcast (&x, 1, MPI_INT, 0, comm);
if (cod_err != MPI_SUCCESS) {
MPI_Error_string (cod_err, mens_err, &long_mens);
fprintf (stderr, Error BC = %s\n, mens_err);
fprintf (stderr, Agur Benhur\n);
MPI_Abort (MPI_COMM_WORLD, -1); // -1: error_code
}
Debugging
IF - EHU
MPI
146 3
De cara a mejorar el rendimiento del programa,
tenemos que identificar qu partes del mismo son las
responsables de la mayor parte del tiempo de
ejecucin: hay que obtener un perfil.

Obviamente, para obtener un buen rendimiento debemos
de partir de un buen algoritmo.
Hay que medir tiempos:
- gettimeofday, MPI_Wtime
- barreras (?)
- modificar las funciones MPI, para incluir toma de tiempos
(PMPI)
Profiling
IF - EHU
MPI
147 3
Usar alguna herramienta especfica de profiling:

gprof (serie)

TotalView, Paragraph, Pablo, Vampir, Paradyne
(INTEL, KAI, Porland, PALLAS)

jumpshot (xmpi / lam)

Se puede analizar el tiempo de ejecucin de cada funcin MPI,
los patrones de comunicacin...
Profiling
IF - EHU
MPI
148 3
Jumpshot es una aplicacin que permite analizar
grficamente el comportamiento de programas
paralelos (MPICH / MPE) que se han ejecutado
previamente y de los que se ha obtenido un fichero
tipo log.

Para generar el fichero log podemos aadir puntos de
muestreo en lugares concretos (aadiendo funciones de
MPE), o, en casos sencillos, tomar datos de todas las
funciones MPI:

> mpicc mpe=mpilog o p1 p1.c
> mpiexec n num_proc p1
Jumpshot
IF - EHU
MPI
149 3
Al ejecutar el programa se genera el fichero p1.clog2,
que, transformado a formato slog2, puede analizarse
mediante jumpshot4

> clog2TOslog2 p1.clog2
> jumpshot
Veamos unos ejemplos de uso de jumpshot.
Jumpshot
IF - EHU
Hemos analizado las funciones principales de MPI,
pero hay ms.
Por ejemplo, MPI-2 permite generar procesos de
manera dinmica, y no solamente de manera
esttica, tal como hemos hecho a lo largo del curso.
Tambin existen operaciones de comunicacin one-
sided (put, get) que permiten a un proceso acceder
a la memoria local de otro (con lo que podramos
utilizar un modelo de memoria compartida!).
Comunicacin one-sided
IF - EHU
En la mayora de los clusters, cada nodo es un pequeo
multiprocesador (4-8 procesadores), o un procesador de
cuatro a ocho ncleos con multithreading.

En esos casos es interesante utilizar simultneamente los
dos modelos: MPI (paso de mensajes entre nodos de
memoria privada) y OpenMP (hilos de memoria compartida).
Basta con aadir a los procesos MPI las correspondientes
directivas OpenMP, de tal manera que la tarea asignada a
cada nodo se reparta entre los procesadores locales.
Atencin al modelo de memoria (variables privadas y
compartidas), que es diferente en cada caso.
MPI-OpenMP
IF - EHU
> MPI

P. S. Pacheco: Parallel Programming with MPI.
Morgan Kaufmann, 1997.

W. Gropp et al.: Using MPI. Portable Parallel Programming
with the Message Passing Interface.
Using MPI-2. Advanced Features of the Message Passing
Interface. The MIT Press, 1999.

M. Snir et al.: MPI - The complete reference (vol. 1 /2).
The MIT Press, 1998.

mpich: www-unix.mcs.anl.gov/mpi/
lam: www.lam-mpi.org
Referencias
IF - EHU
> Gestin de un cluster

T. Sterling: Beowulf Cluster Computing with Linux.
The MIT Press, 2002

J.D. Sloan: High Performance Linux Clusters with OSCAR,
Rocks, openMosix & MPI.
OReilly, 2005
Referencias

LP Mpi

Cargado por

Copyright:

Formatos disponibles

LP Mpi

Cargado por

Información del documento

Título original

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

LP Mpi

Cargado por

Copyright:

Formatos disponibles

Laboratorio de Paralelismo

También podría gustarte