PROGRAMACIÓN BASADA EN PASO DE MENSAJES Recordar concurrencia pthreads: contar y descifrar Un modelo de paso de mensajes Opciones de programación Creación de procesos Rutinas genéricas de paso de mensajes MPI Introducción Procesos Envío y recepción de mensajes Comunicación colectiva Evaluación de programas paralelos Herramientas de depuración y monitorización
Recordar concurrencia pthreads contarPar.c: Número de apariciones de un número en un vector (Gp:) 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 (Gp:) const N = 40; objetivo = 6; numCPUs = 4; var vector array[1..N] of integer;
¿ Algoritmo paralelo ? (Gp:) T1 (Gp:) T2 (Gp:) T3 (Gp:) T4
(Gp:) 1 (Gp:) 3 (Gp:) 2 (Gp:) 2
(Gp:) + (Gp:) 8
Recordar concurrencia pthreads (Gp:) int longRodaja, numVecesLocal[MAX_ESCLAVOS], *vector;
void *esclavo (void *parametro) { ….. }
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 = %dn”, numVeces); }
(Gp:) %cuentaPar 1000000 4
Recordar concurrencia pthreads // 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); }
Recordar concurrencia pthreads (Gp:) 5 (Gp:) 1,286 (Gp:) 4,26 (Gp:) 0,85 (Gp:) 6 (Gp:) 1,127 (Gp:) 4,86 (Gp:) 0,81 (Gp:) 7 (Gp:) 1,113 (Gp:) 4,92 (Gp:) 0,70 (Gp:) 8 (Gp:) 0,998 (Gp:) 5,49 (Gp:) 0,69
(Gp:) Esclavos (Gp:) Tiempo (Gp:) Aceleración (Gp:) Eficiencia (Gp:) 1 (Gp:) 5,480 (Gp:) 2 (Gp:) 2,721 (Gp:) 2,01 (Gp:) 1,01 (Gp:) 4 (Gp:) 1,408 (Gp:) 3,89 (Gp:) 0,97
(Gp:) cuentaPar 400.000.000 1..8 // Recorriéndolo diez veces (Gp:) 2 Xeon E5520 Quad 2,26GHz • 8ML3 • 12GB • 500GB
Recordar concurrencia pthreads descifra.c: Descifrar una clave basada en “crypt” (Gp:) char *crypt(const char *key, const char *salt); (Gp:) crypt (“abrir”, “aa”) => “aaHUVtmrCqHAw” crypt (“ajaja”, “aa”) => “aaCV68P63epR6” crypt (“clave”, “aa”) => “aa80JYxYfBfpI”
(Gp:) claveCruda (Gp:) claveCifrada
¿ aaSjbUR3erIrQ ? (Gp:) if (crypt (claveCruda, “aa”) == claveCifrada) encontrada else siguiente (claveCruda) (Gp:) aaaaa .. zzzzz
¿ Paralelo ? (Gp:) 5 letras (Gp:) |a..z| = 26
Recordar concurrencia pthreads descifraPar.c: Descifrar una clave basada en “crypt” 4 núcleos (Gp:) aaaaa (Gp:) zzzzz
(Gp:) ¿Qué claves a cada proceso? (Gp:) 0 (Gp:) 1 (Gp:) 2 (Gp:) 3
(Gp:) aaaaa .. fzzzz (Gp:) gaaaa .. lzzzz (Gp:) maaaa .. szzzz (Gp:) taaaa .. zzzzz
(Gp:) ? (Gp:) ? (Gp:) ?
(Gp:) aaaaa, aaaae, .. (Gp:) aaaab, aaaaf, .. (Gp:) aaaac, aaaag, .. (Gp:) aaaad, aaaah, ..
saltoRana ¿Cómo terminar? (Gp:) encontrada (Gp:) varComún
Recordar concurrencia pthreads #define MAX_ESCLAVOS 16 #define FRECUENCIA_MUESTREO 1000
//————- VARIABLES GLOBALES ——————————— int encontrada, numEsclavos; char cifradaBuscada [LONG_CLAVE_CIFRADA+1];
static void esclavo (int yo) { int i; int totalClaves, iMiPrimeraClave, clavesPorEsclavo; char clave [LONG_CLAVE_CRUDA+1]; char 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); } }
Recordar concurrencia pthreads int main(int argc, char *argv[]) { int numClaves, i; struct timeval t0, tf, t; pthread_t pids[MAX_ESCLAVOS];
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);
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:msegn", t.tv_sec, t.tv_usec/1000); return 0; } ¡¡ No la encuentran !! (Gp:) No reentrante (Gp:) crypt()
(Gp:) crypt_r()
Recordar concurrencia pthreads (Gp:) 2 Threads (Gp:) 0:000 (Gp:) 11:114 (Gp:) 13:654 (Gp:) 23:208 (Gp:) 0:016 (Gp:) 5:635 (Gp:) 11:761 (Gp:) 11:991 (Gp:) 14:594 (Gp:) 23:487 (Gp:) 115:460
(Gp:) 4 Threads (Gp:) 0:000 (Gp:) 10:905 (Gp:) 1:991 (Gp:) 11:735 (Gp:) 0:015 (Gp:) 5:042 (Gp:) 11:799 (Gp:) 0:109 (Gp:) 2:912 (Gp:) 11:857 (Gp:) 56:365
(Gp:) claves (Gp:) aaaaa (Gp:) galas (Gp:) hojas (Gp:) musas (Gp:) nadas (Gp:) pumas (Gp:) tizas (Gp:) tomos (Gp:) vasos (Gp:) zzzzz (Gp:) Total (Gp:) secuencial (Gp:) 0:000 (Gp:) 10:819 (Gp:) 13:571 (Gp:) 23:065 (Gp:) 23:420 (Gp:) 28:406 (Gp:) 34:818 (Gp:) 35:196 (Gp:) 37:842 (Gp:) 46:796 (Gp:) 253:933 (Gp:) PC9: 2 Xeon E5520 Quad 2,26GHz
Opciones de programación (Gp:) Entornos de programación paralela en los 90 “Tim Mattson – Intel”
Opciones de programación (Gp:) 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 (Gp:) 2005
| Página siguiente |