l4 aplicatii mpi

Felicia Ionescu, Valentin Pupezescu Laborator de Calcul paralel

Lucrarea 4 - APLICATII MPI

In aceasta lucrare se vor dezvolta mai multi algoritmi paraleli folosind biblioteca MPI (Message Passing Interface) din distribuia open-source OpenMPI. Se incepe cu instalarea si configurarea bibliotecii OpenMPI (dac nu a fost realizat deja), apoi se testeaza cativa algoritmi de baz simpli, care sa permita intelegerea functionarii programelor MPI. Dupa aceasta, studentii vor realiza si testa mai muli algoritmi paraleli mai compleci.

Experimentele se pot efectua att n clusterele Linux din laboratoarele B125a i B138 (ITEMS), ct i n clusterul HPC Dell PowerEdge, programele sunt compatibile datorit bibliotecii OpenMPI care se poate instala pe oricare dintre sisteme.

4.1. Instalarea i utilizarea bibliotecii OpenMPI

n clusterele Linux-Ubuntu din laboratoarele B125a i B138, mai intai se instaleaz g++ (nu

este instalat implicit in distributia Ubuntu 12.04) si se face Update la sistem. Distributia in format surs a versiunii OpenMPI curente stabile (openmpi-1.6.5.tar.gz) se obtine de pe site-ul oficial www.open-mpi.org.

Sunt mai multe posibilitati de instalare si executie a programelor MPI in retea. Este posibil ca biblioteca MPI sa fie instalata intr-un sistem de fisiere partajate (NFS Network File System) sau se pot instala copii separate pe fiecare host, cu conditia ca arborele de executie al instalarii (run-time tree) sa fie acelasi in toate statiile din cluster. Pentru aceasta este suficient ca directorul de instalare (prefix) fie acelasi in toate statiile.

In continuare vom exemplifica instalarea in cea de-a doua modalitate (copii separate instalate local in fiecare statie)

4.1.1. Instalare OpenMPI n clusterele Linux-Ubuntu

Instalarea in directorul implicit /usr/local. Cu un user cu drepturi de administrator se face download fisierul openmpi-1.6.2.tar.gz (sau ultima versiune stabila, dac a aprut alta) si se execut urmatoarele comenzi: tar xvf openmpi-1.6.2.tar.gz cd openmpi-1.6.2 ./configure sau ./configure --prefix /usr/local sudo make all install

Dupa aceasta se introduc linkuri simbolice in /usr/lib catre bibliotecile MPI din /usr/local/lib/ $cd /usr/lib /usr/lib$ sudo ln --symbolic -T /usr/local/lib/libmpi.so.1 libmpi.so.1 /usr/lib$ sudo ln --symbolic -T /usr/local/lib/libopen-pal.so.4 libopen-pal.so.4 /usr/lib$ sudo ln --symbolic -T /usr/local/lib/libmca_common_sm.so.3 \ libmca_common_sm.so.3 /usr/lib$ sudo ln --symbolic -T /usr/local/lib/libopen-rte.so.4 libopen-rte.so.4

Se d restart si se testeaza unele comenzi. Daca totul a fost instalat corect, comanda mpicc -show afiseaza:

1

Lucrarea 4 Aplicatii MPI

gcc -I/usr/local/include -pthread -L/usr/local/lib -lmpi -ldl -lm -Wl,--export-dynamic -lrt -lnsl -lutil -lm -ldl Comanda ompi_info afiseaza: Package: Open MPI user@Ubuntu-12-1 Distribution Open MPI: 1.6.2 Open MPI SVN revision: r27344 Open MPI release date: Sep 18, 2012 Open RTE: 1.6.2 Open RTE SVN revision: r27344 Open RTE release date: Sep 18, 2012 OPAL: 1.6.2 OPAL SVN revision: r27344 OPAL release date: Sep 18, 2012 MPI API: 2.1 Ident string: 1.6.2 Prefix: /usr/local .......................

Instalarea OpenMPI ntr-un director oarecare. Daca se doreste instalarea OpenMPI n alt director dect directorul implicit (/usr/local), de exemplu in /usr/local/openmpi se specific acest director ca argument al optiunii -prefix al comenzii configure: ./configure --prefix /usr/local/openmpi sudo make all install

Calea ctre executabile (/usr/local/openmpi/bin) se adauga in PATH in fisierul .profile din directorul HOME al userului care utilizeaza biblioteca - ultima linie: PATH="/usr/local/openmpi/bin:$PATH"

Linkurile simbolice trebuie sa contina targetul /usr/local/openmpi/lib, de exemplu: /usr/lib$ sudo ln --symbolic -T /usr/local/openmpi/lib/libmpi.so.1 \ libmpi.so.1 4.1.2 Instalarea OpenMPI n HPC Dell PowerEdge n HPC, administratorul de sistem a instalat biblioteca OpenMPI (versiunea 1.6.2) n directorul /opt/openmpi. Toate setrile au fost deja efectuate i se pot executa compilri i lansri de programe OpenMPI pe toate cele 64 de procesoare (cores) ale nodurilor HPC. n plus, software-ul de cluster Rocks asigur replicarea automat a directoarelor utilizatorilor pe cele 4 noduri, astfel nct nu este necesar copierea unui executabil MPI pe fiecare nod.

4.1.3 Configurare SSH pentru comunicaia cu autentificare fr parol

n clusterele Linux (laborator B125a i B138) trebuie instalat serverul SSH pe fiecare dintre

