proPar
Curso 15/16
4
1 Computadores Paralelos
4
2 Programación basada en paso de mensajes
3 Técnicas básicas de programación paralela
2, 3, 2 Compulsiva, Divide y Vencerás, Pipeline,
2, 2
5
Síncrona, Equilibrado de carga y Terminación
4 Programación basada en memoria común
5 Algoritmos y aplicaciones
4
Ordenación, …
Procesamiento Paralelo
Temario
pasoMsj-2
2 PROGRAMACIÓN BASADA EN PASO DE MENSAJES
1 Recordar concurrencia pthreads: contar y descifrar
2 Un modelo de paso de mensajes
• Opciones de programación
• Creación de procesos
• Rutinas genéricas de paso de mensajes
3 MPI
• Introducción
• Procesos
• Envío y recepción de mensajes
• Comunicación colectiva
4 Evaluación de programas paralelos
5 Herramientas de depuración y monitorización
proPar
Recordar concurrencia pthreads
pasoMsj-3
• contarPar.c: Número de apariciones de un número en un vector
6 2 0 7 4 9 3 4 9 8 0 6 7 9 6 0 6 7 9 8 6 2 5 2 6 4 7 9 3 5 2 1 7 3 2 6 6 4 4 0
T1
1
T2
T3
3
2
T4
2
+
8
const
N
= 40;
objetivo = 6;
numCPUs = 4;
var
vector array[1..N] of integer;
¿ Algoritmo paralelo ?
proPar
Recordar concurrencia pthreads
pasoMsj-4
int longRodaja, numVecesLocal[MAX_ESCLAVOS], *vector;
void *esclavo (void *parametro) { ..... }
%cuentaPar 1000000 4
int main (int argc, char *argv[]) {
int i, numVeces, cardinalidad = atoi (argv[1]);
int
numEsclavos = atoi (argv[2]);
pthread_t pids[MAX_ESCLAVOS];
// Pedir memoria e inicializar vector
// Crear esclavos y esperar a que terminen su trabajo
for (i = 0; i < numEsclavos; i++)
pthread_create (&pids[i], NULL, esclavo, (void *) i);
for (i = 0; i < numEsclavos; i++)
pthread_join (pids[i], NULL);
// Sumar los valores de todos e informar del resultado
numVeces = numVecesLocal[0];
for (i = 1; i < numEsclavos; i++)
numVeces = numVeces + numVecesLocal[i];
printf (“Veces que aparece = %d\n”, numVeces);
}
proPar
Recordar concurrencia pthreads
pasoMsj-5
// Variables globales
int longRodaja, numVecesLocal[MAX_ESCLAVOS], *vector;
void *esclavo (void *parametro) {
int yo, inicio, fin, i, j, numVeces;
yo = (int) parametro;
inicio = yo
* longRodaja;
fin
= inicio + longRodaja;
// Buscar en mi parte del vector
numVeces = 0;
for (i = inicio, i < fin; i++)
if (vector[i] == NUM_BUSCADO) numVeces++;
numVecesLocal[yo] = numVeces;
pthread_exit (NULL);
}
proPar
Recordar concurrencia pthreads
cuentaPar 400.000.000 1..8
// Recorriéndolo diez veces
Esclavos Tiempo Aceleración Eficiencia
1
5,480
2
2,721
2,01
1,01
4
1,408
3,89
0,97
5
6
7
8
1,286
1,127
1,113
0,998
pasoMsj-6
4,26
4,86
4,92
5,49
0,85
0,81
0,70
0,69
2 Xeon E5520 Quad
2,26GHz • 8ML3 • 12GB • 500GB
proPar
Recordar concurrencia pthreads
pasoMsj-7
• descifra.c: Descifrar una clave basada en “crypt”
char *crypt(const char *key, const char *salt);
crypt (“abrir”, “aa”) => “aaHUVtmrCqHAw”
crypt (“ajaja”, “aa”) => “aaCV68P63epR6”
crypt (“clave”, “aa”) => “aa80JYxYfBfpI”
5 letras
|a..z| = 26
aaaaa .. zzzzz claveCruda
if (crypt (claveCruda, “aa”)
== claveCifrada)
encontrada
else siguiente (claveCruda)
claveCifrada
¿ aaSjbUR3erIrQ ?
¿ Paralelo ?
proPar
Recordar concurrencia pthreads
pasoMsj-8
• descifraPar.c: Descifrar una clave basada en “crypt” 4 núcleos
?
?
?
aaaaa
zzzzz
• ¿Qué claves a cada proceso?
0 aaaaa .. fzzzz
aaaaa, aaaae, ..
1 gaaaa .. lzzzz
aaaab, aaaaf, ..
2 maaaa .. szzzz
aaaac, aaaag, ..
aaaad, aaaah, ..
3 taaaa .. zzzzz
saltoRana
• ¿Cómo terminar?
varComún
encontrada
proPar
Recordar concurrencia pthreads
#define MAX_ESCLAVOS 16
#define FRECUENCIA_MUESTREO 1000
//------------- VARIABLES GLOBALES --------------------------------int encontrada, numEsclavos;
char cifradaBuscada [LONG_CLAVE_CIFRADA+1];
static
int
int
char
char
void esclavo (int yo) {
i;
totalClaves, iMiPrimeraClave, clavesPorEsclavo;
clave [LONG_CLAVE_CRUDA+1];
cifradaActual [LONG_CLAVE_CIFRADA+1];
// Inicializaciones
totalClaves = numClavesPosibles();
clavesPorEsclavo = totalClaves / numEsclavos;
iMiPrimeraClave = (yo-1) * clavesPorEsclavo;
if (yo == (numEsclavos))
clavesPorEsclavo = totalClaves - iMiPrimeraClave;
// Busqueda en mi trozo del espacio de claves
claveCrudaIesima (iMiPrimeraClave, clave);
for (i=0; i<clavesPorEsclavo; i++) {
if (((i%FRECUENCIA_MUESTREO) == 0) && encontrada) break;
cifrar (clave, cifradaActual);
if (strcmp (cifradaActual, cifradaBuscada) == 0) {
encontrada = TRUE;
printf ("%s ", clave);
break;
}
siguienteClaveCruda (clave);
}
}
pasoMsj-9
proPar
Recordar concurrencia pthreads
int main(int argc, char *argv[]) {
int numClaves, i;
struct timeval t0, tf, t;
pthread_t pids[MAX_ESCLAVOS];
¡¡ No la encuentran !!
crypt()
numEsclavos = atoi(argv[2]);
numClaves
= abrir (argv[1]);
// Inicializacion
if (leerClaveCifrada (cifradaBuscada) != 0) {
printf ("La clave no es correcta \n");
return 0;
}
gettimeofday (&t0, NULL);
No reentrante
crypt_r()
encontrada = FALSE;
// Crear esclavos y esperar a que terminen su trabajo
for (i=1; i<=numEsclavos; i++)
pthread_create (&pids[i], NULL, esclavo, (void *) i);
for (i=1; i<=numEsclavos; i++)
pthread_join (pids[i], NULL);
gettimeofday (&tf, NULL);
timersub (&tf, &t0, &t);
printf ("Tiempo => %ld:%ld seg:mseg\n", t.tv_sec, t.tv_usec/1000);
return 0;
}
pasoMsj-10
proPar
Recordar concurrencia pthreads
PC9: 2 Xeon E5520 Quad 2,26GHz
claves
secuencial 2 Threads
4 Threads
aaaaa
0:000
0:000
0:000
galas
10:819
11:114
10:905
hojas
13:571
13:654
1:991
musas
23:065
23:208
11:735
nadas
23:420
0:016
0:015
pumas
28:406
5:635
5:042
tizas
34:818
11:761
11:799
tomos
35:196
11:991
0:109
vasos
37:842
14:594
2:912
zzzzz
46:796
23:487
11:857
Total
253:933
115:460
56:365
pasoMsj-11
proPar
Opciones de programación
pasoMsj-12
Entornos de programación paralela en los 90 “Tim Mattson - Intel”
proPar
Opciones de programación
pasoMsj-13
2005
1 A Pattern Language for Parallel Programming
2 Background and Jargon of Parallel Computing
3 The Finding Concurrency Design Space
4 The Algorithm Structure Design Space
5 The Supporting Structures Design Space
6 The Implementation Mechanisms Design Space
7 A Brief Introduction to OpenMP
8 A Brief Introduction to MPI
9 A Brief Introduction to Concurrent Programming in Java
proPar
Opciones de programación
pasoMsj-14
1. Diseño específico de un lenguaje: Occam  Transputer
2. Extensión de lenguaje existente: Fortran M, CC++, Cilk++
www.netlib.org/fortran-m
OpenMP
www-unix.mcs.anl.gov/dbpp/text/node51.html
www.cilk.com
3. Biblioteca de paso de mensajes sobre C, Fortran, C++
PVM:
www.csm.ornl.gov/pvm
MPI:
www-unix.mcs.anl.gov/mpi
HPC++: www.extreme.indiana.edu/hpc++/index.html
Paralelización automática: El compilador extrae
paralelismo del código secuencial
¿ Sistema
Operativo ?
Opciones … (TRANSPUTER)
proPar
1979 Proyecto Europeo: Inmos
pasoMsj-15
SGS-Thomson
ICL ... †
Objetivo: µP de altas prestaciones, como elemento básico para
construir máquinas paralelas (multicomputadores)
1992: habían vendido 500.000 unidades (µP+1MB => 180.000pts)
Característica relevante: 4 enlaces de comunicación (canales)
1
0 T800 2
3
Ejecución eficiente de n procesos que
envían/reciben mensajes por canales
P1
P3
P2
cP3 ! dato
cP2 ? dato
proPar
Creación de procesos
pasoMsj-16
• ¿Cómo podría ser contarPar.c si no hay memoria común?
maestro
620… 067… 625… 217…
1
3
2
+
620… 067… 625… 217…
2
1
8
3
2
2
esclavo1
esclavo2
esclavo3
esclavo4
620…
067…
625…
217…
• El vector lo tiene un proceso “maestro”
2 tipos distintos
de procesos
• El maestro: reparte “envía” trabajo a los “esclavos” y
recoge “recibe” resultados
proPar
Creación de procesos
pasoMsj-17
• ¿Cómo podría ejecutarse la aplicación?
maestro
esclavo1
esclavo2
esclavoN
maestro.exe
esclavo.exe
maestro.c
esclavo.c
maestro.exe
esclavo.exe
Un proceso x núcleo
M
E
E
E
¿ SPMD ?
¿Arquitecturas distintas?
MPMD Multiple Program
• Dos ejecutables: maestro.exe y esclavo.exe
Multiple Data
• Creación de procesos: estática vs dinámica
proPar
Creación de procesos (creación dinámica)
pasoMsj-18
• MPMD: Multiple Program Multiple Data
maestro.c
esclavo.c
--------------------------spawn (“esclavo”, 4, ...)
---------------------------
--------------------------contarEnTrozo (......)
---------------------------
maestro
%pvm
pvm>add PC2 .....
pvm>spawn maestro
esclavo
M
E
E
proPar
Creación de procesos (creación estática)
pasoMsj-19
• SPMD: Single Program Multiple Data
M
E
programa
fuente
0
*.exe
1
*.exe
8
*.exe
sort.c
--------------------------if (miIdProceso == 0)
maestro()
else
esclavo()
---------------------------
%mpirun –np 9 sort
%mpirun –p4pg
fiConf sort
proPar
Creación de procesos
pasoMsj-20
• A veces, viene bien que el maestro también trabaje
maestro0
620… 067… 625… 217…
1
3
2
2
esclavo1
esclavo2
esclavo3
067…
625…
217…
• Modelo SPMD y creación de procesos estática
proPar
Rutinas genéricas de paso de mensajes
pasoMsj-21
• Pi.enviar(Pj, &msj, ...)  Pj.recibir(Pi, &msj, ...)
sortM
--------------------------enviar (esclavo,
&rodaja[k], ...)
---------------------------
Varias semánticas:
• Máquina
• PID_Local
sortE
--------------------------recibir (maestro,
&miRodaja, ...)
---------------------------
enviar( Pi, &msj, temporización, )
• Bloqueante (Síncrona | Rendezvous)
• No bloqueante (Asíncrona: Capacidad de almacenar)
• Temporizada (Tiempo máximo de bloqueo)

