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 anterior | Volver al principio del trabajo | Página siguiente  |