mergesort paralel

Paralelizarea algoritmuluiMerge Sort

12.01.2011

Prezentarea problemeiMerge Sort este un algoritm de sortare bazata pe comparatii, cu o

complexitate medie O(n*log n).

Algoritmul este de tipul divide et impera si a fost inventat de John von Neumann in 1945.

Conceptual, un algoritm Merge Sort cunoaste urmatorii pasi:

- daca lista este vida sau contine un singur element, se considera sortata;

- altfel: - se imparte lista nesortata in 2 subliste cu lungimi aproape egale

- se sorteaza fiecare sublista recursiv, reaplicand Merge Sort - se interclaseza cele 2 subliste intr-o lista sortata

Pseudocodul algoritmului serial

function merge_sort(m) if length(m) ≤ 1 return m var list left, right, result var integer middle = length(m) / 2 for each x in m up to middle add x to left for each x in m after middle add x to right left = merge_sort(left) right = merge_sort(right) result = merge(left, right) return result

function merge(left,right) var list result while length(left) > 0 or length(right) > 0 if length(left) > 0 and length(right) > 0 if first(left) ≤ first(right) append first(left) to result left = rest(left) else append first(right) to result right = rest(right) else if length(left) > 0 append first(left) to result left = rest(left) else if length(right) > 0 append first(right) to result right = rest(right) end while return result

Merge Sort paralel

Intrucat Merge Sort este un algoritm de tipul divide et impera, el poate fi foarte usor schitat ca un arbore in care fiecare nod detine una dintre sublistele ce trebuiesc sortate:

- radacina detine lista initiala de la care se porneste, si care furnizeaza in cele din urma rezultatul final

- frunzele detin listele ce trebuiesc sortate in mod direct (de dimensiune 0, 1 sau mai mare decat 1 daca se aplica un algoritm de sortare pe elementele ei)

- nodurile intermediare se ocupa cu impartirea in subliste, distribuirea acestora catre fii si in cele din urma colectarea rezultatelor de la acestea si combinarea lor

Merge Sort paralel (2)De exemplu, avand o lista initiala de 2000 de elemente, putem distribui

cate o lista de 1000 de elemente catre 2

procese distincte, fiecare repetand acelasi procedeu pana cand se ajunge la o anumita adancime.

Daca dorim sa ne oprim la adancimea din imagine, procesele-frunza vor folosi cel mai rapid algoritm disponibil pentru a sorta listele si vor furniza rezultatele catre parinti.

Implementare in MPI

Definim 3 etichete (flags) pentru tipurile de mesaje intre procese:

#define INIT 1 // mesaj care ofera marimea si inaltimea arborelui dorit

#define DATA 2 // mesaj care ofera vectorul de sortat

#define ANSW 3 // mesaj care returneaza vectorul sortat

Pentru stabilirea rangurilor proceselor implicate pe fiecare ramura a arborelui, putem imprumuta modelul heap-urilor astfel: daca nodul curent are rangul i, atunci parintele sau are rangul (i-1)/2, iar fiii stang si drept vor avea rangurile 2*i+1 respectiv 2*i+2.

Implementare in MPI (2)

Totusi, la o privire mai atenta putem observa faptul ca putem folosi eficient numarul de noduri/procesoare disponibile, astfel:

In imagine s-au folosit doar 8 noduri in loc de 15 si, in plus, fiecare nod are de efectuat o munca aproximativ egala, eliminand overhead-ul ce s-ar fi putut crea in modelul anterior.

Implementare in MPI (3)

Nodul 0 din nivelul 3 trebuie sa comunice cu nodul 4 – ceea ce se poate realiza prin trecerea in 1 a bitului 2 (presupunand ca numaram bitii cu bitul 0 fiind cel mai putin semnificativ) . Acest lucru poate fi satisfacut printr-o shiftare de tipul: rang|(1<<2) .

In nivelul 2, nodul 0 trebuie sa comunice cu nodul 2, in timp ce nodul 4 trebuie sa comunice cu nodul 6. Tot ce trebuie facut este sa se treaca in 1 bitul 1 (al doilea LSB), sau altfel spus rang|(1<<1) .

In final, la nivelul unu, nodurile pare trebuie sa comunice cu cele impare, trecand in 1 bitul 0 (LSB), sau rang|(1<<0).

Generalizand: rang|(1<<(inaltime-1)).

Implementare in MPI (4)In mod asemanator, se poate trece pe 0 bitul corespunzator astfel

