E' uno standard per la comunicazione a scambio di messaggi tra processi a memoria distribuita (host diversi) con i seguenti obiettivi:
Principali funzionalità:
Esistono 2 versioni di MPI
Le comunicazioni punto-punto posso avvenire utilizzando diversi tipi di Network. I principali sono:
Ricompilazione del SRPMS:
wget http://www.open-mpi.org/software/ompi/v1.2/downloads/openmpi-1.2.8-1.src.rpm rpm -ivh openmpi-1.2.8-1.src.rpm cd /usr/src/redhat/SPECS/ rpmbuild -bb openmpi-1.2.8.spec
Nota: Sul nodo in cui avviene la ricompilazione è necessario che il pacchetto torque-devel sia installato per avere il supporto per l'autodiscovery del machinefile e del numero di processori.
kickstart:
rpm -ivh http://rep.fis.unipr.it/install/post/sl52-i386/openmpi-1.2.8-1.i386.rpm
Per usare infiniband occorre la libreria generica libibverbs e quella specifica Mellanox libmthca e libmthca-devel.
Creiamo la directory mpi/ e creiamo al suo interno il file wn.list:
cat > lista-wn.conf << EOF sdlab-wn01 sdlab-wn02 sdlab-wn03 sdlab-wn04 EOF
Repository dei programmi MPI: MPI repository
Il comando per eseguire un job ha un formato del tipo:
mpirun -np 2 --hostfile lista-wn.conf executable
Il programma executable viene eseguito su 2 processi
residenti su host elencati nel file lista-wn.conf.
I processi vengono attivati via ssh dall'host che esegue mpirun.
l'hostfile (detto anche machinefile) ha la seguente sintassi:
#Nodo con singolo processore: sdlab-wn01 #Nodo dual processor ( o dual core): sdlab-wn02 slots=2
La lista degli host puo' essere inclusa nella linea di comando. Esempio:
mpirun -np 2 --host a,b executable
L'applicazione può essere sequenziale. Esempio:
mpirun -np 2 --host sdlab-wn01.fis.unipr.it,sdlab-wn02.fis.unipr.it hostname
Esiste un hostfile di default a livello di sistema:
cat > /etc/openmpi-default-hostfile << EOF sdlab-wn01.fis.unipr.it sdlab-wn02.fis.unipr.it sdlab-wn03.fis.unipr.it sdlab-wn04.fis.unipr.it EOF
Esempio di utilizzo dell'hostfile di default:
mpirun -np 2 hostname
Questo comando lancia 4 copie dell'eseguibile sullo stesso host:
mpirun -np 4 --host sdlab-wn01.fis.unipr.it uptime
Alcune componenti e funzionalità di openMPI sono organizzate in una Architettura Modulare denominata MCA (Modular Component Architecture). Per vedere i moduli disponibili con i relativi parametri:
ompi_info
Un componente denominato btl (Byte transfer layer) si occupa della comunicazione punto-punto.
ompi_info | grep btl
Il seguente comando mostra tutti i parametri relativi ai moduli del componente btl:
ompi_info --param btl all
I moduli btl piu' comuni sono:
Posso selezionare le reti da utilizzare nel seguente modo:
mpirun --mca btl openib,self
Se TCP ha diversi devices (e.g. eth0 e ib0) posso forzare l'uso di uno solo:
mpirun -mca btl tcp,sm,self --mca btl_tcp_if_include eth0
Per default openMPI seleziona automaticamente la rete piu' veloce disponibile.
Quando sottometto un Job con Torque posso specificare il numero o i nomi dei nodi richiesti. Ad esempio:
-l nodes=2 # chiede 2 processori -l nodes=2:ppn=2 # chiede 2 nodi biprocessore (4 processori) -l nodes=sdlab01+sldab02 # chiede 2 specifici nodi -l nodes=2,mem=200mb # rimane in coda finche' non si liberano 2 nodi con 200MB disponibili
Quando il JOB entra in eseguzione, Torque scrive un file con l'elenco dei nodi assegnati.
Il nome di questo file e' accessibile al processo mediante la variabile $PBS_NODEFILE.
Con il comando
NP=$[`cat ${PBS_NODEFILE} | wc --lines`]
il processo puo' ricavare il numero di processori e quindi eseguire:
mpirun -hostfile $NODEFILE -np $NP eseguibile
Lo script di shell (e quindi il comando mpirun) viene eseguito dal primo nodo della lista.
Esempio:
mpi_esegui.bash
wget http://www.fis.unipr.it/home/roberto.alfieri/didattica/matdid/prog/mpi/mpi_esegui.bash sh mpi_esegui.bash qsub -l nodes=2 mpi_esegui.bash
Lo script esegui_mpi.bash puo' essere eseguito nell'ambiente Torque in modo interattivo:
ui> qsub -l nodes=2 -I wn> cat $PBS_NODEFILE wn> sh mpi_esegui.bash wn> exit ui>
Il comando qsub on gestisce gli argomenti dello script, ovvero non posso scrivere
qsub script.sh arg1
Per passare parametri devo usare l'opzione -v:
qsub script.sh -v param1=arg1
All'interno dello script $param1 rappresenta l'argomento.
#include "mpi.h" //Necessaria per le chiamata alle routine MPI
Formato delle chiamate MPI:
rc = MPI_xxxxx(parametri, ....);
Esempio:
rc = MPI_Bsend(&buf,count,data_type,dest_rank,tag,communicator_name)
tipo MPI | Tipo C | Byte |
---|---|---|
MPI_CHAR | signed char | 1 |
MPI_SHORT | signed short int | 2 |
MPI_INT | signed int | 4 |
MPI_LONG | signed long int | 4 |
MPI_UNSIGNED_CHAR | unsigned char | 1 |
MPI_UNSIGNED_SHORT | unsigned short | 1 |
MPI_UNSIGNED | unsigned int | 4 |
MPI_UNSIGNED_LONG | unsigned long int | 4 |
MPI_FLOAT | float | 4 |
MPI_DOUBLE | double | 8 |
MPI_LONG_DOUBLE | long double | 12 |
MPI_BYTE | 8 binary digit | 1 |
MPI_PACKED | packed with MPI_Pack() unpacked with MPI_Unpack() |
nota: La funzione MPI_Type_extent() consente di conoscere la lunghezza di un tipo di dato. Es: MPI_Type_extent(MPI_CHAR, &charlen)
Un Communicator e' l'insieme di processi coinvolti nella comunicazione.
Esiste un Communicator di default, denominato MPI_COMM_WORLD che include tutti
i processi disponibili (quelli richiesti all'avvio).
Ogni processo ha un identificativo numerico Rank assegnato automaticamente.
Il processo che lancia il Job e attiva gli altri ha rank 0.
Servono per inizializzare/terminare l'ambiente MPI e per ottenere informazioni sull'ambiente
MPI_Init (&argc,&argv) //Inizializza l'ambiente MPI MPI_Comm_size (MPI_COMM_WORLD,&size) // scrive in size il numero di processi del communicator MPI_Comm_rank (MPI_COMM_WORLD,&rank) // scrive in rank il Rank del processo chiamante MPI_Get_processor_name(&name,&namelength) //scrive nome dell'host del processo chiamante MPI_Finalize() // Chiude l'ambiente MPI
wget http://www.fis.unipr.it/home/roberto.alfieri/didattica/matdid/prog/mpi/mpi_first.c mpicc mpi_first.c -o mpi_first mpirun -np 2 -host sdlab-wn01,sdlab-wn02 mpi_first mpirun -np 2 mpi_first # si usa /etc/openmpi-default-hostfile
#### BLOCKING SEND/RECEIVE #### MPI_Recv (&buf,count,datatype,source,tag,comm,&status) #source puo' essere MPI_ANY_SOURCE # RECEIVE: Si sblocca quando il dato atteso e' disponbile MPI_Send (&buf,count,datatype,dest,tag,comm) # SEND: Si sblocca quando il buffer di spedizione e' stato svuotato MPI_Ssend (&buf,count,datatype,dest,tag,comm) # SYNCRONOUS SEND: si sblocca quando il destinatario ha iniziato a ricevere. MPI_Bsend (&buf,count,datatype,dest,tag,comm) # BUFFERED SEND: Ritorna quando i dati sono copiati in un buffer specifico MPI_Rsend (&buf,count,datatype,dest,tag,comm) # READY SEND: Da usare quando siamo certi che il destinatario e' in ascolto #### NON BLOCKING SEND/RECEIVE #### MPI_Irecv(&buf,count,datatype,source,tag,comm,&request) #I-RECEIVE: Ritorna immediatamente. #request e' un handle per verificare lo status della richiesta (vedi MPI_Wait e MPI_Test) MPI_Isend (&buf,count,datatype,dest,tag,comm,&request) # I-SEND: Ritorna immediatamente senza attende che i dati vengano copiati nel buffer. #request e' un handle per verificare lo status della richiesta (vedi MPI_Wait e MPI_Test) MPI_Test (&request,&flag,&status) #TEST: verifica lo stato di una request send/receive non bloccante. flag=1 -> operazione completato, flag=0 -> non copletata MPI_Wait (&request,&status) #WAIT: come MPI_Test, ma si blocca finoche' non termina la request
I processi inviano (MPI_Send) al processo root (rank=0) il nome dell'host su cui sono in esecuzione.
Il processo root riceve (MPI_Recv) i dati (in ordine di rank) e li stampa su stdout.
wget http://www.fis.unipr.it/home/roberto.alfieri/didattica/matdid/prog/mpi/mpi_name.c mpicc mpi_name.c -o mpi_name mpirun -np 2 mpi_name # si usa /etc/openmpi-default-hostfile
Eseguire il programma utilizzando il Resource Manager
Sono operazioni che coinvolgono tutti i processi di un Communicator. E' compito del programmatore assicurarsi che tutti i processi partecipino.
Classificazione delle primitive:
MPI_Barrier(comm)
#Ogni processo si blocca fino a quando tutti i processi del Communicator non eseguono MPI_Barrier(): MPI_Bcast (&buffer,count,datatype,root,comm) #send di un messaggio da un processo a tutti gli altri (root spedisce, gli altri ricevono): MPI_Scatter (&sendbuf,sendcnt,sendtype,&recvbuf, recvcnt,recvtype,root,comm) #Un array su un processo root viene distribuito inviando un elemento ad ogni altro processo MPI_Gather (&sendbuf,sendcnt,sendtype,&recvbuf,recvcount,recvtype,root,comm) # Da un array distribuito viene costruito un array sul processo root. MPI_Allgather (&sendbuf,sendcount,sendtype,&recvbuf,recvcount,recvtype,comm) # Da un array distribuito viene costruito un array replicato su tutti i processi MPI_Reduce (&sendbuf,&recvbuf,count,datatype,op,root,comm) # I dati da un array distribuito vengono elaborati con l'operazione 'op'; il risultato # e' scritto nel processo root. MPI_Allreduce (&sendbuf,&recvbuf,count,datatype,op,comm) # Il risultato della riduzione e' replicato su tutti i processi (MPI_Reduce + MPI_Bcast)
Principali OPerazioni per reduce:
OP | function | C-type |
---|---|---|
MPI_MAX | maximum | integer, float |
MPI_MIN | minimun | integer, float |
MPI_SUM | sum | integer, float |
MPI_PROD | product | integer, float |
MPI_LAND | logical AND | integer |
MPI_BAND | bitwise AND | integer, MPI_BYTE |
MPI_LOR | logical OR | integer |
MPI_BOR | bitwise OR | integer, MPI_BYTE |
In tutti gli esempi visti, la comunicazione coinvolgeva sempre due (o più entità). Infatti un'operazione di Send, doveva sempre avere una corrispondente operazione di Receive (discorso analogo per le comunicazioni collettive). Si imponeva in sostanza una sorta di sincronizzazione: i due processi dovevano invocare due funzioni complementari.
Con la funzionalità di One-sided Communication, invece, la comunicazione coinvolge unicamente un'entità. Vengono messe a disposizione infatti delle chiamate che consentono di leggere e scrivere nella memoria di un altro processo. Naturalmente, affinché ciò sia possibile, tale processo dovrà aver condiviso inizialmente una quantità di memoria.
Molte applicazioni distribuite si applicano ad ampi domini di dati con architettura regolare (1-D, 2-D, ..) che vengono partizionati ed elaborati contestualmente da diversi task (SIMD - Single Instruction Multiple Dtata o SPMD - Single Program Multiple Data)
Pro [Scalabile con quantita' di dati] Contro
[Generalemnte vantaggioso solo per grandi quantita' di
dati]
mpi_cpi.c
Nell'integrazione numerica per il calcolo di PiGreco abbiamo un dominio 1-D di n intervalli. Se disponiamo di p processi affidiamo all'i-esimo processo il sottominio con gli intervalli (i,i+p,i+2p,i+3p,..,i+n-1). Al termine sommiamo tutti i contribuiti:
wget http://www.fis.unipr.it/home/roberto.alfieri/didattica/matdid/prog/mpi/mpi_cpi.c mpicc mpi_cpi.c -o mpi_cpi mpirun -np 2 mpi_cpi
Eseguire il programma utilizzando il Resource Manager
Distribuzione delle funzioni tra piu' soggetti. Decompongo il lavoro in base al lavoro che deve essere svolto
(MPMD) * Pro [scalabile con il numero di elaborazioni indipendenti] Contro [vantaggioso solo per elaborazioni sufficientemente complesse]
E' una architettura in cui un nodo, denominato Manager (e.g. rank 0) gestisce i "descrittori di problemi" e li distribiusce agli altri nodi, denominati Worker, generalmente su richiesta. Vantaggi: load-balancing, fault-tolerance (se un worker fallisce nell'esecuzione di un task il problema viene passato dal manager ad un altro worker).
mpi_cpi_mc.c
Ogni Worker esegue lo stesso programma sequenziale partendo da un seed diverso. Al termine il Manager calcola il valore medio.
mpicc mpi_cpi_mc.c -o mpi_cpi_mc mpirun -np 4 mpi_cpi_mc
Eseguire il programma utilizzando il Resource Manager
Un sistema discreto viene simulato su di una griglia cartesiana in cui tutti i nodi evolvono in modo sincrono grazie ad un a funzione di trasformazione che dipende dallo stato dei nodi vicini.
Esempio bi-dimensionale:
Esempi di funzione di trasformazione:
xi,j(t+1)=f( xi,j(t),xi-1,j(t),xi+1,j(t),xi,j-1(t),xi,j+1(t) )
Idealmente la migliore strategia di aggiornamento e' quella della doppia griglia t0 e t1. L'aggiornamento avviene nel seguente modo:
Il modello non e' scalabile: al crescere della dimensione del problema diventa di difficile gestione sia la complessita' spaziale (spazio in memoria) che la complessita' temporale (tempo di esecuzione).
Per le applicazione che utilizzano l'intorno d Moore viene spesso utilizzata una strategia, basata su di un'unica griglia, denominata red-black:
Queste applicazioni sono naturalmente parallelizzabili con la Domain Decomposition: la griglia Cartesiana viene scomposta in P sotto-griglie, ciascuna delle quali viene elaborata da un processo del communicator.
Le comunicazioni sono locali, ovvero sono punto-punto tra i nodi adiacenti. La topologia ideale della rete e' la mesh (griglia).
Gli automi cellulari sono adatti a rappresentare e simulare l'evoluzione globale di fenomeni che dipendono solo da leggi locali. Esempi di fenomeni di questo tipo sono il comportamento fisico dei gas perfetti, l'evoluzione di una popolazione, il movimento dei filamenti di DNA in una soluzione.
Proprieta' fondamentali:
L'esempio classico e' il gioco "Life".
http://www.soe.ucsc.edu/classes/ams290b/Winter08/Homeworks/MPI_homework/MPI_game_of_life_project.pdf
http://bccd.net/ver2_2/wiki/index.php/Game_of_Life
Il seguente programma applica una strategia a doppia griglia con intorno di Moore. La griglia e' suddivisa verticalmente in N parti; ogni parte e' aggiornata da uno degli N processi.
Il processo deve gestire le condizioni al contorno
mpic++ mpi_life.cpp -o mpi_life
mpirun -np 3 mpi_life 10 10 10
Esercizio: Modificare il programma applicando la strategia Red-Black con update sull'intorno di Von Neumann.
Il metodo delle differenze finite è un metodo per risolvere numericamente equazioni differenziali, prevalentemente ordinarie anche se sono spesso usate come schema di avanzamento nel tempo per problemi alle derivate parziali. L'idea di base di questi metodi è di sostituire alle derivate i rapporti incrementali, dato che il limite di questi è appunto la derivata. Il sistema viene discretizzato e fatto evolvere a intervalli di tempi finiti. Ad ogni step temporale su ogni nodo della griglia viene applicata la funzione di transizione, che generalmente dipende dai nodi vicini.
Esempio della propagazione del calore in una dimensione ( 1): <math> \frac{\partial u\;}{\partial t\;}=c\frac{\partial^2 u\;}{\partial x^2\;} \qquad 0\le x\le L\;\; \qquad t\ge 0\; </math>
Passaggio alle differenze finite: <math> \frac{u^{k+1}_i-u^{k}_i}{\Delta t} = c\frac{u^{k}_{i+1}-2u^{k}_i+u^{k}_{i-1}}{(\Delta x)^2} \qquad \qquad </math>
Funzione di transizione: <math> u^{k+1}_i = u^{k}_i + c\frac{\Delta t}{(\Delta x)^2}(u^{k}_{i+1}-2u^{k}_i+u^{k}_{i-1}) </math>
Questa e' la versione sequenziale ( LLNL)
wget http://www.fis.unipr.it/home/roberto.alfieri/didattica/matdid/prog/ser/heat_ser.c gcc heat_ser.c -o heat_ser ./heat_ser
Se T1 è il tempo di esecuzione dell'algoritmo sequenziale e TP è il tempo dell'algoritmo parallelo con P processi, misuriamo il rendimento della parallelizzazione come: Speedup= T1/ TP oppure Efficienza= T1/ (TP*P) = SpeedUp/P
Idealmente Speedup coincide con P, mentre l'Efficenza è pari a 1.
Questo andamento non e' realistico per 2 motivi:
Esercizio: Scrivere un programma che realizza la riduzione somma tra N processi utlizzando N comunicazioni punto-punto. Confrontare i tempi di esecuzione con la primitiva MPI_reduce().
Modello piu' realistico per lo Speedup, ipotizzando di minimizzare il tempo di Idle (source DBPP): <math> Speedup=\frac{T_{par}+T_{nonpar}}{T_{nonpar}+\frac{T_{par}}{P}+\sum_{msg}(Latency+MessageLength/Bandwidth)} </math>
MPI_Wtime() // Ritorna il wall clock time in secondi MPI_Wtick() // ritorna la risoluzione di MPI_Wtime (0.000001)
wget http://www.fis.unipr.it/home/roberto.alfieri/didattica/matdid/prog/mpi/mpi_time.c mpicc mpi_time.c -o mpi_time mpirun -np 2 mpi_time
wget http://www.fis.unipr.it/home/roberto.alfieri/didattica/matdid/prog/mpi/mpi_bandwidth.c wget http://www.fis.unipr.it/home/roberto.alfieri/didattica/matdid/prog/mpi/mpi_latency.c mpicc mpi_bandwidth.c -o mpi_bandwidth mpicc mpi_latency.c -o mpi_latency mpirun -np 2 -host sdlab-wn01,sdlab-wn02 mpi_bandwidth # bandwidth della LAN mpirun -np 2 -host sdlab-wn01,sdlab-wn02 mpi_latency # latenza della LAN mpirun -np 2 -host sdlab-wn01,sdlab-wn01 mpi_bandwidth # bandwidth SMP mpirun -np 2 -host sdlab-wn01,sdlab-wn01 mpi_latency # latenza SMP
Esempi di Latenza e Bandwidth su alcuni cluster:
Cluster | Network | Lat.(μs) | Band.(MB/s) | data |
---|---|---|---|---|
sdlab | tcp | 500 | 11 | 200801 |
grid-pr | tcp | 117 | 11 | 200801 |
albert | tcp | 700 | 11 | 200801 |
Quarto | openib | 27 | 450-670 | 200801 |
sdlab | shmem | 300 | 450 | 200801 |
grid-pr | shmem | 4 | 337 | 200801 |
albert | shmem | 12 | 110 | 200801 |
Quarto | shmem | 4 | 800 | 200801 |
Albert2 | shmem | 3 | 450 | 20100407 |
Albert2 | ofud | 16 | 275 | 20100407 |
Albert2 | tcp | 48 | 114 | 20100407 |
Esempio: invio di un messaggio di 10 byte con tcp su sdlab: Tmsg=Latency+MessageLength/Bandwidth=500e-6 + 10/(11e+6)= 500μs + 1μs
Mpptest e' un tool sviluppato da ANL per determinare le performance di MPI
wget http://www.fis.unipr.it/home/roberto.alfieri/didattica/matdid/prog/mpi/perftest.tar.gz tar xzvf perftest.tar.gz cd perftest-1.4b ./configure --with-mpi=/opt/openmpi/1.2.6 make mpptest
Esempio calcolo latenza. Vengono scambiati messaggi da 1 a 50 byte con incremento di 2. La serie è ripetuta 4 volte. L'output e' in formato gnuplot:
mpirun -np 2 mpptest -gnuplot -reps 4 -size 1 50 2
Esempio di calcolo del throughput. Vengono scambiati messaggi da 1000 a 10000 byte con incremento di 1000:
mpirun -np 2 mpptest -gnuplot -reps 4 -size 1000 10000 1000
Visualizzazione dei dati con gnuplot
Per la latenza si visualizza il tempo di trasferimento in funzione del numero di byte trasferiti.
Per il Throughput si visualizza il Transfer Rate (byte/sec) in funzione del numero di byte trasferiti.
Per la misura delle prestazioni nelle comunicazioni collettive si usa goptest.
Il cluster di calcolo ha 2 User Interface:
Code disponibili:
OpenMPI si trova in /opt/openmpi/1.2.6/bin/:
/opt/openmpi/1.2.6/bin/mpicc /opt/openmpi/1.2.6/bin/mpirun
La coda da usare e' albert
qstat -Q pbsnodes | grep "state = free" -B1 /opt/openmpi/1.2.6/bin/mpirun -host grid-wn08,grid-wn09 mpptest -gnuplot -reps 4 -size 1 50 2 qsub -q albert -l nodes=grid-wn26.pr.infn.it+grid-wn27.pr.infn.it mpi_esegui.bash
/opt/openmpi/1.2.6/bin/mpirun -host grid-wn08,grid-wn09 mpi_life2 1000 1000 4
Tempi di Comunicazione di una colonna sul cluster Albert:
1K righe (4KB) con TCP → 0.7x10-3+4x103/11x106 = 0.7x10-3+0.36x10-3 = 1.06x10-3
1K righe (4KB) con ShMem → 0.012x10-3+4x103/110x106 = 0.012x10-3+0.036x10-3 = 0.048x10-3
100K righe (400KB) con TCP → 0.7x10-3+400x103/11x106 = 0.7x10-3+36x10-3 = 36x10-3
100K righe (400KB) con ShMem → 0.012x10-3+400x103/110x106 = 0.012x10-3+3.6x10-3 = 3.6x10-3
Esercizio: determinare lo Speedup teorico e sperimentale per 2 nodi (con comunicazioni tcp e smp) di un ciclo di Update in funzione della dimensione del problema (numero di elementi di una griglia bidimensionale quadrata).
Esercizio: determinare lo Speedup teorico e sperimentale per una matrice 10000x10000 in funzione del numero di nodi.
Per vedere se i thread sono alilitati:
ompi_info | grep Thread
MPI-2 supporta i thread mediante la primitiva MPI_Init_thread (da utilizzare al posto di MPI_Init) Il supporto prevede diversi livelli si sicurezza:
Sintassi:
int MPI_Init_thread(int *argc, char ***argv, int required, int *provided)
Required e' il livello richiesto. Provided e' il livello abilitato o il maggiore livello supportato.
Programma ibrido:
#include "mpi.h" int main(int argc, char **argv){ int rank, size, ierr, i; MPI_Init(&argc,&argv[]); MPI_Comm_rank (...,&rank); MPI_Comm_size (...,&size); #pragma omp parallel for for(i=0; i<n; i++) { printf("do some work\n"; } MPI_Finalize();
Game of Life ibrido MPI/openMP: http://www.ukhec.ac.uk/publications/tw/mixed.pdf