Embed Size (px)
DESCRIPTION
Introducción a la programación HPC. Josep Vidal Canet Alejandro Soriano Universitat de València. Objetivos. Conocer los principios básicos que rigen la programación de altas prestaciones (HPC) Hardware Software Conocer las tecnologías más utilizadas para implementar algoritmos paralelos - PowerPoint PPT Presentation
Citation preview
Introducción a la programación HPC
Josep Vidal CanetAlejandro SorianoUniversitat de València
ObjetivosConocer los principios básicos que rigen la programación de altas prestaciones (HPC) Hardware Software
Conocer las tecnologías más utilizadas para implementar algoritmos paralelos Posix Threads MPI OpenMP (Alex)
Las tendencias en el campo de HPCReducir el tiempo de ejecución
MotivaciónHay problemas que no se pueden resolver con un algorítmo secuencial
Predicción meteorológicaHardware roadmap
Imposible seguir aumentando la velocidad del reloj a causa de la disipación de calor
Para aumentar el rendimiento -> aumentar el número de cores y threads per core
Configuración PCs actuales = 4 cores Existen PCs (orientado segmento mercado profesional) con 8 cores
(2 socket)La tendencia del Hardware implica rediseñar el software para poder aprovechar toda la potencia del hardware
Pasar de aplicaciones secuenciales mono-hilo a paralelas multi-hilo
Actualmente existe software multihilo -> servidores web, J2EE, BBDD, etc …
En definitiva, paralelismo masivo en la era del paralelismo para las masas
Una nueva era en el diseño de sistemas
Los sistemas altamente paralelos construidos con múltiples procesadores pequeños, están ocupando un segmento cada vez mayor del mercado de servidores $ 41,995.00 por 1 servidor con 32 cores basado en AMD
Generalmente, caracterizados por un rendimiento modesto en aplicaciones mono-hilo, buen rendimiento a nivel d chip (N cores) y excelente relación entre consumo/rendimientoLa tecnología de paralelismo, anteriormente utilizada en HPC (High Performance Computing) se está convirtiendo de uso generalizado en toda la pila de software.
Evolución numero de transistores en los Microprocesadores
La litografía permitirá seguir escalando nº de transistores por chip (densidad)
dual-core Power6 tiene790 millones
Tendencia en la frecuencia de reloj de los procesadores
La disipación de calor limita el incremento en las velocidades del reloj
Chip Power DensityLa disipación de calor está limitando el aumento de la frecuencia de los relojes, dando lugar a la emergencia de chips multicore con menor consumo de energía
Low power multicores replacing single high-power cores
Tendencia en procesadores multicore
Cell = 9 cores, 10 threads
Crecimiento del número de threads por procesador
Estamos entrando en la era de la computación masivamente multithread
1 Ejemplo: Sun Niagara; 1 chip = 8 cores x 8 threads/core = 64 threads
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)
DB2 UDBMaxappls
CICSSERVER
jdbc + ctg db2jd
DB2
OS/390
power 616 cores
32 threads
ORACLE
Fonts DadesServidors AplicacionsServidors WEB
THREADLIMIT
AUTOMAT
LDAPserver2
Switch L
evel 4 / poundB
alanceig Càrrega
LDAPserver1
pugin-cfg.xml
RACF
OS/390 Z
890
FireWall PIX
Cisco
Explica
DB2
persistenciasessions
JVMn
JMVx
JVM1, JVMx
JVMm
AIX pseries4 cores, 8 threads
(power 5)
WAS GridCluster
servidors web
Linux/Apache
Dual-core AMDwebges01
webges11
Webges..
Soporta + d 500 peticiones x segundo
Programación paralelaSegú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 ejemplopublic 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.javajava –Xmx 512 MyThread
Modificación concurrente de datos compartidos
1. Thread 1: load value of i into a register on processor 1 (lets call it r1) [i=1, r1=1] 2. Thread 2: load value of i into a register on processor 2 (lets call it r2) [i=1, r1=1,
r2=1] 3. Thread 1: increment r1 by 1 [i=1, r1=2, r2=1] 4. Thread 2: increment r2 by 1 [i=1, r1=2, r2=2] 5. Thread 1: store value in r1 back into i [i=2, r1=2, r2=2] 6. 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 impredecibleSolución: Pasar de ejecución paralela a secuencial con un semáforoComo 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 secuencialSIMD Computadores vectoriales (NEC, Fujitsu, Cray),procesadores con instrucciones de extensiónmultimedia (SSE3, Altivec), GPU’sMIMD 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 AccessNUMA: Non-Uniform Memory Accesscc-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 DistribuidaSe requiere una red de comunicación para que los procesadores
puedan acceder a la memoria no local
CaracterísticasNo existe el concepto de memoria globalProcesadores 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ísticasCada nodo es un multiprocesador (p.e. cc-NUMA)Comunicación para mover datos de un nodo a otroActualmente, 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 DataSon modelos de programación de más alto nivel,
aplicables a cualesquiera de los paradigmas descritosSPMD: el mismoprograma se ejecutapor todas las tareasMPMD: cada tareapuede tener unprograma distintoLos programas SPMD son más fáciles de mantenerSuelen instrucciones condicionales
pid=fork(); if (pid ==0) {printf(“Child\n”);}else{printf(“Master\n”);}
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. paralelaParticionado: Repartir el espacio de datos del problema entre N trabajadoresCada 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 10int 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:%d\n",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 1000x20
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 transformarlaSe 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 1000x20
(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
T0 T1 T2 ………… T999
T0 T4 T8 ………… T996
T1 T5 T9 ………… T997
T2 T6 T10 ………… T998
T3 T7 T11 ………… 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 segundosTiempo 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)
T0/s1 T1/s1 T2/s1 ………… T23/s1
T0/s2 T1/s2 T2/s2 ………… T23/s1
T0/s3 T1/s3 T2/s3 ………… 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ónSolució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
T0/s1T4/s1T8/s1 ………… T20/s1
T1/s1T5/s1T9/s1 ………… T21/s1
T2/s1T6/s1T10/s1 ………… T22/s1
T3/s1T7/s1T11/s1 ………… T23/s1
T0/s2T4/s2T8/s2 ………… T20/s2
T1/s2T5/s2T9/s2 ………… T21/s2
T2/s2T6/s2T10/s2 ………… T22/s2
T3/s2T7/s2T11/s2 ………… T23/s2
T0/s3T4/s3T8/s3 ………… T20/s3
T1/s3T5/s3T9/s3 ………… T21/s3
T2/s3T6/s3T10/s3 ………… T22/s3
T3/s3T7/s3T11/s3 ………… 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
T0/s1T4/s1T8/s1 ………… T20/s1
T1/s1T5/s1T9/s1 ………… T21/s1
T2/s1T6/s1T10/s1 ………… T22/s1
T3/s1T7/s1T11/s1 ………… T23/s1
T0/s2T4/s2T8/s2 ………… T20/s2
T1/s2T5/s2T9/s2 ………… T21/s2
T2/s2T6/s2T10/s2 ………… T22/s2
T3/s2T7/s2T11/s2 ………… T23/s2
T0/s3T4/s3T8/s3 ………… T20/s3
T1/s3T5/s3T9/s3 ………… T21/s3
T2/s3T6/s3T10/s3 ………… T22/s3
T3/s3T7/s3T11/s3 ………… 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ónNúmero Tablas = 24 , T=10.000 s = S1 + S2 + S3Versión Secuencial = 120.000 s
T0/s1 T4/s1 T8/s1 ………… T20/s1
T1/s1 T5/s1 T9/s1 ………… T21/s1
T2/s1 T6/s1T10/s1 ………… T22/s1
T3/s1 T7/s1T11/s1 ………… T23/s1
T0/s2 T4/s2 T8/s2 ………… T20/s2
T1/s2 T5/s2 T9/s2 ………… T21/s2
T2/s2 T6/s2T10/s2 ………… T22/s2
T3/s2 T7/s2T11/s2 ………… T23/s2
T0/s3 T4/s3 T8/s3 ………… T20/s3
T1/s3 T5/s3 T9/s3 ………… T21/s3
T2/s3 T6/s3T10/s3 ………… T22/s3
T3/s3 T7/s3T11/s3 ………… T23/s3
Maestro-esclavo segmentado = 120.000 / 4 = 30.000 / 3 = 10.000 + 6666 = 10666 (teórico)
Replica – Versión secuencial
ExportIXF
LoadIXF
UnloadTXT
LoadTarget DB
INDEX Statistics
ExportIXF
LoadIXF
UnloadTXT
LoadTarget DB
INDEX
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
ExportIXF
LoadIXF
UnloadTXT
LoadTarget DB
INDEX Statistics
ExportIXF
LoadIXF
UnloadTXT
LoadTarget DB
INDEX Statistics
ExportIXF
LoadIXF
UnloadTXT
LoadTarget DB
INDEX Statistics
ExportIXF
LoadIXF
UnloadTXT
LoadTarget DB
INDEX Statistics
ExportIXF
LoadIXF
UnloadTXT
LoadTarget DB
INDEX Statistics
ExportIXF
LoadIXF
UnloadTXT
LoadTarget DB
INDEX Statistics
ExportIXF
LoadIXF
UnloadTXT
LoadTarget DB
INDEX Statistics
ExportIXF
LoadIXF
UnloadTXT
LoadTarget DB
INDEX Statistics
ExportIXF
LoadIXF
UnloadTXT
LoadTarget DB
INDEX Statistics
ExportIXF
LoadIXF
UnloadTXT
LoadTarget DB
INDEX Statistics
t0
t1
t2
t3
t4
t5
t6
t7
Tiempo
•En este espacio de tiempo, hemos conseguido procesar 10 tablas (teóricamente)
Posix ThreadsObjetivos 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
ThreadsUn 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 procesoLos threads contenidos en un proceso pueden ser ejecutados y planificados independientementeMuchos threads comparten el mismo espacio de memóriaAdemás de para desarrollar aplicaciones HPC, se utilizan en otro SW: BBDD, servidores Web y de aplicaciones
Monohilo versus Multihilo
Planificación de threadsLos 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
1. Hay q guardarla memoria del proceso y su estado a disco
2. 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 PthreadsUna API estándar POSIX (IEEE 1003.1c), para la creación y sincronización de hilosLa API especifica el comportamiento de la librería de hilos La implementación es responsabilidad del
desarrolladorPortable: Corre en todos los UNIX: Linux, Solaris, z/os UNIX Services, etc ..Simplemente una colección de funciones en C
Utilización de pthreadsSiempre incluir la libreria: #include <pthread.h>Compilar: gcc program.c -lpthreadint 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=%d\n",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=%lld\n",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=%lld\n",roll,i); fflush(stdout); }#endif array[i]=i; }#ifdef __HPC__
j++; begin=j*slices; end=(j+1)*slices; printf("roll=%lld i=%lld\n",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 1000x1000
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 4long long N=1000000, c,*array,i=0;pthread_mutex_t mutex;
void *do_work(void *data){ long long roll=*((long long*)data); printf("roll=%d\n",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
Sistemas Operativos
Lenguajes de programación
Inhibidores de paralelismo
Mercado:
MPIPreviamente 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 comunicacionesLa 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ásicasFunciones 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 Mundo\n" ); 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
distintosUn comunicador agrupa a p procesosint MPI_Comm_size(MPI_Comm comm, int *size)Cada proceso tiene un identificador (rango), un número entre 0 y p − 1int 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 %d\n", rank, size ); MPI_Finalize(); return 0;}
Ejecutar este ejemplo:gcc –lmpi hello.cmpirun -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 )1. start: puntero a los datos a enviar2. count: número de elementos a enviar3. datatype: tipo de dato4. dest: Identificación del proceso destino5. tag: etiqueta de la comunicación6. 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)
1. start: puntero para la recepción de los datos2. count: número de elementos3. datatype: tipo de dato4. source: Identificación del proceso origen5. tag: etiqueta de la comunicación6. comm: Identificación del comunicador7. 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 %d\n",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("%s\n",message); } } MPI_Finalize();}
Processor 2 of 4Processor 3 of 4Processor 1 of 4processor 0, p = 4 greetings from process 1!greetings from process 2!greetings from process 3!
mpicc -o hello hello.cmpirun -np 4 hello
Tipos de datos MPISe 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-trabajadoresEl maestro distribuye a cada trabajador su parte del problema MPI_SendLos hijos reciben su parte d datos dl problema MPI_RecvLos 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 maestroEs 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
1. start: puntero a los datos a enviar2. count: número de elementos a enviar3. datatype: tipo de dato4. root: identificación del proceso origen5. comm: Identificación del comunicador
#include <stdio.h>#include "mpi.h"
#define N 10int 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]=%d\n ",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_GattherMPI_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=%d\n",porcio[i],maximum,i); maximum=max(maximum,porcio[i]); } printf("Local maximum: %f from rank:%d\n",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 memory\n");
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=%d\n",porcio[i],maximum,i); maximum=max(maximum,porcio[i]); } printf("Local maximum: %f from rank:%d\n",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:%f\n",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 10int CPU=0;typedef double matrix[N][N]; //Array d M matrices d NxNmatrix *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("\n\t| "); \ 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:%d\n", 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 %d\n",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 1000x1000 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 //1Ktypedef double matrix[N][N]; //Array d M matrices d NxNmatrix *amat[M];int CPU=0;
void * do_work(int roll, matrix *slice_mat[]) { int i,j,k,m,n; double max=0 ; printf("roll=%d\n",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= %f\n",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 %d\n",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:%d\n",
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 masterMPI_Finalize(); return 0;}
Ejercicio: Enviar los datos de vuelta al maestro.
MPI_Allgather
MPI_Reduce
BibliografiaBá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.
