Download Configuració dels sistemes de informació

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



Posix Threads
MPI
OpenMP (Alex)
Las tendencias en el campo de HPC
Reducir el tiempo de ejecución
Motivación
Hay problemas que no se pueden resolver con un algorítmo
secuencial

Predicción meteorológica
Hardware 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/rendimiento
La 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 tiene
790 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 Density
La 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)
Servidors WEB
Servidors Aplicacions
Webges..
JVMn
db2jd
DB2 UDB
Maxappls
AIX pseries
4 cores, 8 threads
(power 5)
DB2
persistencia
sessions
RACF
CICS
SERVER
THREAD
LIMIT
AUTOMAT
DB2
OS/390
OS/390 Z890
Soporta + d 500 peticiones x segundo
ORACLE
JVMm
Explica
LDAP
server1
jdbc + ctg
JMVx
pugin-cfg.xml
Switch Level 4 / pound
Balanceig Càrrega
FireWall PIX Cisco
JVM1,
JVMx
webges01
LDAP
server2
power 6
16 cores
32 threads
WAS Grid
Cluster
servidors web
Linux/Apache
Dual-core
AMD
webges11
Fonts Dades
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
javac MyThread.java
java –Xmx 512 MyThread
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
}
}
}
Modificación concurrente de datos compartidos
2 threads intentando incrementar el valor de la variable i=1 (i++)

Th 1 i++; (i=2)