staii. Dintr-un utilizator cu drepturi de administrare se instaleaza serverul SSH cu comanda: sudo apt-get install openssh-server

Se verific fiierul de configurare /etc/ssh/sshd_config astfel nct sa conin opiunile: RSAAuthentication yes PubkeyAuthentication yes

2


Se editeaz fiierul /etc/hosts (cu sudo gedit) astfel ca sa contina numele si adresa staiilor.

n laboratorul B125a adresele IP sunt statice i fiierul /etc/hosts arat astfel: 141.85.107.201 h1 141.85.107.202 h2 141.85.107.203 h3 ................... 141.85.107.216 h16

n laboratorul B138 (ITEMS) adresele IP sunt dinamice (prin router DHCP), dar s-a fcut rezervarea adreselor n router, astfel ca acestea s rmn nemodificate. Pentru aceasta se intr n administrarea routerului (http://191.168.0.1) i se selecteaza LAN IP Setup. Se introduce adresa fizica MAC si adresa de retea in tabela Address Reservation (fie manual, fie selectatnd adresa dispozitivului respectiv din Address Reservation Table). Fiierul /etc/hosts arat astfel: ITEMS01.imag.pub.ro 192.168.0.101 ITEMS02.imag.pub.ro 192.168.0.102 ................................. ITEMS12.imag.pub.ro 192.168.0.112

Pentru fiecare utilizator (standard sau administator), pentru care se doreste comunicatia SSH fara parola, se executa urmatoarele setari.

a) Pe fiecare main, pentru fiecare utilizator care va comunica in retea, se genereaz o pereche de chei public-privat cu comanda: $ ssh-keygen -t dsa

Nu se da passphrase de stocare a cheii private. Implicit (pentru utilizatorul user) aceste chei se depun n locaiile: Your identification has been saved in /home/user/.ssh/id_dsa Your public key has been saved in /home/user/.ssh/id_dsa.pub

b) Pentru conectarea ssh la localhost fara parola este necesar ca si cheia publica generata pentru fiecare host/user sa fie copiata in propria lista de chei autorizate authorized_keys cu comenzile: cd .ssh cat id_dsa.pub >> authorized_keys

Dup aceasta setare trebuie sa nu se ceara parola la conexiunea la localhost cu comanda: ssh localhost

c) Se copiaz cheia public generat a fiecrei maini pe toate celelalte maini care trebuie s accepte autentificarea fr parol prin comanda: $ ssh-copy-id user@remotehost

Acestea se adaug n /home/username/.ssh/authorized_keys. Se verific autentificarea reciproc fr parol, din ambele maini, prin comanda: $ ssh user@hostname

Dac nu se cere parola la autentificare, nseamn c s-a realizat corect conexiunea ssh cu autentificare fr parol.

n clusterul HPC sunt instalate de administrator serverele ssh i este setat configurarea pentru

comunicaia cu autentificare fr parol i sincronizarea (replicarea) directoarelor utilizatorilor n toate cele 4 noduri.

3


4.1.4. Compilarea si executia programelor OpenMPI

MPI este o bibliotec pentru dezvoltarea programelor paralele portabile n aplicaii C i Fortran executate att n multicalculoatore ct i n reele de calculatoare.

Biblioteca MPI este standard: MPI 1.0 (1994), MPI 2.0 (1997) [MPI09] i ofer diferite implementri: MPICH (cu surs liber), OpenMPI, MPIPRO, LAM etc.

Programele MPI se execut (cu comanda mpirun sau mpiexec) sub controlul unui server (process manager mpd, hydra, gforker, smpd, orte) care lanseaz n execuie procesele MPI pe mainile specificate direct sau ntr-un fiier de configurare (hostfile). Comunicaia ntre procesele MPI folosete n general protocolul ssh (Secure Shell).

Programarea paralel folosind biblioteca MPI este explicit: programatorul este responsabil cu crearea i distribuirea proceselor i cu transferul de mesaje ntre acestea, folosind construcii MPI.

Biblioteca MPI ofer sute de funcii; cu puine excepii, funciile MPI returneaz un cod de eroare (numr ntreg - de tipul int, care este 0 la execuia corect). Funciile MPI de baz sunt:

int MPI_Init initializeaz execuia proceselor MPI int MPI_Finalize termin execuia proceselor MPI int MPI_Comm_size determina numarul de procese MPI int MPI_Comm_rank determina rangul procesului MPI int MPI_Send transmiterea blocant a unui mesaj int MPI_Recv receptionarea blocant a unui mesaj Pentru compatibilitate, MPI definete propriile tipuri de date i corespondena cu tipurile

limbajului de implementare (C /C++ sau Fortran.) De exemplu, n C/C++ o parte din tipurile de date i corespondena cu tipurile MPI: Tip de date MPI Tip de date C MPI_CHAR signed char MPI_SHORT signed short int MPI_INT signed int MPI_FLOAT float MPI_DOUBLE double Utilizarea bibliotecii MPI se poate face de orice utilizator (standard sau administrator) pentru

care s-a setat comunicatia ssh fr parol. Descrierea functiilor bibliotecii OpenMPI se gseste pe site-ul oficial (http://www.open-

mpi.org/doc/current/) si in paginile man pe orice calculator pe care este instalata biblioteca. Cel mai simplu program MPI:

// Hello_MPI.c #include #include // Se poate lansa cu oricate procese int main(int argc, char *argv[]) { int rank, len; char hostname[MPI_MAX_PROCESSOR_NAME]; MPI_Init (&argc,&argv); MPI_Comm_rank (MPI_COMM_WORLD,&rank); MPI_Get_processor_name(hostname, &len); hostname[len] = 0; // sir terminat cu null printf ("Hello MPI - Process %d host %s\n", rank, hostname); MPI_Finalize(); return 0; }

4


Pentru aflarea numelui hostului n care are loc executia se foloseste functia MPI : int MPI_Get_processor_name(char * hostname, int* len)

Bufferul n care se citete numele hostului (hostname) trebuie s aib lungimea suficient ca s ncap numele staiei (MPI_MAX_PROCESSOR_NAME).

Compilarea acestui program MPI se face cu comanda: $ mpicc Hello_MPI.c -o Hello_MPI

Comanda de compilare mpicc este un wrapper pentru invocarea compilatorului gcc cu optiunile necesare (bibliotecile de inclus).

Pentru executia cu mai multe procese pe hostul local (de exemplu pe hostul h1) se seteaz numrul de procese in optiunea np a comenzii mpirun: $ mpirun -np 3 Hello_MPI Hello MPI Process 0 host h1 Hello MPI Process 2 host h1 Hello MPI Process 1 host h1

Functionarea MPI in mod SPMD. Daca se doreste executia aceluiai program n mai multe statii (mod SPMD Single Program, Multiple Data), se creeaz un fisier (hosts) care contine numele statiilor si numarul de slot-uri (procesoare disponibile pe care vor fi lansate procese MPI) pentru fiecare dintre ele; de ex. pe HPC: $cat hosts_hpc hpc slots=1 compute-0-1 slots=1 compute-0-2 slots=1 compute-0-3 slots=1

Statiile care se pot nscrie in fiierul hosts trebuie sa fie din cele incluse in fisierul /etc/hosts (cu adresa IP a fiecareia) si pentru care s-a setat comunicatia ssh fara parola pentru userul respectiv. Dup definirea fisierului hosts, se da acest fisier ca parametru opiunii hostfile a comenzii mpirun: $ mpirun -hostfile hosts_hpc -np 10 Hello_MPI Hello MPI - Proces 0 host hpc.intern Hello MPI - Proces 4 host hpc.intern Hello MPI - Proces 8 host hpc.intern Hello MPI - Proces 5 host compute-0-1.local Hello MPI - Proces 9 host compute-0-1.local Hello MPI - Proces 1 host compute-0-1.local Hello MPI - Proces 7 host compute-0-3.local Hello MPI - Proces 2 host compute-0-2.local Hello MPI - Proces 3 host compute-0-3.local

Functionarea este corect dac pe toate nodurile se gasesc aceeasi utilizatori si aceleasi fisiere executabile cu acelasi nume si cale n ierarhia de fiiere. n HPC aceste condiii sunt asigurate prin software-ul de cluster (Rocks). n clusterele din laboratoarele B125a sau B138, trebuie copiat manual fiierul executabil pe fiecare staie, n aceeai cale. Daca acest lucru este dificil, trebuie instalat NFS.

Dac nu este instalat nici un planificator de procese (resource manager SLURM, Condor, PBS etc.), aa cum este cazul atr n laborator ct i n HPC, procesele sunt creeate i distribuite n execuie de modulul de control al execuiei din biblioteca OpenMPI, ORTE (OpenMPI Real-Time Executive).

5


Numrul de procese care se creeaz este dat de argumentul opiunii np; n lipsa acestei opiuni se creeaz attea procese ct este suma slots din fiierul dat ca argument opiunii hostfile; de exemplu, pentru fiierul dat hosts_hpc se vor creea 4 procese care se distribuie n cele 4 noduri, n ordinea din lista din hosts_hpc. Dac argumentul np este mai mare dect suma slots din list, se reia distribuirea n aceeai ordine, pn ce se creeaz toate procesele, aa cum se vede n exemplul dat.

Functionarea MPI n mod MPMD. Se pot lansa programe diferite pe host-uri diferite (modul Multiple Programs, Multiple Data - MPMD) cu comanda: $ mpirun --app appfile

Fisierul de executie apppfile conine cte un fiier executabil pentru fiecare host. Se creeaz nc trei fiiere surs Hello_MPI_v0.c, Hello_MPI_v1.c i Hello_MPI_v2.c care afieaz i versiunea de program (v0, v1, v2) i se adaug versiunea i la numele executabilului. Se creeaz fiierul appfile_hpc astfel: $ cat appfile_hpc # Comments are supported; comments begin with # # Application context files specify each sub-application in the # parallel job, one per line. -np 1 -host user@hpc /home/user/Hello/Hello_MPI -np 1 -host user@compute-0-0 /home/user/Hello/Hello_MPI_v0 -np 1 -host user@compute-0-1 /home/user/Hello/Hello_MPI_v1 -np 1 -host user@compute-0-2 /home/user/Hello/Hello_MPI_v2 Se lanseaz execuia cu comanda: $ mpirun --app appfile_hpc Programul afieaz mesajele: Hello MPI - Process 0 host hpc.intern Hello MPI v1 - Process 1 host compute-0-1.local Hello MPI v2 - Process 2 host compute-0-2.local Hello MPI v3 - Process 3 host compute-0-3.local Exerciiul E4.1.a Compilai i executai programul Hello_MPI.c cu diferite valori ale numrului de procese i hosturi n clusterul local i pe HPC. Experimentai modurile de execuie SPMD i MPMD.