0
t
proPar
Rutinas genéricas de paso de mensajes
• Bloqueante
------------------enviar...
-------------------
vs
------------------recibir...
-------------------
pasoMsj-22
NoBloqueante
------------------enviar...
-------------------
¿ Dónde ?
Buffer
------------------recibir...
-------------------
El primero se bloquea
Transferencia sin
buffers adicionales
Se desacopla env | rec
Se sabe que se ha recibido
¿Se ha recibido? => msjACK
Gestión de buffers
enviar( Pi, &msj, temporización, ...)
proPar
Rutinas genéricas de paso de mensajes
pasoMsj-23
• recibirDeCualquiera (&msj) | recibir ( -1, &msj)
sortM
sortE1
sortEn
sortM
--------------------------quien = recibir (-1,
&rodaja[k], ...)
---------------------------
• Mensajes etiquetados
Cliente
H P P P P P P P
Cliente
Servidor
Cliente
enviar (S, &msj, tipoP)
enviar (S, &msj, tipoH)
recibir (-1, &msj, tipoH)
recibir (-1, &msj, -1 )
Paso de mensajes entre “grupos”
proPar
pasoMsj-24
• Broadcast (a todos) Multicast (a unos concretos)
Problema: Número de ocurrencias de (un dato)* en array grande
“Ala”
“Ala”
cuentaE1
cuentaM
cuentaE2
cuentaM
--------------------------Para todo esclavo
enviar (esclavo,
&palabra, ...)
---------------------------
¿Más eficiente?
¿Sincronismo?
“Ala”
cuentaEn
cuentaM
--------------------------bcast (esclavos,
&palabra, ...)
---------------------------
Paso de mensajes entre “grupos”
proPar
pasoMsj-25
• scatter ( esparcir ) y gather ( recoger ) Ej: Ordenación
sortM
sortM
V
sortE1
V
sortEn
sortM y sortE
scatter (V, rodaja, grupo, emisor, )
sortE1
sortEn
sortM y sortE
gather (V, rodaja, grupo, receptor, )
proPar
Paso de mensajes entre “grupos”
int V[N];
pasoMsj-26
int R[longRodaja];
inic(V);
recibir (0, R, longRodaja);
i=0;
ordenar (V, longRodaja);
for (e=1; e<=nProc; e++) {
enviar (0, R, longRodaja);
enviar (e, &V[i], longRodaja);
i += longRodaja;
}
ordenar (V, longRodaja);
i=0;
for (e=1; e<=nProc; e++) {
recibir(e, &V[i], longRodaja);
i += longRodaja;
}
int *V;
if (yo==0) { V = malloc(N); inic(V); }
else
V = malloc(longRodaja);
scatter (V, V, grupo, 0);
ordenar (V, longRodaja);
gather (V, V, grupo, 0);
Paso de mensajes entre “grupos”
proPar
pasoMsj-27
• reduce (recibir de unos concretos y operar) Ej: Ocurrencias
cuentaM
3
¿Más eficiente?
+
2
cuentaE1
5
cuentaE2
cuentaM
Total = veces;
Para todo esclavo
recibir (esclavo,
&veces, ...)
Total += veces;
1
cuentaEn
cuentaM y cuentaE
reduce (+, &veces, grupo, receptor, ...)
máximo, mínimo, *, .....
proPar
MPI (Introducción)
pasoMsj-28
MPI: Message Passing Interface – 1994 MPI Forum [Nov/92]
“Ejecución de aplicaciones paralelas
distribuidas en ordenadores heterogéneos”
MPI-2
MPI-3
• Biblioteca “mpi.h”
MPI_Send,
MPI_Recv,
-------------
maestro
esclavo1
M
esclavo2
E1
esclavo3
E2
esclavo4
E3
E4
• Implementación
MPICH
LAM/MPI
IBM, …
Cada uno con su dirIP
proPar
MPI (Procesos)
pasoMsj-29
• Creación estática de procesos (según implementación “mpirun”)
int MPI_Init( ....... ); /* Inicia MPI */
int MPI_Comm_size(…, int *numProcesos);
5
int MPI_Comm_rank(…, int *yo);
int MPI_Finalize();
2
0
1
2
>= 0 => MPI_SUCCESS, significado concreto
< 0 => un error ( ... MPI_ERR_ARG ...)
3
4
MPI_COMM_WORLD
proPar
MPI (Procesos)
pasoMsj-30
• helloWorld paralelo
#include “mpi.h”
int main (int argc,
char *argv[]) {
int yo, numProcesos;
% mpirun –np 3 helloWorld
MPI_Init (&argc, &argv);
MPI_Comm_size (MPI_COMM_WORLD, &numProcesos);
MPI_Comm_rank (MPI_COMM_WORLD, &yo);
if (yo == 0) printf (“Creados %d procesos\n”, numProcesos);
printf (“Hola, soy el proceso %d\n”, yo);
MPI_Finalize();
}
% mpirun –p4pg helloWorld.txt helloWorld
pc1 2 /usuarios/alumnosPropar/propar01/p1/helloWorld
pc2 2 /usuarios/alumnosPropar/propar01/p1/helloWorld
pc3 1 /usuarios/alumnosPropar/propar01/p1/holaMundo
proPar
MPI (Envío y Recepción Simple)
pasoMsj-31
• Enviar y recibir arrays de datos simples (int, byte, ...) Bloqueante
P1
P2
int vector[N];
---------MPI_Send (vector, …
P2, ...)
----------
int tabla[M];
---------MPI_Recv (tabla, …
P1, ...)
----------
int MPI_Send(void *buffer, int cuantos, MPI_Datatype tipo,
int destino, int etiqueta, MPI_Comm grupo)
MPI_COMM_WORLD
0..MPI_TAG_UB
MPI_INT,
MPI_FLOAT, …
proPar
MPI (Envío y Recepción Simple)
pasoMsj-32
• Enviar y recibir arrays de datos simples (int, byte, ...) Bloqueante
int MPI_Recv(void *buffer, int cuantos, MPI_Datatype tipo,
int remitente,int etiqueta,MPI_Comm grupo,
MPI_Status *estado)
MPI_ANY_SOURCE
MPI_ANY_TAG
estado.MPI_SOURCE
estado.MPI_TAG
int MPI_Get_count( MPI_Status *estado, MPI_Datatype tipo,
int *cuantos)
proPar
MPI (Envío y Recepción Simple)
• Ejemplo de uso: psendrec.c
#include <stdio.h>
#include <unistd.h>
#include “mpi.h"
#define N
3
#define VECES 5
void esclavo(void) {...}
void maestro(void) {...}
int main( int argc, char *argv[] ) {
int yo;
MPI_Init (&argc, &argv);
MPI_Comm_rank (MPI_COMM_WORLD, &yo);
if (yo == 0) maestro();
else
esclavo();
MPI_Finalize();
return 0;
}
pasoMsj-33
proPar
MPI (Envío y Recepción Simple)
pasoMsj-34
• Ejemplo de uso: psendrec.c
void maestro (void) {
int i, j, vector[N];
for (i=0; i<VECES; i++) {
printf ("M: envia => ");
for (j=0; j<N; j++) {
vector[j] = i*N+j;
esclavo
printf("%d ", vector[j]);
}
printf ("\n");
MPI_Send (vector, N, MPI_INT, 1, 1, MPI_COMM_WORLD);
}
}
proPar
MPI (Envío y Recepción Simple)
• Ejemplo de uso: psendrec.c
void esclavo(void) {
int i, j,tabla[N], n;
MPI_Status estado;
maestro
sleep(2);
for (i=0; i<VECES; i++) {
MPI_Recv (tabla, N, MPI_INT, 0, 1,
MPI_COMM_WORLD, &estado);
MPI_Get_count (&estado, MPI_INT, &n);
printf ("E: recibe => ");
for (j=0; j<N; j++) printf("%d ", tabla[j]);
printf (" de tid = %d eti = %d longi = %d\n",
estado.MPI_SOURCE, estado.MPI_TAG, n);
}
}
pasoMsj-35
proPar
MPI (Envío y Recepción No Tan Simple)
pasoMsj-36
• Enviar y recibir arrays de datos simples No Bloqueante
int MPI_Iprobe(int origen, int etiqueta, MPI_Comm grupo,
int *hayMsj, MPI_Status *estado)
NO
SI
Hacer otras cosas
int MPI_Recv(void *buffer,… MPI_Status *estado)
• Enviar y recibir datos no homogéneos
Crear tipos => Algo tedioso
proPar
MPI (Comunicación colectiva)
“Ala”
“Ala”
cuenta.1
cuenta.2
pasoMsj-37
cuenta.0
“Ala”
cuenta.N
int MPI_Bcast(void *buffer, int cuantos,
MPI_Datatype tipo, int emisor,
Send+Recv MPI_Comm grupo)
?
void maestro () {
char palabra[4];
---------MPI_Bcast (
palabra, 4, MPI_CHAR,
0, MPI_COMM_WORLD);
----------
tag
void esclavo () {
char texto[4];
---------MPI_Bcast (
texto, 4, MPI_CHAR,
0, MPI_COMM_WORLD);
----------
proPar
MPI (Comunicación colectiva)
pasoMsj-38
sendCount
grupoM.0
grupoE.1
int MPI_Scatter(
void *vOrg, int nOrg, MPI_Datatype tOrg,
void *vDst, int nDst, MPI_Datatype tDst,
int emisor, MPI_Comm grupo);
grupoE.9
+
MPI_SUM, MPI_PROD,
MPI_MIN, MPI_MAX, ....
int MPI_Reduce(void *vOrg, void *vDst, int nOrg,
MPI_Datatype tDatoOrg, int operacion,
int receptor, MPI_Comm grupo);
proPar
MPI (Comunicación colectiva: Ejemplo)
pasoMsj-39
• Ejemplo de uso completo: cuentaPar2.c (modelo SPMD)
#include <stdio.h>
#include “mpi.h"
#define CARDINALIDAD 2000000
#define MAX_ENTERO
1000
#define NUM_BUSCADO
5
int main( int argc, char *argv[] ) {
int i, numVeces, numVecesTotal, yo;
int longRodaja, numProcesos;
int *vector;
MPI_Init (&argc, &argv);
MPI_Comm_size (MPI_COMM_WORLD, &numProcesos);
MPI_Comm_rank (MPI_COMM_WORLD, &yo);
--------------------------MPI_Finalize();
}
proPar
MPI (Comunicación colectiva: Ejemplo)
pasoMsj-40
• Ejemplo de uso completo: cuentaPar2.c
// Pedir memoria vector e inicializarlo si maestro
longRodaja = CARDINALIDAD / numProcesos;
if (yo == 0) {
vector = malloc (CARDINALIDAD * 4);
for (i=0; i<CARDINALIDAD; i++)
vector[i] = random() % MAX_ENTERO;
} else
vector = malloc (longRodaja * 4);
MPI_Scatter (vector, longRodaja, MPI_INT,
vector, longRodaja, MPI_INT, 0, MPI_COMM_WORLD);
// Todos buscan en su trozo
numVeces = 0;
for (i=0; i<longRodaja; i++)
if (vector[i] == NUM_BUSCADO) numVeces++;
MPI_Reduce (&numVeces, &numVecesTotal, 1, MPI_INT,
MPI_SUM, 0 , MPI_COMM_WORLD);
if (yo == 0)
printf (“Numero de veces => %d\n”, numVecesTotal);
proPar
MPI (Comunicación colectiva)
pasoMsj-41
• Otras llamadas interesantes:
int MPI_Gather(void *vOrg, int nOrg, MPI_Datatype tOrg,
void *vDst, int nDst, MPI_Datatype tDst,
int receptor, MPI_Comm grupo);
int MPI_Barrier(MPI_Comm grupo);
---------MPI_Comm_size (MPI_COMM_WORLD, &numProcesos);
---------// Computar todos paso 1
MPI_Barrier (MPI_COMM_WORLD);
// Computar todos paso 2
6
proPar
Evaluación de programas paralelos
pasoMsj-42
• ¿Cuánto tardará mi programa paralelo TP?
• Medición experimental
• Estudio analítico
N’
Codificar, Depurar, Probar, ...
Modelo imperfecto, aproximado
m
TP = TCPU + TRED
e0
veces = 0;
for (i=0; i<N’; i++)
if (rodaja[i] == D)
veces++;
N’ * (#i * Tinst)
e9
N
cuentaVeces:
• V[1.000.000]
• 10 esclavos
a. Enviar rodajas
b. Contar veces
c. Recibir veces
TRED
TCPU
TRED
O (N) | O (N2) | O (NlogN) | O(logN)
proPar
Evaluación de programas paralelos
N’ * (#i * Tinst)
TP = TCPU + TRED
#m * (TL + #d * TD)
#msj,
tamaño(#d),
topología red,
tecnología, ...
pasoMsj-43
t
TL
Ejemplos
TL TD[8B] Tinst
TL TD Tinst
T3D+PVM
6
1
3s 63ns 11ns Normalizar 273
IBM PS2+MPI 35s 230ns 4,2ns
8333 55
1
iacluster+MPI 40s 64ns 0,6ns
66666 107 1
TP = TCPU + TRED
Solapar tiempos | ocultar latencias
Comunicación asíncrona
#d
proPar
Evaluación de programas paralelos
pasoMsj-44
• Ejemplo: cuentaVeces, V[1.000.000], 10 esclavos
T1 = 1.000.000 * (#i * Tinst)
T10 = TRED(10Rodajas) + TCPU(100.000) + TRED(10Resultados)
T3D: TL(273) y TD(6)
T10 = 10*(273+100.000*6) + 100.000*#i*1 + 10*(273+6)
= 6.005.520 + 100.000#i
S10 = 1.000.000*#i / (6.005.520+100.000#i)
#i
5
10
500
S10
0,8
1,4
8,9
#i
50
100
500
S10
0,71
1,33
4,34
iacluster: TL(66.666) y TD(64)
T10 = ... 66.666 ... 64 + ...*1 + ... 66.666+64
= 65.333.960 + 100.000#i
S10 = 1.000.000*#i / (65.333.960 +100.000#i)
proPar
Herramientas de depuración y monitorización pasoMsj-45
• Medición de tiempos de ejecución
• Depuración
• Monitorización
#include <sys/time.h>
struct timeval t0, tf, tiempo;
¿Efecto del
optimizador
de código?
gcc –O3
/* Inicialización */
gettimeofday (&t0, NULL);
/* ejecucion del programa paralelo */
gettimeofday (&tf, NULL);
timersub (&tf, &t0, &tiempo);
printf (“Tiempo => %ld:%ld seg:micro\n”,
tiempo.tv_sec, tiempo.tv_usec);
Evitar E/S
proPar
Herramientas de depuración y monitorización pasoMsj-46
%mpirun –dbg=ddd –np 2 psendrec
depurar (ddd)
printf
fflush(stdout)
setbuf(stdout,
NULL)
Depurar más
de un proceso,
algo más
complejo
proPar
Herramientas de depuración y monitorización pasoMsj-47
• Monitorización (XPVM) para PVM
proPar
Herramientas de depuración y monitorización pasoMsj-48
• Monitorización (totalview) para MPI, openMP, … www.etnus.com
www.roguewave.com
proPar
Herramientas de depuración y monitorización pasoMsj-49
• Monitorización VAMPIR www.vampir.eu
FIN
Descargar

Programación basada en paso de mensajes.