Download Configuració dels sistemes de informació
Document related concepts
no text concepts found
Transcript
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.