4.1.6. Comunicaii MPI Biblioteca MPI implementeaz att comunicaii punct-la-punct ct i comunicaii de grup

(colective), transferndu-se mesaje formate din vectori de date de un tip de date. n MPI sunt definite grupuri de procese i contexte de comunicaie (communicators

comunicatori). Un grup este o colecie ordonat de procese, fiecare proces cu un numr de identificare (rank rang, id), care este folosit ca nume pentru comunicaiile ntre procese. Numerele rank ncep cu 0 i sunt n continuare, n ordine.

Un comunicator este un context de comunicaie ntre procese MPI; exist 2 tipuri: Intra-comunicator comunicator definit ntr-un singur grup de procese, att pentru

comunicaii punct-la-punct, ct i pentru comunicaii colective Inter-comunicator definete comunicaia ntre dou grupuri de procese disjuncte. Toate implementrile MPI definesc un intra-comunicator implicit (reprezentat prin constanta

MPI_COMM_WORLD), care cuprinde grupul de procese creat la iniializare (MPI_Comm_Init). Pentru definirea altor grupuri de procese i comunicatori exist funcii MPI speciale.

6


Pentru definirea dinamic a altor procese i regiuni paralele exist funcia MPI_COMM_SPWAN, dar aceasta este foarte costisitoare ca timp de execuie i nu este recomandat (nici n standardul MPI, nici n doc. de implementare). De aceea, n general n MPI sunt preferai algoritmii cu o singur reg paralel.

Comunicaii MPI punct-la-punct. Biblioteca MPI implementeaz att comunicaii punct-la-

punct ct i comunicaii de grup (colective) prin functii de transfer multiplu. O comunicaie punct-la-punct are loc ntre 2 procese dintr-un comunicator. Procesul surs

trimite un mesaj (send) ctre procesul destinaie (care execut funcia receive) Completarea unei comunicaii nseamn c transferul mesajului s-a terminat i locaiile de

memorie folosite (bufferul) pot fi accesate n siguran: la transmitere (send), poate fi reutilizat bufferul de tranmisie la recepie (receive), pot fi folosite variabilele recepionate n bufferul de recepie Modurile de comunicaie MPI difer dup modul de completare a transferului: blocante revenirea din funciile apelate nseamn c tranferul este complet ne-blocante funciile revin imediat, dar utilizatorul trebuie s testeze completarea Funcia de transmitere blocant:

int MPI_Send (void *buffer, int count, MPI_Datatype datatype, int dest, int tag, MPI_Comm comm) Tipul i semnificaia argumentelor este urmtoarea:

buffer - adresa unde este memorat mesajul la transmitor count - numrul de date care se transmit datatype - tipul datelor transmise dest - adresa (rangul) procesului destinaie (receptor) tag - markerul mesajului comm - comunicatorul n care are loc transmisia

Funcia de recepie blocant: int MPI_Recv (void *buffer, int count, MPI_Datatype datatype,

int source, int tag, MPI_Comm comm, MPI_Status *status) Starea comunicaiei se obine ntr-o structur de tip MPI_Status: typedef struct MPI_Status { int MPI_SOURCE; int MPI_TAG; int MPI_ERROR; ..../* inf. privind nr. de octeti receptionati*/ }; Procesul receptor poate recepiona de la orice proces surs (dac se specific

MPI_ANY_SOURCE) i cu orice marker de mesaj (MPI_ANY_TAG) Pentru execuia corect a unei comunicaii este necesar ca: Procesele transmitor i receptor s aib adrese (rang) valide n acelai comunicator Mesajele s aib acelai marker (tag) Bufferul de recepie s fie suficient de mare astfel nct s ncap mesajul primit Dup terminarea recepiei, procesul receptor poate obine urmtoarele informaii: Sursa real a mesajului (MPI_SOURCE direct din structura de tip MPI_Status) Markerul real al mesajului (MPI_TAG direct din structura de tip MPI_Status)

7


Numrul real de date recepionate se obine n variabila indicat de pointerul count - din structura de tip MPI_Status, prin apelul funciei:

int MPI_Get_count(MPI_Status *status,MPI_Datatype datatype,int *count)

Exemplu Send_Receive_MPI.c // Send_Receive_MPI.c #include #include // Se lanseaza in executie cel putin 2 procese MPI int main(int argc, char *argv[]) { int rank, i, count, len = 8; float sendbuf[100], recvbuf[100]; MPI_Status status; MPI_Init (&argc,&argv); MPI_Comm_rank (MPI_COMM_WORLD, &rank); if(rank == 0) { // procesul transmitator for(i = 0; i < len; ++i) sendbuf[i] = i; MPI_Send(sendbuf, len, MPI_FLOAT, 1, 55, MPI_COMM_WORLD); } else if (rank == 1){ // procesul receptor MPI_Recv(recvbuf, 100, MPI_FLOAT, MPI_ANY_SOURCE, 55, MPI_COMM_WORLD, &status); MPI_Get_count(&status, MPI_FLOAT, &count); printf("Procesul %d a primit %d numere de la procesul %d \n", rank, count, status.MPI_SOURCE); for (i = 0; i < count; i++) printf(%4.0f ); printf(\n); } MPI_Finalize(); return 0; } Compilare : $ mpicc Send_Receive_MPI.c -o Send_Receive_MPI Execuie: $ mpirun -np 2 Send_Receive_MPI Mesajul afiat la consol : Procesul 1 a primit 8 numere de la procesul 0: 0 1 2 3 4 5 6 7

