Cuplarea circuitelor pe magistral ă sau pe un port paralel / serial
Merge sort paralel
8
MERGESORT PARALEL T.G. Structuri Multiprocesor 10. 01. 2012
-
Upload
georgiana-t -
Category
Science
-
view
112 -
download
1
Transcript of Merge sort paralel
MERGESORT PARALEL
T.G.
Structuri Multiprocesor
10. 01. 2012
Prezentarea problemei
MergeSort: algoritm de tip divide et
impera, de complexitate O(n log n) pentru
sortarea unui vector
Pasi:
2MERGESORT PARALEL
7 3 6 12
7 3 6 12
7 3
3 7
6 12
6 12
3 6 7 12
Paralelizare in MPI Numar fix de noduri, dat de la tastatura
Fiecare nod (thread) se poate ocupa de cate un subsir al setului de
baza
sau:
MERGESORT PARALEL 3
• adancimea arborelui este fixa
• comunicatia prin mesaje: de sus
in jos la transmiterea datelor &
de jos in sus la transmiterea
rezultatelor
• nodurile-frunza: aplica
quicksort pentru a-si sorta
elementele
• 4 noduri in loc de 7
• fiecare nod realizeaza o munca
aproximativ egala
NOD 0
NOD 1 NOD 2
NOD 3 NOD 4 NOD 5 NOD 6
1000 elem
500 elem500 elem
250 elem 250 elem 250 elem 250 elem
NOD 0
NOD 0 NOD 2
NOD 0 NOD 1 NOD 2 NOD 3
1000 elem
500 elem500 elem
250 elem 250 elem 250 elem 250 elem
Paralelizare in OpenMP Numar variabil de thread-uri, in functie de cat este nevoie
Fiecare thread lucreaza pe propriul subsir din sir, interclasand cele
doua jumatati (sortate) ale acestuia
Memorie partajata: nu mai este nevoie de transmiterea datelor
intre fire de executie; pe un “arbore” se porneste de jos in sus
Fara quicksort!
MERGESORT PARALEL 4
Thread 0
Thread 0 Thread 1
Thread 0 Thread 1 Thread 2 Thread 3
8 elem
4 elem4 elem
2 elem 2 elem 2 elem 2 elem
4 6
Thrd 0 Thrd 1 Thrd 2 Thrd 3
1 2 3 4 6 7 7 8 7 1 3 2 7 8 1 7 2 3
Thrd 1Thrd 0
1 4 6 7 2 3 7 8
Thrd 0
Paralelizare in pthread
Algoritm asemanator OpenMP
Numarul initial de thread-uri este 2^n
(cea mai mica putere a lui 2 >= n) si
ajunge in final la 1
Fork/join pentru lansarea si reunirea
thread-urilor
MERGESORT PARALEL 5
Rezultate
MERGESORT PARALEL 6
3.43.53.63.73.8
100
elemente
500
elemente
1000
elemente
10000
elemente
MPI
00.5
11.5
2
OpenMP
0123
pthread
Rezultate comparative
MERGESORT PARALEL 7
0
0.5
1
1.5
2
2.5
3
3.5
4
MPI OpenMP pthread
100
500
1000
10000
Concluzii
Timpul rularii in MPI cu un numar fix de 100 noduri se
mentine constant, in jur de 3 secunde
OpenMP si pthread s-au dovedit a fi mult mai rapide in
fiecare caz
OpenMP este mai rapid decat pthread: este modelul de
programare cu cele mai bune rezultate
MERGESORT PARALEL 8