incat sa se obtina rangul nodului parinte.

Nivelul 0 trebuie sa stearga bitul 0; nivelul 1 – bitul 1; nivelul 2 – bitul 2, etc. Astfel, inaltimea arborelui determina care este bitul ce trebuie sters; astfel, complementand masca inversa si folosind un SI pe biti se obtine formula: rang&~(1<<inaltime).

Daca nodul parinte este acelasi cu cel curent, nu este nevoie de comunicatie intre ele, ci doar de intoarcerea din apelul recursiv. Partea stanga a sirului este deja la locul ei si sortata.

Urmatoarele slide-uri arata modul in care poate fi testata schema de comunicatie cat si output-ul corespunzator.

#include <stdio.h>

void comunicatie ( int inaltime, int rang )

{ int parinte = rang & ~(1<<inaltimet);

if ( inaltime > 0 )

{ int next = inaltime - 1;

int fiu = rang | ( 1 << next );

printf ("%d trimite date catre %d\n", rang, fiu);

comunicatie ( next, rang );

comunicatie ( next, fiu );

printf ("%d primeste date de la %d\n", rang, fiu);

}

if ( parinte != rang )

printf ("%d transmite catre %d\n", rang, parinte);

}

int main ( void )

{ int inaltime = 3, rang = 0;

printf ("Se construieste un arbore de inaltime %d \n", inaltime);

comunicatie(inaltime, rang);

return 0;

}

Output

Se construieste un arbore de inaltime 3

0 trimite date catre 4



1 transmite catre 0

0 primeste date de la 1


3 transmite catre 2


2 transmite catre 0




5 transmite catre to 4







4 transmite catre 0


Implementarea secventiala a algoritmului de sortare a arborelui

Aceasta este o simulare a testarii in paralel, folosind in loc de comunicatia reala intre noduri, un apel al unei functii recursive. Astfel, implementarea devine un prototip al programului de sortare.

Pe langa informatiile referitoare la inaltime si rang, modulul trebuie sa primeasca sirul de sortat si, cum limbajul folosit este C, este nevoie si de numarul elementelor din el.

Daca inaltimea nodului este mai mare decat 0, se va calcula pozitia jumatatii drepte a sirului pentru a genera doua alte siruri care primesc limitele stanga si dreapta ale lor.

Totusi, in loc sa se trimita subsirul din dreapta catre procesul fiu si sa se primeasca rezultatul, se va face doar un apel recursiv pentru acea jumatate, la fel ca si pentru cealalta jumatate din stanga.

La intoarcerea din aceste doua apeluri se realizeaza interclasarea datelor. In cazul in care inaltimea nodului este 0 (nod frunza), se aplica direct sortarea asupra elementelor (functia qsort este o varianta rapida pentru aceasta).

In slide-ul urmator este prezentata implementarea in C.

void sortarePartitionala ( long *vector, int lungime, int inaltime, int mySelf )

{ int parinte, fiu, next;

parinte = mySelf & ~(1 << inaltime);

next = inaltime – 1; fiu = mySelf | ( 1 << next );

if ( inaltime > 0 )

{

int lungime_stg = lungime / 2, lungime_drp = lungime - lungime_stg;

long *vector_stg = (long*) calloc (lungime_stg, sizeof *vector_stg),

*vector_drp = (long*) calloc (lungime_drp, sizeof *vector_drp);

int i, j, k;

memcpy (vector_stg, vector, left_size*sizeof *vector_stg);

memcpy (vector_drp, vector+lungime_stg, lungime_drp*sizeof *vector_drp);

sortarePartitionala ( vector_stg, lungime_stg, next, mySelf );

sortarePartitionala ( vector_drp, lungime_drp, next, fiu );

// operatia de „merge”

i = j = k = 0;

while ( i < lungime_stg && j < lungime_drp )

if ( vector_stg[i] > vector_drp[j])

vector[k++] = vector_drp[j++];

else

vector[k++] = vector_stg[i++];

while ( i < lungime_stg )


while ( j < lungime_drp )


free(vector_stg); free(vector_drp);

}

else

qsort( vector, lungime, sizeof *vector, compare );

}

Implementarea paralelaFata de cazul anterior, apelurile recursive ale jumatatii din dreapta vor fi inlocuite cu

trimiterea de mesaje catre „fiul” raspunzator de ele.

Se vor trimite 2 mesaje:

- primul trimite informatiile referitoare la inaltimea fiului cel drept din arbore si lungimea sirului de primit.