Comunicaii colective MPI. Comunicaiile colective sunt sincrone, adic funciile nu revin dect dup ce s-a terminat transferul. Aceasta funcionare asigur sincronizarea ntre procesele comunicante; de ex. ntre procesul root si toate celelalte procese n comunicaiile one-to-all, all-to-one: procesul root nu continu dect dup ce s-au term toate transferurile. Dar procesele care nu comunic ntre ele pot s termine operaiile colective asincron i, dac este necesar sincronizarea, trebuie s apelm explicit MPI_Barrier().

MPI_Barrier implementeaz o operaie de sincronizare (barier) ntre toate procesele din comunicatorul dat ca parametru:

int MPI_Barrier (MPI_Comm comm); MPI_Bcast - operaie de difuziune unul-la-toate (one-to-all) prin care procesul root trimite

count date de tipul datatype din bufferul buffer, tuturor proceselor din comunicatorul dat ca parametru (comm); prototipul funciei MPI_Bcast() : int MPI_Bcast(void *buffer, int count, MPI_Datatype datatype, int root, \ MPI_Comm comm)

8

Felicia Ionescu, Valentin Pupezescu Laborator de Calcul paralel Exemplu - Bcast_MPI.c: // Bcast_MPI.c #include #include /* Executie cu oricate procese */ int main (int argc, char *argv[]) { int rank, root = 0, buffer[8]; MPI_Init (&argc, &argv); MPI_Comm_rank (MPI_COMM_WORLD, &rank); if (rank == root) for (i = 0; i < 8; i++) buffer[i] = i; MPI_Bcast (&buffer, 8, MPI_INT, root, MPI_COMM_WORLD); printf("P%d: ); for (i = 0; i < 8; i++) printf(%4d,buffer[i]); printf(\n); MPI_Finalize(); return 0; } MPI_Gather () comunicaie toi-la-unul (all-to-one) - toate procesele transmit date procesului root, care le asambleaz ntr-un vector, n ordinea rangului proceselor (rank). int MPI_Gather(void* sendbuf,int sendcnt,MPI_Datatype sendtype, \ void* recvbuf,int recvcnt,MPI_Datatype recvtype,int root,MPI_Comm comm)

Toate argumentele au semnificaie numai n procesul root; pentru celelalte procese au semnificaie numai sendbuf, sendcount, sendtype, root i comm.

Nu se admite suprapunerea bufferelor recvbuf i sendbuf. Dac datele aferente procesului root exist deja n bufferul de recepie exact n poziia dorit, nu se mai face transferul pentru root i se paseaz ca argument sendbuf MPI_IN_PLACE (numai n procesul root) .

Dac se colecteaz blocuri de date de dimensiuni diferite, se folosete MPI_Gatherv().

MPI_Scatter() - comunicaie unul-la-toi (one-to-all): procesul root transmite partiii de date diferite fiecrui proces din comunicator, n ordinea rangului. int MPI_Scatter(void* sendbuf,int sendcnt,MPI_Datatype sendtype, \ void* recvbuf,int recvcnt,MPI_Datatype recvtype,int root, MPI_Comm comm)

Toate argumentele au semnificaie numai n procesul root, pentru celelalte procese au semnificaie numai recvbuf, recvcount, recvtype, root i comm; argumentele root i comm trebuie s aib aceeai valoare pentru toate procesele. Nu se admite suprapunerea bufferelor recvbuf i sendbuf.

Dac datele aferente procesului root exist deja n bufferul de recepie, nu se mai face transferul pentru root i se d ca argument recvbuf MPI_IN_PLACE (numai n procesul root).

Dac se distribuie blocuri de date de dimensiuni diferite, se folosete funcia MPI_Scatterv() Att n MPI_Scatter ct i n MPI_Gather numrul elementelor de tipul datatype care se transmit (sendcnt) sau se recepioneaz (recvcnt) este numrul care revine unui singur proces, nu cel pe care l transmite, respectiv recepioneaz procesul root. De exemplu, pentru distribuirea sau colectarea unui vector de n elemente la p procese, sendcnt = recvcnt = s = n / p. Exemplu - Scatter_Gather_MPI.c // Scatter_Gather_MPI.c #include #include

9


