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 |