- al doilea trimite segmentul de sir propriu-zis.

Sortarea partii stangi din sir se face in mod recursiv. La intoarcerea din apelul recursiv, se vor accepta mesaje venite din partea fiului drept care trimite segmentul sau de sir gata sortat.

In cele din urma, fie ca este vorba de un nod frunza sau un nod intern, trebuie trimis un mesaj cu rezultatul sortat catre parinte. Acest fapt are loc cand rangul parintelui este diferit de rangul nodului propriu-zis.

Codul C aferent se poate gasi in slide-urile urmatoare.

// parte din MAIN

if ( rang == 0 )

{ //inaltimea radacinii, contor nr. de noduri

int h_root = 0, contor = 1;

while ( contor < nProc )

{ contor += contor; h_root++; }

printf ("%d procese cer inaltimea radacinei care este %d\n", nProc, h_root);

getData (&vector, &lungime); //vectorul pt sortat

solo = (long*) calloc ( size, sizeof *solo );

memcpy (solo, vector, size * sizeof *solo);

start = MPI_Wtime();

parallelMerge ( vector, lungime, h_root);

middle = MPI_Wtime();

}

else {

int iVect[2], // mesajele lipite intr-un sir

inaltime, // se extrage din iVect

parinte; // calculata prin rang si inaltime

MPI_Status status;

rc = MPI_Recv( iVect, 2, MPI_INT, MPI_ANY_SOURCE, INIT,

MPI_COMM_WORLD, &status );

lungime = iVect[0]; inaltime = iVect[1];

vector = (long*) calloc (size, sizeof *vector);

rc = MPI_Recv( vector, lungime, MPI_LONG, MPI_ANY_SOURCE, DATA,

MPI_COMM_WORLD, &status );

parallelMerge ( vector, size, height );

MPI_Finalize(); return 0;

}

// doar procesul cu rang =0 calculeaza

qsort( solo, lungime, sizeof *solo, compare );

finish = MPI_Wtime();

void parallelMerge ( long *vector, int lungime, int inaltime )

{ int parinte;

int rang, nProc, rc, next, fiu;

rc = MPI_Comm_rank (MPI_COMM_WORLD, &rang);

rc = MPI_Comm_size (MPI_COMM_WORLD, &nProc);

parinte = rang & ~(1 << inaltime);

next = inaltime - 1;

fiu = rang | ( 1 << next );

if ( inaltime > 0 ) {

if ( fiu >= nProc ) // nu exista fiu drept, nivelul scade cu 1

parallelMerge ( vector, lungime, next );

else {

int lungime_stg = lungime / 2,

lungime_drp = size - lungime_stg;

long *vector_stg = (long*) calloc (lungime_stg,

sizeof *vector_stg),

*vector_drp = (long*) calloc (lungime_drp,

sizeof *vector_drp);

int iVect[2];

int i, j, k;

MPI_Status status;

memcpy (vector_stg, vector, lungime_stg*sizeof *vector_stg);

memcpy(vector_drp, vector+lungime_stg, lungime_drp*sizeof *vector_drp);

iVect[0] = lungime_drp; iVect[1] = next;

rc = MPI_Send( iVect, 2, MPI_INT, fiu, INIT, MPI_COMM_WORLD);

rc = MPI_Send( vector_drp, lungime_drp, MPI_LONG, fiu, DATA, MPI_COMM_WORLD);

parallelMerge ( vector_stg, lungime_stg, next );

rc = MPI_Recv( vector_drp, lungime_drp, MPI_LONG, fiu, ANSW, MPI_COMM_WORLD, &status );

i = j = k = 0; // merge

while ( i < lungime_stg && j < lungime_drp )

if ( vector_stg[i] > vector_drp[j])


else


while ( i < lungime_stg )


while ( j < lungime_drp )


} }

else

qsort( vector, lungime, sizeof *vector, compare );

if ( parinte != rang)

rc = MPI_Send( vector, lungime, MPI_LONG, parinte, ANSW, MPI_COMM_WORLD ); }

Testarea aplicatieiSpeed-up = Timpul_exe_secvential / Timpul_exe_paralel

Testare pe un singur calculator, folosind 4 procese:

Paralel: 3.877

Secvential: 11.607

Speed-up: 2.994

Testare pe un singur calculator, folosind 8 procese:

Paralel: 3.643

Secvential: 11.573

Speed-up: 3.177

Intrebari?

mergesort paralel

Documents