#include int main (int argc, char *argv[]) { int i, p, s, rank, root = 0; MPI_Init (&argc, &argv); MPI_Comm_rank (MPI_COMM_WORLD, &rank); MPI_Comm_size (MPI_COMM_WORLD, &p); s = n / p; int *X = (int*)malloc(sizeof(int)*n); if (rank == root) for (i = 0; i < n; i++) X[i] = i; else for (i = 0; i < n; i++) X[i] = 0; // Procesul root distribuie partitiile de date celorlalte procese if (rank==root) MPI_Scatter(X,s,MPI_INT,MPI_IN_PLACE,s,MPI_INT, root,\ MPI_COMM_WORLD); else MPI_Scatter(X,s,MPI_INT,X, s, MPI_INT, root, MPI_COMM_WORLD); printf("P%d dupa MPI_Scatter: ", rank); for (i = 0; i < n; i++) printf("%d ", X[i]); printf ("\n"); // Modificare date in fiecare proces for (i = 0; i < s; i++) X[i] *= 10; MPI_Barrier(MPI_COMM_WORLD); if (rank == root) printf("MPI_Barrier\n"); // Rezultatul se colecteaza in procesul root if (rank == root) MPI_Gather(MPI_IN_PLACE, s,MPI_INT, X, s, MPI_INT, \ root, MPI_COMM_WORLD); else MPI_Gather(X, s, MPI_INT, X, s, MPI_INT, root, MPI_COMM_WORLD); printf("P%d dupa MPI_Gather: ", rank); for (i = 0; i < n; i++) printf("%d ", X[i]); printf ("\n"); MPI_Finalize(); return 0; } Datele din vectorul X se initializeaz n procesul root cu valori cresctoare, de la 0 la (n-1) iar n celelalte procese cu 0. Procesul root transmite cte o partiie de s elemente celorlalte procese, care o recepioneaz n prima partiie (primele s elemente ale vectorului) apoi le modific nmulindu-le cu 10. Dup modificare toate procesele ateapt la o barier de sincronizare, dup care procesul root colecteaz datele de la celelalte procese. Rezultatul execuiei este: $ mpirun -np 4 Scatter_Gather P0 dupa MPI_Scatter: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 P1 dupa MPI_Scatter: 4 5 6 7 0 0 0 0 0 0 0 0 0 0 0 0 P2 dupa MPI_Scatter: 8 9 10 11 0 0 0 0 0 0 0 0 0 0 0 0 P3 dupa MPI_Scatter: 12 13 14 15 0 0 0 0 0 0 0 0 0 0 0 0 MPI_Barrier P1 dupa MPI_Gather: 40 50 60 70 0 0 0 0 0 0 0 0 0 0 0 0 P2 dupa MPI_Gather: 80 90 100 110 0 0 0 0 0 0 0 0 0 0 0 0 P3 dupa MPI_Gather: 120 130 140 150 0 0 0 0 0 0 0 0 0 0 0 0 P0 dupa MPI_Gather: 0 10 20 30 40 50 60 70 80 90 100 110 120 130 140 150

10


Exerciiul E4.1.b. Compilai i executai toate programele de comunicaii MPI (Send_Receive.c, Bcast.c, Scatter_Gather.c). Urmrii i explicai funcionarea pentru diferii parametri.

4.2. Program MPI de inmultire a doua matrice

Se paralelizeaz acelai algoritm secvenial ca i n lucrrile precedente, adic cel mai simplu algoritm sevenial de nmulire a dou matrice ptrate a i b de dimensiuni n x n, cu rezultat matricea c: for (i = 0; i < n; i++) for (j = 0; j < n; j++) { c[i][j] = 0; for (k = 0; k < n; k++) c[i][j] += a[i][k]*b[k][j]; }

In fisierul Matrix_Mult_MPI.c este dat programul MPI de nmulire paralel a dou matrice prin partiionare unidimensional orientat pe linii. Aceast partiionare este echivalent cu distribuirea iteraiilor buclei exterioare a algoritmului, deoarece aceste iteraii sunt independente.

Partea de program de alocare a datelor i nmulire a submatricelor este urmtoarea: #include int main(int argc, char *argv[]) { int n = 1024; // Diensiune matrice int p = 2; // Nr procese MPI int max_rep = 1; // Numar de repetari executie int rank, root = 0; int i, j, k, s, rep; // Citire parametri n, p, max_rep din linia de comanda ... // Initializare MPI MPI_Init (&argc,&argv); MPI_Comm_rank (MPI_COMM_WORLD, &rank); MPI_Comm_size(MPI_COMM_WORLD, &p); s = n / p; // Alocarea matricelor float **a = (float**)malloc(sizeof(float*)*n); float **b = (float**)malloc(sizeof(float*)*n); float **c = (float**)malloc(sizeof(float*)*n); float *ma = (float*)malloc(sizeof(float)*n*n); float *mb = (float*)malloc(sizeof(float)*n*n); float *mc = (float*)malloc(sizeof(float)*n*n); for (i = 0; i < n; i++){ a[i] = ma; ma += n; b[i] = mb; mb += n; c[i] = mc; mc += n; } // Initializarea matricelor ... // Transmiterea matricelor a, b if (rank == root && root == 0) MPI_Scatter(a[0],s*n,MPI_FLOAT,MPI_IN_PLACE,s*n,MPI_FLOAT,root,\ MPI_COMM_WORLD); else MPI_Scatter(a[0],s*n,MPI_FLOAT,a[0],s*n,MPI_FLOAT,root, \ 11


MPI_COMM_WORLD); MPI_Bcast(b[0], n*n, MPI_FLOAT, root, MPI_COMM_WORLD); // Inmultire submatrice de s linii in fiecare proces for (i = 0; i < s; i++) for (j = 0; j < n; j++){ c[i][j] = 0; for (k = 0; k < n; k++) c[i][j] += a[i][k] * b[k][j]; } // Colectare rezultate if (rank == root && root == 0) MPI_Gather(MPI_IN_PLACE,s*n,MPI_FLOAT, c[0], s*n, MPI_FLOAT, root,\ MPI_COMM_WORLD); else MPI_Gather(c[0], s*n, MPI_FLOAT, c[0], s*n,MPI_FLOAT, root, \ MPI_COMM_WORLD); // Memorare si afisare timp de executie ... MPI_Finalize(); return 0; }

