Opciones de programación Diseño específico de un lenguaje: Occam ? Transputer Extensión de lenguaje existente: Fortran M, CC++, Cilk++ www.netlib.org/fortran-m www-unix.mcs.anl.gov/dbpp/text/node51.html www.cilk.com 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 ? OpenMP
(Gp:) 1979 Proyecto Europeo: Inmos SGS-Thomson ICL … † (Gp:) Objetivo: µP de altas prestaciones, como elemento básico para construir máquinas paralelas (multicomputadores) (Gp:) 1992: habían vendido 500.000 unidades (µP+1MB => 180.000pts) (Gp:) Característica relevante: 4 enlaces de comunicación (canales)
(Gp:) T800 (Gp:) 0 (Gp:) 1 (Gp:) 2 (Gp:) 3
Ejecución eficiente de n procesos que envían/reciben mensajes por canales (Gp:) P1 (Gp:) P2 (Gp:) P3
Opciones … (TRANSPUTER) (Gp:) cP3 ! dato (Gp:) cP2 ? dato
Creación de procesos ¿Cómo podría ser contarPar.c si no hay memoria común? (Gp:) 1 (Gp:) 3 (Gp:) 2 (Gp:) 2 (Gp:) 6 2 0 … (Gp:) 0 6 7 … (Gp:) 6 2 5 … (Gp:) 2 1 7 … (Gp:) + (Gp:) 8
(Gp:) esclavo1 (Gp:) esclavo2 (Gp:) esclavo3 (Gp:) esclavo4
(Gp:) maestro (Gp:) 6 2 0 … (Gp:) 0 6 7 … (Gp:) 6 2 5 … (Gp:) 2 1 7 … (Gp:) El vector lo tiene un proceso “maestro”
El maestro: reparte “envía” trabajo a los “esclavos” y recoge “recibe” resultados (Gp:) 6 2 0 … (Gp:) 0 6 7 … (Gp:) 6 2 5 … (Gp:) 2 1 7 …
(Gp:) 1 (Gp:) 3 (Gp:) 2 (Gp:) 2
(Gp:) 2 tipos distintos de procesos
Creación de procesos (Gp:) ¿Cómo podría ejecutarse la aplicación? (Gp:) maestro (Gp:) esclavo1 (Gp:) esclavo2 (Gp:) esclavoN
(Gp:) Un proceso x núcleo (Gp:) M (Gp:) E (Gp:) E (Gp:) E
Dos ejecutables: maestro.exe y esclavo.exe (Gp:) maestro.c (Gp:) esclavo.c (Gp:) maestro.exe (Gp:) esclavo.exe
(Gp:) Multiple Program Multiple Data (Gp:) MPMD
(Gp:) maestro.exe (Gp:) esclavo.exe
Creación de procesos: estática vs dinámica ¿Arquitecturas distintas? ¿ SPMD ?
Creación de procesos (creación dinámica) MPMD: Multiple Program Multiple Data (Gp:) ————————— spawn (“esclavo”, 4, …) ————————— (Gp:) maestro.c (Gp:) ————————— contarEnTrozo (……) ————————— (Gp:) esclavo.c
(Gp:) maestro
(Gp:) esclavo
(Gp:) %pvm pvm>add PC2 ….. pvm>spawn maestro
M (Gp:) E (Gp:) E
Creación de procesos (creación estática) SPMD: Single Program Multiple Data programa fuente (Gp:) *.exe (Gp:) *.exe (Gp:) *.exe
(Gp:) M (Gp:) E
%mpirun –np 9 sort
%mpirun –p4pg fiConf sort (Gp:) ————————— if (miIdProceso == 0) maestro() else esclavo() ————————— (Gp:) sort.c
(Gp:) 0 (Gp:) 1 (Gp:) 8
Creación de procesos A veces, viene bien que el maestro también trabaje (Gp:) esclavo1 (Gp:) esclavo2 (Gp:) esclavo3 (Gp:) maestro0 (Gp:) 6 2 0 … (Gp:) 0 6 7 … (Gp:) 6 2 5 … (Gp:) 2 1 7 … (Gp:) 0 6 7 … (Gp:) 6 2 5 … (Gp:) 2 1 7 … (Gp:) 1 (Gp:) 3 (Gp:) 2 (Gp:) 2
Modelo SPMD y creación de procesos estática
Rutinas genéricas de paso de mensajes Pi.enviar(Pj, &msj, …) ? Pj.recibir(Pi, &msj, …) (Gp:) ————————— enviar (esclavo, &rodaja[k], …) ————————— (Gp:) sortM (Gp:) ————————— recibir (maestro, &miRodaja, …) ————————— (Gp:) sortE
(Gp:) Máquina PID_Local
Varias semánticas: Bloqueante (Síncrona | Rendezvous) No bloqueante (Asíncrona: Capacidad de almacenar) Temporizada (Tiempo máximo de bloqueo) (Gp:) enviar( Pi, &msj, temporización, ) (Gp:) ? (Gp:) 0 (Gp:) t
Rutinas genéricas de paso de mensajes Bloqueante vs NoBloqueante (Gp:) ———- ———- enviar… ———- ———- (Gp:) ———- ———- recibir… ———- ———-
(Gp:) El primero se bloquea
(Gp:) Transferencia sin buffers adicionales
(Gp:) Se sabe que se ha recibido
(Gp:) ———- ———- enviar… ———- ———- (Gp:) ———- ———- recibir… ———- ———- (Gp:) Buffer
(Gp:) Se desacopla env | rec
(Gp:) Gestión de buffers
(Gp:) ¿ Dónde ?
(Gp:) ¿Se ha recibido? => msjACK
enviar( Pi, &msj, temporización, …)
Rutinas genéricas de paso de mensajes recibirDeCualquiera (&msj) | recibir ( -1, &msj) (Gp:) sortE1 (Gp:) sortEn (Gp:) sortM
(Gp:) ————————— quien = recibir (-1, &rodaja[k], …) ————————— (Gp:) sortM
Mensajes etiquetados P P P P P P P H (Gp:) enviar (S, &msj, tipoP) enviar (S, &msj, tipoH) (Gp:) recibir (-1, &msj, tipoH)
recibir (-1, &msj, -1 ) (Gp:) Cliente (Gp:) Servidor (Gp:) Cliente (Gp:) Cliente
Paso de mensajes entre “grupos” Broadcast (a todos) Multicast (a unos concretos) (Gp:) ————————— Para todo esclavo enviar (esclavo, &palabra, …) ————————— (Gp:) cuentaM
Problema: Número de ocurrencias de (un dato)* en array grande (Gp:) cuentaM (Gp:) cuentaE1 (Gp:) cuentaEn (Gp:) cuentaE2
(Gp:) “Ala” (Gp:) “Ala” (Gp:) “Ala”
(Gp:) ————————— bcast (esclavos, &palabra, …) ————————— (Gp:) cuentaM
¿Más eficiente? ¿Sincronismo?
(Gp:) sortM
(Gp:)
sortE1 (Gp:)
sortEn (Gp:) V
(Gp:) sortM
(Gp:)
sortE1 (Gp:)
sortEn (Gp:) V
Paso de mensajes entre “grupos” scatter ( esparcir ) y gather ( recoger ) Ej: Ordenación (Gp:) scatter (V, rodaja, grupo, emisor, ) (Gp:) sortM y sortE
(Gp:) gather (V, rodaja, grupo, receptor, ) (Gp:) sortM y sortE
Paso de mensajes entre “grupos” int V[N];
inic(V); i=0; for (e=1; e< =nProc; e++) { 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 R[longRodaja];
recibir (0, R, longRodaja); ordenar (V, longRodaja); enviar (0, R, 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);
(Gp:) cuentaM
(Gp:)
cuentaE1 (Gp:) 2 (Gp:) 3 (Gp:)
cuentaE2 (Gp:) 5 (Gp:)
cuentaEn (Gp:) 1
Paso de mensajes entre “grupos” reduce (recibir de unos concretos y operar) Ej: Ocurrencias (Gp:) Total = veces; Para todo esclavo recibir (esclavo, &veces, …) Total += veces; (Gp:) cuentaM
(Gp:) reduce (+, &veces, grupo, receptor, …) (Gp:) cuentaM y cuentaE (Gp:) +
(Gp:) máximo, mínimo, *, …..
¿Más eficiente?
MPI (Introducción) MPI: Message Passing Interface – 1994 MPI Forum [Nov/92] “Ejecución de aplicaciones paralelas distribuidas en ordenadores heterogéneos” (Gp:) maestro (Gp:) esclavo1 (Gp:) esclavo3 (Gp:) esclavo2 (Gp:) esclavo4
Cada uno con su dirIP Biblioteca “mpi.h” MPI_Send, MPI_Recv, ————- (Gp:) M (Gp:) E1 (Gp:) E2 (Gp:) E3 (Gp:) E4
Implementación MPICH LAM/MPI IBM, … MPI-2 MPI-3
(Gp:) >= 0 => MPI_SUCCESS, significado concreto < 0 => un error ( … MPI_ERR_ARG …)
MPI (Procesos) (Gp:) int MPI_Comm_size(…, int *numProcesos); (Gp:) int MPI_Comm_rank(…, int *yo); (Gp:) int MPI_Finalize(); (Gp:) int MPI_Init( ……. ); /* Inicia MPI */
Creación estática de procesos (según implementación “mpirun”) (Gp:) 0 (Gp:) 1 (Gp:) 3 (Gp:) 2 (Gp:) 4 (Gp:) MPI_COMM_WORLD
2 (Gp:) 5
(Gp:) 2
MPI (Procesos) (Gp:) helloWorld paralelo (Gp:) #include “mpi.h” int main (int argc, char *argv[]) { int yo, numProcesos;
MPI_Init (&argc, &argv); MPI_Comm_size (MPI_COMM_WORLD, &numProcesos); MPI_Comm_rank (MPI_COMM_WORLD, &yo); if (yo == 0) printf (“Creados %d procesosn”, numProcesos); printf (“Hola, soy el proceso %dn”, yo); MPI_Finalize(); }
% mpirun –np 3 helloWorld % mpirun –p4pg helloWorld.txt helloWorld (Gp:) pc1 2 /usuarios/alumnosPropar/propar01/p1/helloWorld pc2 2 /usuarios/alumnosPropar/propar01/p1/helloWorld pc3 1 /usuarios/alumnosPropar/propar01/p1/holaMundo
MPI (Envío y Recepción Simple) Enviar y recibir arrays de datos simples (int, byte, …) Bloqueante
int vector[N]; ———- MPI_Send (vector, … P2, …) ———- P1
int tabla[M]; ———- MPI_Recv (tabla, … P1, …) ———- P2 int MPI_Send(void *buffer, int cuantos, MPI_Datatype tipo, int destino, int etiqueta, MPI_Comm grupo) (Gp:) MPI_INT, MPI_FLOAT, …
(Gp:) MPI_COMM_WORLD (Gp:) 0..MPI_TAG_UB
MPI (Envío y Recepción Simple) 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) (Gp:) estado.MPI_SOURCE estado.MPI_TAG
(Gp:) MPI_ANY_SOURCE
(Gp:) MPI_ANY_TAG
(Gp:) int MPI_Get_count( MPI_Status *estado, MPI_Datatype tipo, int *cuantos)
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; }
MPI (Envío y Recepción Simple) 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; printf("%d ", vector[j]); } printf ("n"); MPI_Send (vector, N, MPI_INT, 1, 1, MPI_COMM_WORLD); } } (Gp:) esclavo
MPI (Envío y Recepción Simple) Ejemplo de uso: psendrec.c void esclavo(void) {
int i, j,tabla[N], n; MPI_Status estado;
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 = %dn", estado.MPI_SOURCE, estado.MPI_TAG, n); } } (Gp:) maestro
MPI (Envío y Recepción No Tan Simple) int MPI_Iprobe(int origen, int etiqueta, MPI_Comm grupo, int *hayMsj, MPI_Status *estado) Enviar y recibir arrays de datos simples No Bloqueante Enviar y recibir datos no homogéneos Crear tipos => Algo tedioso (Gp:) Hacer otras cosas (Gp:) NO
(Gp:) int MPI_Recv(void *buffer,… MPI_Status *estado) (Gp:) SI
MPI (Comunicación colectiva) int MPI_Bcast(void *buffer, int cuantos, MPI_Datatype tipo, int emisor, MPI_Comm grupo) (Gp:) cuenta.0 (Gp:) cuenta.1 (Gp:) cuenta.N (Gp:) cuenta.2 (Gp:) “Ala” (Gp:) “Ala” (Gp:) “Ala”
void maestro () { void esclavo () { char palabra[4]; char texto[4];
———- ———- MPI_Bcast ( MPI_Bcast ( palabra, 4, MPI_CHAR, texto, 4, MPI_CHAR, 0, MPI_COMM_WORLD); 0, MPI_COMM_WORLD); ———- ———- (Gp:) ? (Gp:) tag
(Gp:) Send+Recv
MPI (Comunicación colectiva) int MPI_Scatter( void *vOrg, int nOrg, MPI_Datatype tOrg, void *vDst, int nDst, MPI_Datatype tDst, int emisor, MPI_Comm grupo); (Gp:)
grupoE.1 (Gp:)
grupoE.9 (Gp:) grupoM.0
int MPI_Reduce(void *vOrg, void *vDst, int nOrg, MPI_Datatype tDatoOrg, int operacion, int receptor, MPI_Comm grupo); (Gp:) +
(Gp:) MPI_SUM, MPI_PROD, MPI_MIN, MPI_MAX, ….
(Gp:) sendCount
MPI (Comunicación colectiva: Ejemplo) 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(); }
MPI (Comunicación colectiva: Ejemplo) 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 => %dn”, numVecesTotal);
MPI (Comunicación colectiva) 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 (Gp:) 6
Evaluación de programas paralelos ¿Cuánto tardará mi programa paralelo TP? Medición experimental Estudio analítico (Gp:) Codificar, Depurar, Probar, …
(Gp:) Modelo imperfecto, aproximado
(Gp:) m (Gp:) e0 (Gp:) e9 (Gp:) cuentaVeces: V[1.000.000] 10 esclavos
(Gp:) TP = TCPU + TRED
(Gp:) Enviar rodajas TRED
(Gp:) Recibir veces TRED
(Gp:) Contar veces TCPU
(Gp:) veces = 0; for (i=0; i< N’; i++) if (rodaja[i] == D) veces++;
(Gp:) N’ (Gp:) N
(Gp:) N’ * (#i * Tinst)
(Gp:) O (N)
| O (N2) | O (NlogN) | O(logN)
Evaluación de programas paralelos (Gp:) #m * (TL + #d * TD)
(Gp:) #d (Gp:) t (Gp:) TL
(Gp:) TP = TCPU + TRED (Gp:) N’ * (#i * Tinst)
(Gp:) Ejemplos (Gp:) T3D+PVM (Gp:) IBM PS2+MPI (Gp:) iacluster+MPI (Gp:) 40?s (Gp:) 35?s (Gp:) 3?s (Gp:) TL (Gp:) 64ns (Gp:) 230ns (Gp:) 63ns (Gp:) TD[8B] (Gp:) 0,6ns (Gp:) 4,2ns (Gp:) 11ns (Gp:) Tinst
(Gp:) 66666 (Gp:) 8333 (Gp:) 273 (Gp:) TL (Gp:) 107 (Gp:) 55 (Gp:) 6 (Gp:) TD (Gp:) 1 (Gp:) 1 (Gp:) 1 (Gp:) Tinst (Gp:) Normalizar
(Gp:) TP = TCPU + TRED
(Gp:) Solapar tiempos | ocultar latencias Comunicación asíncrona
(Gp:) #msj, tamaño(#d), topología red, tecnología, …
Evaluación de programas paralelos Ejemplo: cuentaVeces, V[1.000.000], 10 esclavos T1 = 1.000.000 * (#i * Tinst) T10 = TRED(10Rodajas) + TCPU(100.000) + TRED(10Resultados) (Gp:) T3D: TL(273) y TD(6) (Gp:) 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)
(Gp:) iacluster: TL(66.666) y TD(64) (Gp:) 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)
(Gp:) #i (Gp:) S10 (Gp:) 50 (Gp:) 0,71 (Gp:) 100 (Gp:) 1,33 (Gp:) 500 (Gp:) 4,34
(Gp:) #i (Gp:) S10 (Gp:) 5 (Gp:) 0,8 (Gp:) 10 (Gp:) 1,4 (Gp:) 500 (Gp:) 8,9
Herramientas de depuración y monitorización Medición de tiempos de ejecución Depuración Monitorización (Gp:) #include < sys/time.h>
struct timeval t0, tf, tiempo;
/* Inicialización */
gettimeofday (&t0, NULL);
/* ejecucion del programa paralelo */
gettimeofday (&tf, NULL); timersub (&tf, &t0, &tiempo); printf (“Tiempo => %ld:%ld seg:micron”, tiempo.tv_sec, tiempo.tv_usec);
(Gp:) Evitar E/S
¿Efecto del optimizador de código? gcc –O3
Herramientas de depuración y monitorización (Gp:) %mpirun –dbg=ddd –np 2 psendrec
Depurar más de un proceso, algo más complejo printf fflush(stdout) setbuf(stdout, NULL) (Gp:) depurar (ddd)
Herramientas de depuración y monitorización Monitorización (XPVM) para PVM
Herramientas de depuración y monitorización Monitorización (totalview) para MPI, openMP, … www.etnus.com (Gp:) www.roguewave.com
| Página siguiente |