Tendencias en el software que complementan las del Hardware Las aplicaciones cada vez son + escalables Muchas nuevas aplicaciones son inherentemente escalables Aplicaciones de búsqueda Minería de datos Ejemplos Servidores de aplicaciones, web, BBDD Google Minería de contenidos multimedia Muchas aplicaciones existentes, middleware y SO están siendo modificadas para ser + escalables: Oracle y apache, pasaron de un modelo basado en procesos a hilos
Ejemplo Arquitectura Software/Hardware escalable (webges) (Gp:)
DB2 UDBMaxappls
CICS SERVER
jdbc + ctg db2jd (Gp:)
DB2 OS/390
(Gp:) power 6 16 cores 32 threads ORACLE
Fonts Dades Servidors Aplicacions Servidors WEB THREAD LIMIT AUTOMAT (Gp:) LDAP server2
Switch Level 4 / pound Balanceig Càrrega (Gp:)
LDAP server1
pugin-cfg.xml RACF OS/390 Z890 FireWall PIX Cisco (Gp:)
(Gp:) Explica
(Gp:)
DB2 persistencia sessions
(Gp:) JVMn (Gp:) JMVx (Gp:) JVM1, JVMx (Gp:) JVMm
AIX pseries 4 cores, 8 threads (power 5) WAS Grid (Gp:) Cluster servidors web Linux/Apache Dual-core AMD
webges01
webges11
Webges..
Soporta + d 500 peticiones x segundo
Programación paralela Según la wikipedia: es una técnica de programación basada en la ejecución simultánea, bien sea en un mismo ordenador (con uno o varios procesadores) o en un cluster de ordenadores, en cuyo caso se denomina computación distribuida. Al contrario que en la programación concurrente, esta técnica enfatiza la verdadera simultaneidad en el tiempo de la ejecución de las tareas. Los sistemas con multiprocesador y multicomputadores consiguen un aumento del rendimiento si se utilizan estas técnicas. En los sistemas monoprocesador el beneficio en rendimiento no es tan evidente, ya que la CPU es compartida por múltiples procesos en el tiempo, lo que se denomina multiplexación o multiprogramación. El mayor problema de la computación paralela radica en la complejidad de sincronizar unas tareas con otras, ya sea mediante secciones críticas, semáforos o paso de mensajes, para garantizar la exclusión mutua en las zonas del código en las que sea necesario. Objetivo: reducir el tiempo de ejecución
Un ejemplo public class MyThread extends Thread{ static final int CPU=5,N=100000000; private int[] A=new int[N]; private int[] B=new int[N]; SynchronizedCounter var=new SynchronizedCounter(); public void run(){ int roll= var.readANDadd(); //Atomic. Avoid condition race with mutex System.out.println("roll="+roll+" n"); for (int i=(roll*(N/CPU)); i < ((roll+1)*(N/CPU));i++){ if ((i % 1000000) == 0) System.out.println("roll= "+roll+" i="+i+" n"); B[i]=i; A[i]=B[i]*i; } } public static void main(String[] args) { for (int i=0;i< CPU;i++) { MyThread worker=new MyThread(); worker.start(); } } public static class SynchronizedCounter { //Binary Object lock private static int c; public synchronized int readANDadd(){ //Not concurrent code. return c++; //First return current value, then increment } } } javac MyThread.java java –Xmx 512 MyThread
Modificación concurrente de datos compartidos Thread 1: load value of i into a register on processor 1 (lets call it r1) [i=1, r1=1] Thread 2: load value of i into a register on processor 2 (lets call it r2) [i=1, r1=1, r2=1] Thread 1: increment r1 by 1 [i=1, r1=2, r2=1] Thread 2: increment r2 by 1 [i=1, r1=2, r2=2] Thread 1: store value in r1 back into i [i=2, r1=2, r2=2] Thread 2: store value in r1 back into i [i=2, r1=2, r2=2]
2 threads intentando incrementar el valor de la variable i=1 (i++) Th 1 i++; (i=2) Th 2 i++; (i=3) Problema: Cuando graben el valor en memoria i=2, cuando tendría q valer 3 ! Solución: Crear una sección crítica de manera q la operación d lectura y incremento sea atómica. ¿Cómo? Mediante semáforos
Solución: Serializar acceso a datos compartidos Cuando N threads modifican los mismos datos en paralelo, el resultado es impredecible Solución: Pasar de ejecución paralela a secuencial con un semáforo Como norma general, los N threads se ejecutaran en paralelo cuando modifiquen “su parte” d datos del problema y en secuencial cuando modifiquen datos compartidos
¿ Para qué sirve la computación paralela ? 2 motivos principales Reducir el tiempo de ejecución Resolver problemas cada vez mas grandes y complejos Otros Utilizar recursos remotos – utilizando recursos disponibles en WAN Reducción de costos – utilizando muchos nodos baratos en vez de un supercomputador caro Salvar las restricciones de memoria – 1 servidor tiene recursos de memoria finitos. Para problemas grandes, utilizando la memoria de N servidores ayuda a superar este obstáculo
Taxonomía Flynn SISD Computador secuencial SIMD Computadores vectoriales (NEC, Fujitsu, Cray), procesadores con instrucciones de extensión multimedia (SSE3, Altivec), GPU’s MIMD Multiprocesadores, clusters, multi-core
Arquitecturas de memoria compartida Espacio de memoria global para todos los procesadores
Ventajas: fácil programación; Desventajas: escalabilidad, precio
Tipos: UMA: Uniform Memory Access NUMA: Non-Uniform Memory Access cc-NUMA: Cache Coherent NUMA
NUMA Acceder de la CPU0 a la memoria d la: CPU0:Muy rápido CPU1:rápido CPU2: rápido CPU3: Menos rápido (2 saltos)
Arquitecturas de Memoria Distribuida Se requiere una red de comunicación para que los procesadores puedan acceder a la memoria no local
Características No existe el concepto de memoria global Procesadores independientes (no coherencia) El programador explicita el intercambio de datos Ventajas: escalabilidad, precio; Desventajas: programación
Arq. Híbridas: Distributed-Shared Memory Combinación de los dos modelos:
Características Cada nodo es un multiprocesador (p.e. cc-NUMA) Comunicación para mover datos de un nodo a otro Actualmente, los supercomputadores suelen seguir este modelo Ejemplos: Multivac, Tirant
Paradigmas de Programación Paralela Principales paradigmas o modelos de programación paralela: Hilos (threads) Paso de mensajes Características: Son una abstracción sobre la arquitectura No hay una relación directa con la arquitectura (p.e. paso de mensajes sobre memoria compartida) cesar.uv.es En debian: apt-cache search mpich-shmem-bin mpich-shmem-bin – MPI parallel computing system implementation, SHMEM version
No se puede hablar de “el mejor paradigma”
Paradigmas de programación paralela Hilos Un proceso puede tener múltiples caminos de ejecución Todos los hilos comparten el mismo espacio de memoria Necesidad de sincronizar el acceso a la memoria mediante semáforos Se utilizan normalmente en arquitecturas de memoria compartida Estándares: Posix Threads: + flexible OpenMP: + sencillo Paso mensajes Un conjunto de tareas que utilizan su propia memoria local para cálculos Diversas tareas pueden residir en la misma máquina física, así como también en un número arbitrario de máquinas distintas (clusters) Las tareas intercambian datos mediante el paso de mensajes Estándares: PVM y MPI
Hilos vs Paso de mensajes Hilos No hay necesidad de comunicación explícita Todos acceden al espacio de datos del problema (memoria compartida) 1 proceso, se encarga de crear los hilos necesarios para balancear la computación necesaria para resolver el problema Paso mensajes 1 proceso se encarga de distribuir (enviando mensajes) los datos del problema a los restantes N-1 procesos remotos Cuando los procesos terminan la computación necesaria para resolver su parte del problema, envían los resultados de vuelta
Metodologías de Programación Paralela Los paradigmas se pueden abordar con diferentes metodologías Paralelización automática (compilador paralelizante) Paralelización semi-automática (directivas de compilador) Lenguajes de programación nuevos Extensión de lenguajes estándar Librerías de subrutinas o funciones (API) Ejemplos OpenMP está basado en directivas MPI y Posix Threads están basados en librerías de funciones
Single/Multiple Program Multiple Data Son modelos de programación de más alto nivel, aplicables a cualesquiera de los paradigmas descritos SPMD: el mismo programa se ejecuta por todas las tareas MPMD: cada tarea puede tener un programa distinto Los programas SPMD son más fáciles de mantener Suelen instrucciones condicionales pid=fork(); if (pid ==0) {printf(“Childn”);}else{printf(“Mastern”);}
Single Program Multiple Data
Esquemas de Programación Paralela La paralelización (manual) suele implicar: Particionado (de datos y/o tareas) Comunicación y/o sincronización En la práctica, hay algunos esquemas de paralelización que aparecen recurrentemente Granja de tareas (maestro-trabajadores) Segmentación (pipelining) Divide y vencerás (encontrar máximo) Otros: Ramificación y poda, algoritmos genéticos, autómatas celulares
Granja de tareas (maestro-trabajadores) Esquema + habitual en prog. paralela Particionado: Repartir el espacio de datos del problema entre N trabajadores Cada uno normalmente ejecuta el mismo código pero sobre su parte de los datos
El maestro se encarga del particionado y la planificación de los trabajadores En memoria compartida no se requiere comunicación para el particionado Necesidad de sincronizar el acceso a la memoria compartida Necesidad de balancear y sincronizar correctamente la ejecución de tareas
Maestro-esclavo con fork() #include < stdio.h> #define N 10 int main(){ int pid,i=0; /* identificador del proceso */ pid = fork(); while (i++ < N){ if ( pid < 0 ) { printf("Cannot fork !!n"); exit(1); } if ( pid == 0 ) { /* Proceso hijo */ printf("I am child number %d n",i); fflush(stdout); } else { /* Proceso padre */ printf("I am the father with PID:%dn",pid); fflush(stdout); } } return 0; }
Para optimizar la llamadaal sistema fork() linux utiliza la técnica d copy_on_write Añadir un sleep(1); para q los mensajes se intercalen
Ejemplo Maestro-esclavo: Aplicar 1 transformación a 1000 matrices d 1000×20 sub transform() { my $i=0;
while ( $i < $f ){ # I want to create N slaves (childs) to parallelize the work my $pid=fork();
if ($pid == 0 ){ # We are the child do_work($i); exit 0 ;
} else { $i++; $nchilds++ ; if ( $nchilds < $CPUS ){ next ; # If there are less childs than CPU, we continue } else { # If the number of childs is equal to the number of CPUS -> we must wait, # until a child ends. This is, we stop forking until a child ends its work. wait ; $nchilds–; } } } #f }
El maestro se encarga d la creación y planificación d esclavos Para cada matriz, se crea un esclavo (hilo) para transformarla Se permiten hasta un máximo d N threads, donde N es igual al numero d CPUs
Trabajo a realizar x cada esclavo sub do_work { my $i=shift; my $aux=0; my $T="$txt"."/T"."$i" ; open(FILE,"< $T"); $T="$mod_txt"."/T"."$i" ; open(FILEMOD,">$T");
while (< FILE>) { my $line = $_; chomp $line; my @FIELDS = split(' ');
foreach my $field (@FIELDS){ # Apply transformation: Matrix x Scalar $aux=$field*10; print FILEMOD $aux." "; } print FILEMOD "n" ;
} # < FILE>
close(FILE); close(FILEMOD); }
Inicialización: Construcción d las 1000 matrices d 1000×20 (T0 ..T999) sub build_dataset() { my $i=0, $j=0 , $k=0; #create auxiliary directories. `rm -r $txt ` ; `rm -r $mod_txt ` ; `mkdir -p $txt` ; `mkdir -p $mod_txt` ; while ($i < $f){ my $T="$txt"."/T"."$i" ; open(FILE,">$T"); $j=0 ; while ($j < $n){ $k=0 ; while($k < $m){ print FILE $j." " ; $k++ ; } # k print FILE "n" ; $j++ ; } # j close(FILE); $i++ ; } # i }
Maestro-esclavo: Transformación 1000 matrices (Gp:) T0 (Gp:) T1 (Gp:) T2 (Gp:) ………… (Gp:) T999
(Gp:) T0 (Gp:) T4 (Gp:) T8 (Gp:) ………… (Gp:) T996 (Gp:) T1 (Gp:) T5 (Gp:) T9 (Gp:) ………… (Gp:) T997 (Gp:) T2 (Gp:) T6 (Gp:) T10 (Gp:) ………… (Gp:) T998 (Gp:) T3 (Gp:) T7 (Gp:) T11 (Gp:) ………… (Gp:) T999
Suponiendo q cada transformación sobrela tabla (matriz) tarde 30 segundos Versión secuencial: 1000 x 30 = 30000 s. Tiempo total= 8 h y 20 minutos Versión paralela para 4 CPUs: 30000 / 4 =7500 segundos Tiempo total= 2 horas y 5 minutos Análisis temporal:
Segmentación Técnica originalmente utilizada en el diseño de procesadores Consiste en dividir un trabajo en N etapas Existe una relación de orden: Una etapa no puede empezar hasta q no termine la predecesora
Versión secuencial: 2 instrucciones en 15 ciclos Versión segmentada: 5 instrucciones terminadas enlos mismos ciclos de reloj http://cse.stanford.edu/class/sophomore-college/projects-00/risc/pipelining/pipelining1.mov
Problema transformación matrices Número Tablas = 24 , T=10.000 s = S1 + S2 + S3 (3 Etapas) Step 1: matrix por escalar Step 2: Transformar la matriz en aleatoria Step 3: Ordenar las filas d la matriz
Versión Secuencial = 240.000 s Versión segmentada = 240.000 / 3 = 80.000 + 6666 = 86666 (teórico)
(Gp:) T0/s1 (Gp:) T1/s1 (Gp:) T2/s1 (Gp:) ………… (Gp:) T23/s1 (Gp:) T0/s2 (Gp:) T1/s2 (Gp:) T2/s2 (Gp:) ………… (Gp:) T23/s1 (Gp:) T0/s3 (Gp:) T1/s3 (Gp:) T2/s3 (Gp:) ………… (Gp:) T23/s3
Segmentación + superescalar HW: Lanzar N instrucciones en cada ciclo de reloj SW: Lanzar N hilos, cada uno de ellos segmentado Versión segmentada: 10 instrucciones terminadas enlos mismos ciclos de reloj
Problema matrices: combinar maestro-esclavo con segmentación Solución algorítmica Crear tantos procedimientos maestro – esclavos como etapas Cada procedimiento maestro-esclavo se encargará de realizar la transformación correspondiente Cada procedimiento lanzará a su vez N (4 en el ejemplo) trabajadores Programaremos barreras para garantizar el orden de las transformaciones evitar q una etapa se ejecute antes q su predecesora (Gp:) T0/s1 (Gp:) T4/s1 (Gp:) T8/s1 (Gp:) ………… (Gp:) T20/s1 (Gp:) T1/s1 (Gp:) T5/s1 (Gp:) T9/s1 (Gp:) ………… (Gp:) T21/s1 (Gp:) T2/s1 (Gp:) T6/s1 (Gp:) T10/s1 (Gp:) ………… (Gp:) T22/s1 (Gp:) T3/s1 (Gp:) T7/s1 (Gp:) T11/s1 (Gp:) ………… (Gp:) T23/s1 (Gp:) T0/s2 (Gp:) T4/s2 (Gp:) T8/s2 (Gp:) ………… (Gp:) T20/s2 (Gp:) T1/s2 (Gp:) T5/s2 (Gp:) T9/s2 (Gp:) ………… (Gp:) T21/s2 (Gp:) T2/s2 (Gp:) T6/s2 (Gp:) T10/s2 (Gp:) ………… (Gp:) T22/s2 (Gp:) T3/s2 (Gp:) T7/s2 (Gp:) T11/s2 (Gp:) ………… (Gp:) T23/s2 (Gp:) T0/s3 (Gp:) T4/s3 (Gp:) T8/s3 (Gp:) ………… (Gp:) T20/s3 (Gp:) T1/s3 (Gp:) T5/s3 (Gp:) T9/s3 (Gp:) ………… (Gp:) T21/s3 (Gp:) T2/s3 (Gp:) T6/s3 (Gp:) T10/s3 (Gp:) ………… (Gp:) T22/s3 (Gp:) T3/s3 (Gp:) T7/s3 (Gp:) T11/s3 (Gp:) ………… (Gp:) T23/s3
$myproc->start(&matrix_X_scalar);
$myproc->start(&rand_matrix);
sort_matrix_rows;
maestro-esclavo con segmentación sub sort_matrix_rows(){ my $i=0; my $aux=0; my $nchilds=0 ; `rm -r $inorder_txt`; `mkdir -p $inorder_txt`; while ( $i < $f ){ # I am the master. I want to create N slaves (childs) to parallelize the work my $pid=fork(); if ($pid == 0 ){ # We are the child. Barrier to wait until rand_matrix step finishes with table Ti $aux=$i+1; if (($aux < $f ) && ($rand_matrix_finished == 0)) { while (! -e "$random_txt"."/T"."$aux" ) { sleep(1); } } do_sort_matrix_rows_work($i); exit 0 ; } else { $i++; $nchilds++ ; if ( $nchilds < $CPUS ){ next ; } else { # Wai t until a child ends. This is, we stop forking until a child ends its work. wait ; $nchilds–; } } } #f }
Problema matrices: combinar maestro-esclavo con segmentación (Gp:) T0/s1 (Gp:) T4/s1 (Gp:) T8/s1 (Gp:) ………… (Gp:) T20/s1 (Gp:) T1/s1 (Gp:) T5/s1 (Gp:) T9/s1 (Gp:) ………… (Gp:) T21/s1 (Gp:) T2/s1 (Gp:) T6/s1 (Gp:) T10/s1 (Gp:) ………… (Gp:) T22/s1 (Gp:) T3/s1 (Gp:) T7/s1 (Gp:) T11/s1 (Gp:) ………… (Gp:) T23/s1 (Gp:) T0/s2 (Gp:) T4/s2 (Gp:) T8/s2 (Gp:) ………… (Gp:) T20/s2 (Gp:) T1/s2 (Gp:) T5/s2 (Gp:) T9/s2 (Gp:) ………… (Gp:) T21/s2 (Gp:) T2/s2 (Gp:) T6/s2 (Gp:) T10/s2 (Gp:) ………… (Gp:) T22/s2 (Gp:) T3/s2 (Gp:) T7/s2 (Gp:) T11/s2 (Gp:) ………… (Gp:) T23/s2 (Gp:) T0/s3 (Gp:) T4/s3 (Gp:) T8/s3 (Gp:) ………… (Gp:) T20/s3 (Gp:) T1/s3 (Gp:) T5/s3 (Gp:) T9/s3 (Gp:) ………… (Gp:) T21/s3 (Gp:) T2/s3 (Gp:) T6/s3 (Gp:) T10/s3 (Gp:) ………… (Gp:) T22/s3 (Gp:) T3/s3 (Gp:) T7/s3 (Gp:) T11/s3 (Gp:) ………… (Gp:) T23/s3
$myproc->start(&matrix_X_scalar);
$myproc->start(&rand_matrix);
# Barrier to wait until rand_matrix step finishes with table Ti $aux=$i+1; if (($aux < $f ) && ($rand_matrix_finished == 0)) { while (! -e "$random_txt"."/T"."$aux" ) { sleep(1);} }
Necesitaremos 2 barreras # Barrier to wait until matrix_X_scalar step finishes with table Ti $aux=$i+1; if (($aux < $f ) && ($rand_matrix_finished == 0)) { while (! -e "$random_txt"."/T"."$aux" ) { sleep(1); } } $myproc->start(&sort_matrix);
Problema matrices: combinar maestro-esclavo con segmentación Número Tablas = 24 , T=10.000 s = S1 + S2 + S3 Versión Secuencial = 120.000 s (Gp:) T0/s1 (Gp:) T4/s1 (Gp:) T8/s1 (Gp:) ………… (Gp:) T20/s1 (Gp:) T1/s1 (Gp:) T5/s1 (Gp:) T9/s1 (Gp:) ………… (Gp:) T21/s1 (Gp:) T2/s1 (Gp:) T6/s1 (Gp:) T10/s1 (Gp:) ………… (Gp:) T22/s1 (Gp:) T3/s1 (Gp:) T7/s1 (Gp:) T11/s1 (Gp:) ………… (Gp:) T23/s1
(Gp:) T0/s2 (Gp:) T4/s2 (Gp:) T8/s2 (Gp:) ………… (Gp:) T20/s2 (Gp:) T1/s2 (Gp:) T5/s2 (Gp:) T9/s2 (Gp:) ………… (Gp:) T21/s2 (Gp:) T2/s2 (Gp:) T6/s2 (Gp:) T10/s2 (Gp:) ………… (Gp:) T22/s2 (Gp:) T3/s2 (Gp:) T7/s2 (Gp:) T11/s2 (Gp:) ………… (Gp:) T23/s2
(Gp:) T0/s3 (Gp:) T4/s3 (Gp:) T8/s3 (Gp:) ………… (Gp:) T20/s3 (Gp:) T1/s3 (Gp:) T5/s3 (Gp:) T9/s3 (Gp:) ………… (Gp:) T21/s3 (Gp:) T2/s3 (Gp:) T6/s3 (Gp:) T10/s3 (Gp:) ………… (Gp:) T22/s3 (Gp:) T3/s3 (Gp:) T7/s3 (Gp:) T11/s3 (Gp:) ………… (Gp:) T23/s3
Maestro-esclavo segmentado = 120.000 / 4 = 30.000 / 3 = 10.000 + 6666 = 10666 (teórico)
Replica – Versión secuencial (Gp:) Export IXF (Gp:) Load IXF (Gp:) Unload TXT (Gp:) Load Target DB (Gp:) INDEX (Gp:) Statistics
(Gp:) Export IXF (Gp:) Load IXF (Gp:) Unload TXT (Gp:) Load Target DB (Gp:) INDEX (Gp:) Statistics
t0 t1 Tiempo Solamente se ejecuta un proceso, en un determinado instante de tiempo En este espacio de tiempo, hemos conseguido procesar casi 2 tablas Sin embargo, cada transformación (etapa) consume un determinado tipo de recurso : Export IXF -> Net , Load, Unload -> I/O, Index + Statistics -> CPU Por ejemplo mientras descargamos los datos del origen (Export IXF), consumimos ancho de banda de la red, pero las CPUs y el I/O están ociosos. Es decir, estamos desperdiciando recursos!!!
Replica – Versión paralela (Gp:) Export IXF (Gp:) Load IXF (Gp:) Unload TXT (Gp:) Load Target DB (Gp:) INDEX (Gp:) Statistics (Gp:) Export IXF (Gp:) Load IXF (Gp:) Unload TXT (Gp:) Load Target DB (Gp:) INDEX (Gp:) Statistics (Gp:) Export IXF (Gp:) Load IXF (Gp:) Unload TXT (Gp:) Load Target DB (Gp:) INDEX (Gp:) Statistics (Gp:) Export IXF (Gp:) Load IXF (Gp:) Unload TXT (Gp:) Load Target DB (Gp:) INDEX (Gp:) Statistics (Gp:) Export IXF (Gp:) Load IXF (Gp:) Unload TXT (Gp:) Load Target DB (Gp:) INDEX (Gp:) Statistics (Gp:) Export IXF (Gp:) Load IXF (Gp:) Unload TXT (Gp:) Load Target DB (Gp:) INDEX (Gp:) Statistics (Gp:) Export IXF (Gp:) Load IXF (Gp:) Unload TXT (Gp:) Load Target DB (Gp:) INDEX (Gp:) Statistics (Gp:) Export IXF (Gp:) Load IXF (Gp:) Unload TXT (Gp:) Load Target DB (Gp:) INDEX (Gp:) Statistics (Gp:) Export IXF (Gp:) Load IXF (Gp:) Unload TXT (Gp:) Load Target DB (Gp:) INDEX (Gp:) Statistics (Gp:) Export IXF (Gp:) Load IXF (Gp:) Unload TXT (Gp:) Load Target DB (Gp:) INDEX (Gp:) Statistics
t0 t1 t2 t3 t4 t5 t6 t7 Tiempo En este espacio de tiempo, hemos conseguido procesar 10 tablas (teóricamente)
Posix Threads Objetivos Comprender las ventajas de desarrollar aplicaciones paralelas basadas en hilos Estudiar el estandard POSIX para hilos, llamado Pthreads Estudiar las primitivas de control de threads: creación, terminación, join, sincronización, concurrencia, etc .. Aprender a diseñar aplicaciones multi-hilo
Threads Un thread es una unidad de trabajo para la CPU Consiste en un flujo de instrucciones y un estado (pila, contador de programa y conjunto de registros). Los procesos tradicionales de UNIX están basados en 1 hilo q tiene la posesión de toda la memoria y recursos del proceso Los threads contenidos en un proceso pueden ser ejecutados y planificados independientemente Muchos threads comparten el mismo espacio de memória Además de para desarrollar aplicaciones HPC, se utilizan en otro SW: BBDD, servidores Web y de aplicaciones
Monohilo versus Multihilo
Planificación de threads Los threads son ejecutados y planificados independientemente
Processor affinity Modificación al planificador d Linux q permite indicar el procesador preferido para una tarea (proceso o thread)
Ventajas threads -> rendimiento El cambio de contexto es muy pesado (ineficiente) en el caso de procesos
Hay q guardarla memoria del proceso y su estado a disco Leer el estado de disco del siguiente y ponerlo en memoria para q se pueda ejecutar I/O mucho + lenta q CPU
Ventajas threads -> rendimiento Cambio de contexto mucho más eficiente Simplemente hay q cambiar el estado del thread ( conjunto de registros + puntero d pila) Como la memoria es común a los 2 threads no hay q guardarla en disco cuando cambiamos de contexto
Librería de Pthreads Una API estándar POSIX (IEEE 1003.1c), para la creación y sincronización de hilos La API especifica el comportamiento de la librería de hilos La implementación es responsabilidad del desarrollador Portable: Corre en todos los UNIX: Linux, Solaris, z/os UNIX Services, etc .. Simplemente una colección de funciones en C
Utilización de pthreads Siempre incluir la libreria: #include < pthread.h> Compilar: gcc program.c -lpthread int pthread_create (pthread_t *tp, const pthread_attr_t * attr, void *(* start_routine)(void *), void *arg); Crea un nuevo hilo de ejecución que acaba llamando a la función start_routine Retorna 0, si todo ha ido bien. En la variable tp, retorna el identificador dl thread. Attr es para modificar los atributos del nuevo thread. Si le pasamos NULL, se utilizan los atributos por defecto Arg, sirve para pasar los argumentos a la función (staart_routine) a ejecutar por el thread Ejemplo: pthread_create(&thread, NULL, do_work, (void*)&i); int pthread_join(pthread_t thid, void ** status); Se espera hasta q el thread (thid) termine Suspende la ejecución del thread actual, hasta q el thread indicado en thid no termine su ejecución Ejemplo: pthread_join(thread, &status); void pthread_exit(void * status); Termina la ejecución del thread actual No es obligatorio
Un ejemplo #include < stdio.h> /* standard I/O routines */ #include < pthread.h> /* pthread functions and data structures */
/* Shared memory */ #define CPU 3 #define N 100
void *do_work(void *data){ int roll=*((int *)data),i ; /* Private data */ for (i=0;i< N;i++){ printf("Hello World from Thread=%dn",roll); sleep(1); } pthread_exit(NULL); /* terminate the thread */ } /* like any C program, program's execution begins in main */ int main(){ int thr_id,i; /* thread ID for the newly created thread */ void * status; pthread_t thread[CPU]; /* thread's structure */ /* create a new thread that will execute 'do_work(). */ for (i=0;i< CPU;i++) thr_id = pthread_create(&thread[i], NULL, do_work, (void*)&i); /* Waint until all threads had finished */ for (i=0;i< CPU;i++) pthread_join(thread[i],&status); return 0; }
N, CPU proceso
array.c #include < stdio.h> /* standard I/O routines */ #include < stdlib.h> #include < pthread.h> /* pthread functions and data structures */ #define __HPC__ #define CPU 10 unsigned long long N=(18000000000); unsigned long long M=10000000 ; unsigned long long j=0; unsigned long long c,*array; void *do_work(void *data){ long long roll=*((long long*)data); unsigned long long i,j=0,begin,end,slices; begin=(roll*(N/CPU)); end=((roll+1)*(N/CPU)); printf("roll=%lldn",roll); #ifdef __HPC__ slices=end/M; while (j< slices) { #endif for (i=begin; i < end ;i++){ #ifndef __HPC__ if ((i % (unsigned long long) M ) == 0) { printf("roll=%lld i=%lldn",roll,i); fflush(stdout); } #endif array[i]=i; } #ifdef __HPC__ j++; begin=j*slices; end=(j+1)*slices; printf("roll=%lld i=%lldn",roll,i); fflush(stdout) ; } #endif /* terminate the thread */ pthread_exit(NULL); }
/* like any C program, program's execution begins in main */ int main(int argc, char* argv[]){ int thr_id; /* thread ID for the newly created thread */ void * status; pthread_t thread[CPU]; /* thread's structure */ array = (unsigned long long *)malloc( N * sizeof(unsigned long long) ); if ( array ) { /* create a new thread that will execute 'do_work()' */ for (j=0;j< CPU;j++) thr_id = pthread_create(&thread[j], NULL, do_work, (long long *)&j); } else { printf("Problem with malloc: cannot reserve memory n"); } for (j=0;j< CPU;j++) pthread_join(thread[j],&status); /* NOT REACHED */ return 0; } Inicializa en paralelo un vector de enteros. Cada thread inicializa su trozo del vector Desde roll*(N/CPU) Hasta (roll+1)*(N/CPU) Para el caso d N=100 y CPU=4 Th0=0 .. 24, Th1=25 .. 49, Th2=50 .. 74, Th3=75 .. 99
Ejercicio: Calcular el máximo de un array (I) Pistas: Utilizar como base el código array.c Cada thread debe encontrar el máximo local (de su parte dl array) Cada thread debe pasar su máximo local a main Por ejemplo, guardándolo en otro array: int localmax[CPU]; El main, debe esperar a q todos los hijos acaben, para calcular máximo global de todos los máximos locales
Aplicar una transformación a 1000 matrices de 1000×1000 Estructuras de datos #define N 1000 //1k #define M 1000 //1k typedef double matrix[N][N]; //Array of M matrix of NxN matrix *amat[M]; Reserva de memoria for (i=0;i< M;i++) amat[i]= (matrix *)malloc( N * N *sizeof(double) ); Acceder al elemento j,k de la matrix i: (*amat[i])[j][k] Observad q amat[i] equivale a la dirección dl puntero. Mientras q (*amat[i]) es su contenido (dirección apuntada por este). En este caso equivale a la posición 0,0 d la matriz i Transformación: (*amat[i])[j][k]=(*amat[i])[j][k]*sin((float)k)*rand()*atan(rand()) ; Ejercicio: Testear el algoritmo, variando el número de CPUs y midiendo tiempos. Disminuir N i M.
Acceso a memoria compartida El programador es responsible de sincronizar el acceso (proteger) a la memoria global compartida ¿Cómo? Serializando el acceso mediante semáforos La idea es evitar q 2 o +threads modifiquen una variable concurrentemente
Las variables declaradas dentrode la función del thread se llamandatos locales. Son ubicados en la pila de cada thread. Por tanto, se mantienen allímientras dura la ejecución de este.
Mutex example #include < stdio.h> /* standard I/O routines */ #include < pthread.h> /* pthread functions and data structures */ #define CPU 4 long long N=1000000, c,*array,i=0; pthread_mutex_t mutex;
void *do_work(void *data){ long long roll=*((long long*)data); printf("roll=%dn",roll); pthread_mutex_lock(& mutex); for (i=0; i < N;i++){ if ((i % (N/10)) == 0) printf("roll=%d array[%lld]=%lld n",roll,i,array[i]); array[i]++; } pthread_mutex_unlock(& mutex); pthread_exit(NULL); /* terminate the thread */ } int main(int argc, char* argv[]){ int thr_id; pthread_t thread[CPU]; void * status; long long i=0; array = (long long *)malloc( N * sizeof(long long) ); memset(array,0,N*sizeof(long long)); if ( array ) { for (i=0;i< CPU;i++) thr_id = pthread_create(&thread[i], NULL, do_work, (void*)&i); } else { printf("Problem with malloc: cannot reserve memory n"); } for (i=0;i< CPU;i++) pthread_join(thread[i],&status); for (i=0; i < N;i++) if (array[i] != CPU ) printf("Wrong result array[%lld]=%lld != %d n",i,array[i],CPU); return 0; }
Distintos threads modificando la variable compartida i Serializar el acceso
Ejercicio: Calcular el máximo de un array (II) Pistas: Utilizar como base el código array.c Cada thread debe encontrar el máximo local (de su parte dl array) Cada thread debe pasar su máximo local a main a través de una variable global int max=0; Si el máximo local es mayor q el global lo escribiremos en la variable max Hay q proteger la comparación y la posible escritura del nuevo máximo para q sea “thread safe” El main, debe esperar a q todos los hijos acaben, para después imprimir el valor de max
Ejercicio: Multiplicación de matrices cuadradas Pistas: Definición de matrices: #define SIZE 10 int A[SIZE][SIZE], B[SIZE][SIZE], C[SIZE][SIZE]; Particionado Cada thread debe ejecutar el algoritmo sobre su parte de el problema (el nº de filas q le toquen) Algoritmo a ejecutar x cada thread (do_work):
for (i=from; i< to; i++) for (j=0; j< SIZE; j++) { C[i][j]=0; for (k=0; k< SIZE; k++) C[i][j] += A[i][k]*B[k][j]; }
Estadísticashttp://www.top500.org/stats
Familia de procesadores Supervivientes: x86 (AMD,intel), power, Itanic
Número de procesadores
Redes de interconexión
Lenguajes de programación
Inhibidores de paralelismo
MPI Previamente PVM: Parallel Virtual Machine. MPI: Message Passing Interface. Una especificación para paso de mansajes. La primera librería de paso de mensajes estándar y portable. Por consenso MPI Forum. Participantes de unas 40 organizaciones.
Paradigma de paso de mensajes Probablemente más extendido hoy día en programación de aplicaciones paralelas. Consiste en una serie de procesos que interactúan por medio de mensajes. Cada proceso puede ejecutar código distinto y sobre diferentes datos. El modelo de paso de mensajes es valido tanto para sistemas de memoria compartida como para sistemas de memoria distribuida (cluster & grid computing). El intercambio de mensajes es cooperativo: los datos deben ser tanto enviados como recibidos explícitamente. Esto supone una ventaja en cuanto a que la modificación en la memoria del proceso es conocida por este.
MPI Estandarización. Portabilidad: multiprocesadores, multicomputadores, redes, heterogéneos, … Buenas prestaciones, …, si están disponibles para el sistema. Amplia funcionalidad. Implementaciones libres (mpich, lam, …)
Comunicaciones básicas en MPI Los datos son transferidos de un procesador a otro Un procesador envía datos Otro recibe los datos Síncrona La llamada no retorna hasta q el mensaje no es enviado o recibido Asíncrono La llamada indica el comienzo del envío o de la recepción Hay q realizar una llamada adicional para determinar si la comunicación ha terminado
Tipos de comunicaciones La comunicación MPI entre procesos puede ser de dos tipos: Punto a punto: el proceso “origen” conoce el identificador del proceso “destino” y envía un mensaje dirigido solo a él. Se usan las funciones MPI_Send y MPI_Recv. Típicamente un master envía la parte correspondiente de los datos del problema a sus esclavos. Colectiva: Operaciones en las que participan todos los procesos de un operador. Ejemplo: “Broadcast”: El proceso origen manda el mensaje a todos los demás (que pertenezcan al mismo comunicador). Esto es típico de un esquema “master-slave”. Se usa la función MPI_Bcast. Típicamente un master envía los mismos datos a sus esclavos.
Las funciones MPI de recepción de datos son por lo general “bloqueantes”, es decir, un proceso que debe recibir un mensaje espera hasta que de hecho lo ha recibido completo.
MPI: Funciones básicas Funciones básicas: MPI_Init => Inicialización de MPI. MPI_Finalize => Termina MPI. MPI_Comm_size => Para averiguar el número de procesos. MPI_Comm_rank => Identifica el proceso. MPI_Send => Envía un mensaje. MPI_Recv => Recibe un mensaje. Referencia del estándar en http://www-unix.mcs.anl.gov/mpi/ Con estas 6 funciones se puede hacer casi cualquier programa
Escribiendo programas en MPI De las 6 funciones básicas que mencionamos antes MPI_Init y MPI_Finalize son imprescindibles para que haya un programa MPI. Veamos un ejemplo trivial
#include "mpi.h" #include < stdio.h>
int main( int argc, char **argv ) { MPI_Init( &argc, &argv ); printf( "Hola Mundon" ); MPI_Finalize(); return 0; }
Corriendo programas en MPI El programa anterior solo inicializa y termina el entorno MPI. Entre tanto cada proceso imprime un mensaje por pantalla. Compilación Para un programa pequeño como este podemos hacer una llamada directamente al comando de compilación: mpicc o gcc –lmpi o icc –lmpi (para programas C) mpif77 (Fortran 77) mpif90 (Fortran 90) Para aplicaciones más complicadas conviene usar un Makefile. En nuestro caso anterior (fichero hello.c): icc -lmpi hello.c gcc –lmpi hello.c
Corriendo programas en MPI Ejecución El modelo de ejecución de MPI sigue un esquema de creación (spawn) simultánea de procesos al lanzar la aplicación La ejecución de una aplicación suele hacerse con: mpirun -np p programa [opciones] -np N: N indica el número de procesos que se quiere en la ejecución del programa. Ejemplo: mpirun -np 2 ./a.out Al ejecutar una aplicación: Se lanzan p copias del mismo ejecutable (p.e. con ssh) Se crea un comunicador MPI_COMM_WORLD que engloba a todos los procesos
Modelo de Programación – Comunicadores Un comunicador es una abstracción que engloba los siguientes conceptos: Grupo: conjunto de procesos Contexto: para evitar interferencias entre mensajes distintos Un comunicador agrupa a p procesos int MPI_Comm_size(MPI_Comm comm, int *size) Cada proceso tiene un identificador (rango), un número entre 0 y p – 1 int MPI_Comm_rank(MPI_Comm comm, int *rank)
Hello.c (II) #include < stdio.h> #include < mpi.h> int main (argc, argv) int argc; char *argv[]; { int rank, size; MPI_Init (&argc, &argv); /* starts MPI */ MPI_Comm_rank (MPI_COMM_WORLD, &rank); /* get current process id */ MPI_Comm_size (MPI_COMM_WORLD, &size); /* get number of processes */ printf( "Hello world from process %d of %dn", rank, size ); MPI_Finalize(); return 0; } Ejecutar este ejemplo: gcc –lmpi hello.c mpirun -np 2 ./a.out Averiguaremos desde el programa el número de procesos que participan y la identificación de cada uno.
MPI_Send La operación básica de envío (bloqueante) es: MPI_Send( start, count, datatype, dest, tag, comm ) start: puntero a los datos a enviar count: número de elementos a enviar datatype: tipo de dato dest: Identificación del proceso destino tag: etiqueta de la comunicación comm: Identificación del comunicador
MPI_Recv La operación básica de recepción correspondiente: MPI_Recv(start, count, datatype, source, tag, comm, status) start: puntero para la recepción de los datos count: número de elementos datatype: tipo de dato source: Identificación del proceso origen tag: etiqueta de la comunicación comm: Identificación del comunicador status: puntero para acceso a información sobre mensaje
Envio de mensajes: N hijos enviando saludos al padre
#include < stdio.h> #include < string.h> #include "mpi.h" main(int argc, char*argv[]) {
int myrank, p, source, dest, tag = 0; char message[100]; MPI_Status status; MPI_Init(&argc,&argv); MPI_Comm_rank(MPI_COMM_WORLD,&myrank); MPI_Comm_size(MPI_COMM_WORLD,&p);
if (myrank != 0) { printf("Processor %d of %dn",myrank, p); sprintf(message,"greetings from process %d!", myrank); dest = 0; MPI_Send(message, strlen(message)+1, MPI_CHAR, dest, tag, MPI_COMM_WORLD); } else { printf("processor 0, p = %d ",p); for(source=1; source < p; source++) { MPI_Recv(message,100, MPI_CHAR, source, tag, MPI_COMM_WORLD, &status); printf("%sn",message); } } MPI_Finalize(); } Processor 2 of 4 Processor 3 of 4 Processor 1 of 4 processor 0, p = 4 greetings from process 1! greetings from process 2! greetings from process 3!
mpicc -o hello hello.c mpirun -np 4 hello
Tipos de datos MPI Se definen los siguientes tipos de datos MPI: MPI_CHAR MPI_SHORT MPI_INT MPI_LONG MPI_UNSIGNED_CHAR MPI_UNSIGNED_SHORT MPI_UNSIGNED MPI_UNSIGNED_LONG MPI_FLOAT MPI_DOUBLE MPI_LONG_DOUBLE MPI_BYTE MPI_PACKED Corresponde a los de C, pero se añaden el tipo byte, y el empaquetado, que permite enviar simultáneamente datos de distintos tipos.
Programación paralela con MPI Típicamente se utiliza el modelo maestro-trabajadores El maestro distribuye a cada trabajador su parte del problema MPI_Send Los hijos reciben su parte d datos dl problema MPI_Recv Los hijos hacen transformaciones sobre la parte de datos q les ha enviado el maestro Posteriormente, los trabajadores le envían el resultado de las transformaciones al maestro Es similar al maestro-trabajadores de memoria compartida, con las comunicaciones se hacen de manera explícita ya q no tenemos acceso a la memoria compartida
Broadcast start: puntero a los datos a enviar count: número de elementos a enviar datatype: tipo de dato root: identificación del proceso origen comm: Identificación del comunicador #include < stdio.h> #include "mpi.h"
#define N 10 int array[N];
int main() { int rank,i;
MPI_Init( &argc, &argv ); MPI_Comm_rank( MPI_COMM_WORLD, &rank ); if (rank == 0 ) { //Only master performs array initialitation for (i=0;i< N;i++) array[i]=i; } MPI_Bcast( array , N, MPI_INT , 0, MPI_COMM_WORLD ); for (i=0;i< N;i++) { printf("rank:%d array[%d]=%dn ",rank,i,array[i]); //Until all threads arrive at this point, we will wait! MPI_Barrier(MPI_COMM_WORLD); } MPI_Finalize( ); return 0; } MPI_Bcast(start, count, datatype, root, comm)
MPI Scatter Repartir datos sobre todos los procesos Calcular max array: El master reparte con MPI_Scatter, la porción correspondiente del array a cada esclavo if (rank == 0 ) { //Only master performs array initialitation array=(double *)malloc(N*sizeof(double)); for (i=0;i< N;i++) array[i]=(double)i;//rand(); porcio=(double *)malloc((N/nprocs)*sizeof(double)); MPI_Scatter(array, N/nprocs, MPI_DOUBLE, porcio, N/nprocs, MPI_DOUBLE, 0, MPI_COMM_WORLD); // En la variable porcio, todas las tareas reciben su parte del array (N/procs elementos)
MPI_Gatther MPI_Gather – obtener datos de todos los procesos. MPI_Scatter …. max_array=(double *)malloc(nprocs*sizeof(double)); double maximum=-1; for (i=0;i< N/nprocs;i++) { printf("Valor actual:%f, Valor max:%f, en i=%dn",porcio[i],maximum,i); maximum=max(maximum,porcio[i]); } printf("Local maximum: %f from rank:%dn",maximum,rank); MPI_Gather(&maximum,1,MPI_DOUBLE,max_array,1,MPI_DOUBLE,0,MPI_COMM_WORLD); //En la variable max_array recibimos todos los máximos locales de todas las tareas ….
Calcular el máximo de una array con MPI #include < stdio.h> #include "mpi.h"
#define N 10 #define max(a,b) (a>b ? a : b)
int main(int argc,char *argv[]) { int rank,i,nprocs; double *array, *porcio, *max_array;
MPI_Init( &argc, &argv ); MPI_Comm_rank( MPI_COMM_WORLD, &rank ); MPI_Comm_size( MPI_COMM_WORLD, &nprocs);
if (rank == 0 ) { //Only master performs array initialitation array=(double *)malloc(N*sizeof(double)); if (array == NULL) { printf("Can't allocate memoryn"); return -1;} for (i=0;i< N;i++) array[i]=(double)i;//rand();
max_array=(double *)malloc(nprocs*sizeof(double)); }
// All processes in communicator porcio=(double *)malloc((N/nprocs)*sizeof(double));
MPI_Scatter(array, N/nprocs, MPI_DOUBLE, porcio, N/nprocs, MPI_DOUBLE, 0, MPI_COMM_WORLD);
double maximum=-1; for (i=0;i< N/nprocs;i++) { printf("Valor actual:%f, Valor max:%f, en i=%dn",porcio[i],maximum,i); maximum=max(maximum,porcio[i]); } printf("Local maximum: %f from rank:%dn",maximum,rank); MPI_Gather(&maximum,1,MPI_DOUBLE,max_array,1,MPI_DOUBLE,0, MPI_COMM_WORLD);
if(rank==0){ for (i=1;i< nprocs;i++) maximum=max(maximum,max_array[i]); printf("Maximum:%fn",maximum); }
MPI_Finalize( ); return 0; }
Repartir M matrices entre N procesos #include < stdio.h> #include < mpi.h> #include < stdlib.h> #include < math.h> #define N 10 #define M 10 int CPU=0; typedef double matrix[N][N]; //Array d M matrices d NxN matrix *amat[M];
#define print_matrix(slice_mat,i,M,N,myrank,j,k,nprocs) do { printf( "Received matrix %d of %d. My rank:%d. Proceding to print it!n“ ,i,M,myrank); for (j=0;j< N;j++){ printf("nt| "); for (k=0;k< N;k++) printf("M[%d][%d]=%f ",j,k,(*slice_mat[i/nprocs])[j][k]); printf("|"); } } while (0)
Repartir M matrices entre N procesos
if (myrank==(i%nprocs)) { printf( "Receiving matrix %d of %d. My rank:%dn", i,M,myrank); slice_mat[i/nprocs]= (double *)malloc( N * N *sizeof(double) ); MPI_Recv(slice_mat[i/nprocs],N*N,MPI_DOUBLE,0,i,MPI_COMM_WORLD,&status); print_matrix(slice_mat,i,M,N,myrank,j,k,nprocs); } }
MPI_Finalize(); return 0; } int main (argc, argv) int argc; char *argv[]; { int myrank, nprocs,i,j,k; MPI_Status status; double p,*aux; MPI_Init (&argc, &argv); /* starts MPI */ MPI_Comm_rank (MPI_COMM_WORLD, &myrank); MPI_Comm_size (MPI_COMM_WORLD, &nprocs); CPU=nprocs; matrix *slice_mat[M/CPU]; printf("Rank:%d nprocs %dn",myrank,nprocs); fflush(stdout); for (i=0;i< M;i++) { if (myrank == 0) { // master amat[i]= (double *)malloc( N * N *sizeof(double) ); for (j=0;j< N;j++) for(k=0;k< N;k++) (*amat[i])[j][k]=i;
MPI_Send(amat[i], N*N, MPI_DOUBLE,i%nprocs,i ,MPI_COMM_WORLD); }
Aplicar una transformación a 1000 matrices de 1000×1000 usando MPI Estructuras de datos #define N 1000 //1k #define M 1000 //1k typedef double matrix[N][N]; //Array of M matrix of NxN matrix *amat[M]; Transformación: (*amat[i])[j][k]=(*amat[i])[j][k]*sin((float)k)*rand()*atan(rand()) ; Adaptaremos el código desarrollado en Posix Threads para ejecutarlo en MPI Simplemente necesitamos añadir la parte de comunicación explícita, mediante el envio de mensajes Ejercicio: Testear el algoritmo, variando el número de CPUs y midiendo tiempos. Disminuir N i M.
Variables + Trabajo a realizar por cada hijo #include < stdio.h> #include < mpi.h> #include < stdlib.h> #include < malloc.h> #include < math.h> #define N 10 //1M #define M 10 //1K typedef double matrix[N][N]; //Array d M matrices d NxN matrix *amat[M]; int CPU=0;
void * do_work(int roll, matrix *slice_mat[]) { int i,j,k,m,n; double max=0 ; printf("roll=%dn",roll); fflush(stdout); for (i=0; i < (M/CPU);i++){ for (j=0; j< N;j++) for (k=0;k< N;k++) (*slice_mat[i])[j][k]=(*slice_mat[i])[j][k] * sin((float)k) * rand() * atan(rand()) ; for (m=0; m< N ; m++) for (n=0; n< N; n++) if ((*slice_mat[i])[m][n] > max ) max=(*slice_mat[i])[m][n]; } printf("Max= %fn",max); fflush(stdout); }
Comunicaciones + transformaciones int main (argc, argv) int argc; char *argv[]; { int myrank, nprocs,i,j; MPI_Status status; double p,* aux; MPI_Init (&argc, &argv); /* starts MPI */ MPI_Comm_rank (MPI_COMM_WORLD, &myrank); MPI_Comm_size (MPI_COMM_WORLD, &nprocs); CPU=nprocs; matrix *slice_mat[M/CPU]; printf("Rank:%d nprocs %dn",myrank,nprocs); fflush(stdout); for (i=0;i< M;i++) { if (myrank == 0) { // master amat[i]= (matrix *)malloc( N * N *sizeof(double) ); aux=amat[i]; p=rand(); for (j=0;j< N*N;j++) aux[j]=p; MPI_Send((*amat[i]), N*N, MPI_DOUBLE,i%nprocs,i ,MPI_COMM_WORLD); }
if (myrank==(i%nprocs)) { printf( "Receiving matrix %d of %d. My rank:%dn", i,M,myrank); slice_mat[i/nprocs]= (double *)malloc( N * N *sizeof(double) ); MPI_Recv((*slice_mat[i/nprocs]),N*N,MPI_DOUBLE,0,i, MPI_COMM_WORLD,&status); } } for (i=0;i< M/CPU;i++) do_work(i,slice_mat); //TODO: Send back results to master MPI_Finalize(); return 0; } Ejercicio: Enviar los datos de vuelta al maestro.
MPI_Allgather
MPI_Reduce
Bibliografia Básica: google Ian Foster: Designing and Building Parallel Programs. 1995. Kumar, Grama, Gupta, Karypis: Introduction to Parallel Computing. Design and Analysis of Algorithms. The Benjamin Cumming Publishing Company. 1994. Barry Wilkinson, Michael Allen: Parallel programming. Prentice-Hall. 1999. Complementaria: Akl: Diseño y análisis de algoritmos paralelos. Ra-ma. 1992. Andrews: Foundations of Multithreaded, Parallel, and Distributed Programming. Addison-Wesley, 2000 Bertsekas, Tsilikis: Parallel and Distributed Computation. Prentice-Hall. 1989. Rajkumar Buyya (Editor): High Performance Cluster Computing, Vol 2, Programming and Applications. Prentice Hall. 1999. Gibbons, Rytter: Efficient Parallel Algorithms. Cambridge University press. 1988. Ja-Ja: An Introduction to Parallel Algorithms. Addison-Wesley. 1992. Lester: The art of Parallel Programming. Prentice-Hall. 1993. Modi: Parallel Algorithms for Matrix Computation. Oxford University Press. 1989. Quinn: Design of Efficient Algorithms. McGraw-Hill. 1987.
| Página siguiente |