Numrul de procese MPI (p) nu este definit n program; se creaz attea procese cte sunt specificate prin comanda mpirun, dar trebuie ca n (dimensiunea liniilor i coloanelor matricelor a, b, c) s fie divizibil cu p; dac n nu este divizibil, trebuie s se adauge cod care s trateze aceast situaie. Fiecare din cele p procese prelucreaz s = n / p linii (partiionare pe linii, cu partiii continue); dac p < P (numrul de proceseare din cluster), atunci cele p procese se execut pe p procesoare diferite, performanele depinznd de p i de ncrcarea general a clusterului.

Dimensiunea matricelor (n) se introduce ca parametru de execuie (valoarea implicit este n = 1024), iar matricele a, b, c se aloca dinamic, fiecare matrice fiind un tablou bidimensional ca bloc continuu de memorie, cu dimensiunea n x n. n acest fel liniile matricelor sunt memorate la adrese consecutive n memorie i pot fi transmise mai multe linii consecutive direct din matrice (cu MPI_Scatter, MPI_Bcast, MNPI_Gather), fr s fie nevoie s fie copiate ntr-un buffer.

Aceast implementare este posibil i dac se aloc static matricele (dar atunci trebuie recompilat programul pentru fiecare nou valoare a lui n) i dac se aloc matricele ca tablouri unidimensionale (dar atunci elementul a[i][j] se acceseaz cu expresia a[i*n+j]).

n schimb, alocarea matricelor cu linii neadiacente (aa cum s-a fcut n programele Pthread i OpenMP) nu garanteaz continuitatea blocului de memorie n care sunt memorate liniile consecutive i programul nu va funciona.

Procesul root initializeaz datele de intrare, distribuie datele de intrare celorlalte procese, calculeaz propria partiie de date i colecteaz partiiile rezultatului.

Pentru distribuirea matricei a se folosete funcia MPI_Scatter care transmite fiecrui proces cte o partiie de s= n/p linii. Matricea b este transmis tuturor celorlalte procese cu funcia MPI_Bcast.

Dup distribuirea datelor folosind MPI_Scatter datele ajung n prima partiie (partiia cu indice 0) n fiecare proces i operaiile de calcul se execut folosind aceast partiie (indicele i parcurge valori de la 0 la s 1), iar rezultatul se obine tot n aceast partiie.

Colectarea rezultatului n procesul root cu funcia MPI_Gather aranjeaz corect partiiile rez., aa cum se vede n figura de mai jos pentru operaia de nmulire a dou matrice cu 4 procese MPI.

12


n acest program a fost alocat spaiu pentru toate datele (matricele a, b, c) n toate procesele.

Dar se observ c n toate procesele care nu sunt root se poate aloca numai o partiie de dimensiune s (s linii de cte n elemente din matricele a i c). Pentru aceasta, se poate face o alocare dinamic a datelor cu dimensiuni care depind de n, size (p) i root.

Compilarea se face cu comanda: $ mpicc Matrix_Mult_MPI.c -o Matrix_Mult_MPI

Lansarea n execuie ntr-un cluster Linux sau clusterul HPC se face cu comanda: $ mpirun -hostfile hosts np p Matrix_Mult_MPI

Numarul de procese lansate p este dat de argumentul optiunii np si aceste procese se distribuie uniform procesoarelor (cores, slots) din lista hosts.

nmulirea a dou matrice cu n = 2048 n HPC cu p = 1,2,4,8,16,32,64 procesoare d rezultatele: $ mpirun -hostfile hosts_hpc -np 1 Matrix_Mult_MPI 2048 1 rep, n = 2048, p = 1, t = 78.552010 sec $ mpirun -hostfile hosts_hpc -np 2 Matrix_Mult_MPI 2048 1 rep, n = 2048, p = 2, t = 47.296356 sec $ mpirun -hostfile hosts_hpc -np 4 Matrix_Mult_MPI 2048 1 rep, n = 2048, p = 4, t = 22.401253 sec $ mpirun -hostfile hosts_hpc -np 8 Matrix_Mult_MPI 2048 1 rep, n = 2048, p = 8, t = 10.859475 sec $ mpirun -hostfile hosts_hpc -np 16 Matrix_Mult_MPI 2048 1 rep, n = 2048, p = 16, t = 7.327429 sec $ mpirun -hostfile hosts_hpc -np 32 Matrix_Mult_MPI 2048 1 rep, n = 2048, p = 32, t = 3.832197 sec $ mpirun -hostfile hosts_hpc -np 64 Matrix_Mult_MPI 2048 1 rep, n = 2048, p = 64, t = 2.592258 sec Pentru msurarea i memorarea performanelor de execuie paralel a programului se lanseaz un script care conine comenzi de execuie pentru diferite valori ale lui n (dimensiunea matricelor) i, pentru fiecare dimensiune, se execut n cluster cu un numr variat de procese. Fiierul de execuie Exec_Matrix_Mult_MPI este asemntor cu celelalte fiiere de execuie. Rezultatele se obin n fiierul Res_Matrix_Mult_MPI.txt i graficele se traseaz setnd numele acestui fiier n programul Grafice.R

Matricea a n root dup iniializare Matricea a dup MPI_SCATTER

Matricea c dup nmulire partiii

Matricea b n toate procesele

Matricea c n root dup MPI_Gather

P0 P1 P2 P3

13


14