Th 2 i++; (i=3)
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]
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
Tipos:
UMA: Uniform Memory Access
NUMA: Non-Uniform Memory Access
cc-NUMA: Cache Coherent NUMA
Ventajas: fácil programación; Desventajas: escalabilidad, precio
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:
Ejemplos:
Multivac, Tirant
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
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(“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. 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:%d\n",pid);
fflush(stdout);
Para optimizar la llamada
al sistema fork() linux utiliza la
técnica d copy_on_write
}
}
return 0;
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;
El maestro se encarga d la creación y planificación d esclavos
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
}
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 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
Análisis temporal:
T0 T1 T2
…………
T999
T0
T1
T2
T3
…………
…………
…………
…………
T996
T997
T998
T999
T4
T5
T6
T7
T8
T9
T10
T11
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
Suponiendo q cada transformación sobre
la tabla (matriz) tarde 30 segundos
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 en
los 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
T23/s1
T0/s1 T1/s1 T2/s1 …………
T0/s2 T1/s2 T2/s2 …………
T23/s1
T23/s3
T0/s3 T1/s3 T2/s3 …………
Versión segmentada = 240.000 / 3 = 80.000 + 6666 = 86666 (teórico)
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 en
los 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
T0/s1T4/s1T8/s1
T1/s1T5/s1T9/s1
T2/s1T6/s1T10/s1
T3/s1T7/s1T11/s1
…………
…………
…………
…………
T0/s2T4/s2T8/s2
T1/s2T5/s2T9/s2
T2/s2T6/s2T10/s2
T3/s2T7/s2T11/s2
T20/s1
T21/s1
T22/s1
T23/s1
…………
…………
…………
…………
T0/s3T4/s3T8/s3
T1/s3T5/s3T9/s3
T2/s3T6/s3T10/s3
T3/s3T7/s3T11/s3
$myproc->start(\&matrix_X_scalar);
T20/s2
$myproc->start(\&rand_matrix);
T21/s2
T22/s2
T23/s2
…………
…………
…………
…………
T20/s3
T21/s3
T22/s3
T23/s3
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
Necesitaremos 2 barreras
T0/s1T4/s1T8/s1
T1/s1T5/s1T9/s1
T2/s1T6/s1T10/s1
T3/s1T7/s1T11/s1
…………
…………
…………
…………
T0/s2T4/s2T8/s2
T1/s2T5/s2T9/s2
T2/s2T6/s2T10/s2
T3/s2T7/s2T11/s2
…………
…………
…………
…………
T0/s3T4/s3T8/s3
T1/s3T5/s3T9/s3
T2/s3T6/s3T10/s3
T3/s3T7/s3T11/s3
$myproc->start(\&matrix_X_scalar);
T20/s1
T21/s1
T22/s1
T23/s1
$myproc->start(\&rand_matrix);
T20/s2
# 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); }
}
T21/s2
T22/s2
T23/s2
…………
…………
…………
…………
T20/s3
T21/s3
T22/s3
T23/s3
$myproc->start(\&sort_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);}
}
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
T20/s1
T0/s1 T4/s1 T8/s1 …………
T21/s1
T1/s1 T5/s1 T9/s1 …………
T22/s1
T2/s1 T6/s1 T10/s1 …………
T23/s1
T3/s1 T7/s1 T11/s1 …………
T0/s2 T4/s2 T8/s2 …………
T20/s2
T21/s2
T1/s2 T5/s2 T9/s2 …………
T22/s2
T2/s2 T6/s2 T10/s2 …………
T23/s2
T3/s2 T7/s2 T11/s2 …………
T20/s3
T0/s3 T4/s3 T8/s3 …………
T21/s3
T1/s3 T5/s3 T9/s3 …………
T22/s3
T2/s3 T6/s3 T10/s3 …………
T23/s3
T3/s3 T7/s3 T11/s3 …………
Maestro-esclavo segmentado
= 120.000 / 4 = 30.000 / 3 = 10.000 + 6666 = 10666 (teórico)
Replica – Versión secuencial
Tiempo
t0
t1
Export
IXF
Load
IXF
Unload
Load
INDEX Statistics
TXT Target DB
Export
IXF
Load
IXF
Unload
Load
INDE
TXT Target DB
• 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 –
Export
IXF
Export
IXF
Versión paralela
Tiempo
Load
IXF
Load
IXF
Export
IXF
Export
IXF
Unload
Load
INDEX Statistics
t0
TXT Target DB
Unload
Load
INDEX Statistics
t1
TXT Target DB
Load
Unload
Load
INDEX Statistics
t2
IXF
TXT Target DB
Load
Unload
Load
INDEX Statistics
t3
IXF
TXT Target DB
Export
Load
Unload
Load
INDEX Statistics
IXF
IXF
TXT Target DB
Export
Load
Unload
Load
INDEX Statistics
IXF
IXF
TXT Target DB
Export
Load
Unload
Load
INDEX
IXF
IXF
TXT Target DB
Export
Load
Unload
Load
INDEX
•En este espacio de tiempo,
IXF
IXF
TXT Target DB
hemos conseguido procesar
Export
Load
Unload
Load
IXF
IXF
TXT Target DB
10 tablas (teóricamente)
Export
Load
Unload
Load
IXF
IXF
TXT Target DB
t4
t5
Statistics
t6
Statistics
t7
INDEX Statistics
INDEX Statistics
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
1.
Hay q guardar
la 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 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
N, CPU
#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;
}
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 dentro
de la función del thread se llaman
datos locales.
• Son ubicados en la pila de cada
thread. Por tanto, se mantienen allí
mientras dura la ejecución de este.
Mutex example
Distintos threads modificando
la variable compartida i
#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=%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;
}
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ísticas
http://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:
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.
#include "mpi.h"
Veamos un ejemplo
trivial
#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 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)
Averiguaremos desde el programa el número de procesos que
participan y la identificación de cada uno.
#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.c
mpirun -np 2 ./a.out
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 enviar
2.
count: número de elementos a enviar
3.
datatype: tipo de dato
4.
dest: Identificación del proceso destino
5.
tag: etiqueta de la comunicación
6.
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 datos
2.
count: número de elementos
3.
datatype: tipo de dato
4.
source: Identificación del proceso origen
5.
tag: etiqueta de la comunicación
6.
comm: Identificación del comunicador
7.
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);
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!
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();
}
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
#include <stdio.h>
#include "mpi.h"
#define N 10
int array[N];
int main() {
int
rank,i;
MPI_Bcast(start, count, datatype, root, comm)
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;
}
1.
2.
3.
4.
5.
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
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=%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();
// 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);
}
max_array=(double *)malloc(nprocs*sizeof(double));
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("\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
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);
}
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;
}
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 //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=%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 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. AddisonWesley, 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.