Felicia Ionescu, Valentin Pupezescu Laborator de Calcul paralel Exercitiul E4.2. Compilai i executai programul Matrix_Mult_MPI.c pe staia Linux i n clusterul HPC, verificati funcionarea corect pentru diferite valori ale matricelor. Executai scriptul Exec_Matrix_Mult_MPI pe HPC i reprezentai graficele cu programul R dat.

4.3. Program MPI de adunare a doi vectori Se implementeaz acelai algoritm de adunare a doi vectori x i y de dimensiune n, cu rezultat

n y folosit i n aplicaiile Pthread: for (i = 0; i < n; i++)

y[i] = y[i] + x[i]; Distribuirea datelor n algoritmul de adunare a doi vectori: vectorii x i y: procesul root distribuie partiii celorlalte procese (cu MPI_Scatter) vectorul y: procesul root colecteaz partiiile rezultate din celel. procese (cu MPI_Gather) Exerciiul E4.3. Dezvoltai programul MPI de adunare a doi vectori Vector_Add_MPI.c,

executai pe staia Linux i pe HPC. Generai matricea de valori ale timpului de execuie folosind un script Exec_Vector_Add_MPI asemntor celui pentru nmulirea a dou matrice pentru n = (4096, 32768, 262144, 16777216), p = (1, 2, 4, 8, 12, 16). Reprezentai graficele performanelor TP (p), S(p), E(p) cu parametru n, folosind programul R dat.

4.4. Program MPI de adunare a dou matrice Se implementeaz acelai algoritm de adunare a dou matrice ptrate a i b de dimensiuni n x n

folosit i n aplicaiile Pthread: for (i = 0; i < n; i++) for (j = 0; j < n; j++) c[i][j] = a[i][j] + b[i][j];

Programul Matrix_Add_MPI.c poate fi identic cu cel de nmulire a dou matrice, cu deosebirea c se distribuie i matricea b (nu se difiuzeaz cu MPI_Bcast) i se nlocuiete partea de calcul a elementului c[i][j] al matricei de ieire.

Exerciiul E4.4. Dezvoltai programul MPI de adunare a dou matrice Matrix_Add_MPI.c, n

mod asemntor programul de inmulire a dou matrice. Executai programul pe staia Linux i pe HPC. Generai matricea de valori ale timpului de execuie folosind un script Exec_Matrix_Add_MPI pentru aceleai valori ale lui p (1, 2, 4, 8, 16, 32, 64) i n = (64, 256, 512, 4096, 32768). Reprezentai graficele performanelor TP (p), S(p), E(p) folosind programul Grafice.R

4.5. Program MPI de reducere paralel

Funciile de reducere sunt folosite pentru a calcula un rezultat prin combinarea datelor

distribuite ntr-un grup de procese MPI: Funcia MPI_Reduce returneaz valoarea rezultat prin combinarea valorilor din sendbuf n

bufferul recvbuf n procesul root, iar MPI_Allreduce n toate procesele. Operaia se aplic la count valori din sendbuf, cu rezultat n recvbuf (count 1).

15


int MPI_Reduce (void *sendbuf, void *recvbuf, int count, MPI_Datatype datatype, MPI_Op op, int root, MPI_Comm comm) int MPI_Allreduce (void *sendbuf, void *recvbuf, int count, MPI_Datatype datatype, MPI_Op op, MPI_Comm comm)

Operatorii de reducere MPI_Op sunt urmtorii: MPI_MAX Maximum MPI_MIN Minimum MPI_SUM Sum MPI_PROD Product MPI_LAND Logical AND MPI_BAND Bitwise AND MPI_LOR Logical OR MPI_BOR Bitwise OR MPI_LXOR Logical exclusive OR MPI_BXOR Bitwise exclusive OR MPI_MAXLOC Maximum and index MPI_MINLOC Minimum and index Operatorii MPI_MAXLOC i MPI_MINLOC permit aflarea maximului (respectiv minimului)

dintre valorile distribuite i un index ataat valorii respective. De exemplu, pentru MAX_LOC:

( ) ( )max , , min ,i if u

u v wwhere w u v k i j if u v

i j k

v

j if u v

> = = = =


Exerciiul E4.6. Implementai algoritmul de nmulire succesiv a matricelor folosind biblioteca OpenMPI, n mod asemntor cu nmulirea a dou matrice. Executai programul pe staia Linux i pe HPC. Generai matricea de valori ale timpului de execuie folosind un script Exec_Many_Matrix_Mult_MPI pentru aceleai valori ale lui p (1, 2, 4, 8, 12, 16) i n = (16, 32, 64, 256, 1024, 4096). Reprezentai graficele performanelor TP (p), S(p), E(p) folosind programul Grafice.R.

4.7. Algoritmii Fox i Cannon de nmulire a dou matrice Algoritmii Fox i Cannon de nmulire a dou matrice folosesc partiionarea n blocuri a

matricelor pentru reducerea spaiului de memorare a matricelor i suprapunerea calculelor cu comunicaia. Implementai aceti algoritmi MPI folosind documentaia disponibil pe Internet (opional).

Bibliografie 1. Felicia Ionescu, Calcul paralel, 2014, slide-uri publicate pe site-ul moodle ETTI. 2. Message Passing Interface Standard, 2009 3. B. Barney, Message Passing Interface, Lawrence Livermore National Laboratory, 2013, https://computing.llnl.gov/tutorials/MPI/

17

l4 aplicatii mpi

Documents