際際滷

際際滷Share a Scribd company logo

Analiza Algoritmilor de Sortare pe Arhitecturi Paralele

Radu Potop
Radu Potop

Sursele: https://bitbucket.org/wooptoo/asapa/ Lucrarea completa: http://wooptoo.com/papers/Analiza_Algoritmilor_de_Sortare_pe_Arhitecturi_Paralele.pdf

1 of 21
Downloaded 11 times
Analiza Algoritmilor de Sortare pe Arhitecturi Paralele Radu Potop
Scopul Prezentarea i analiza a unei serii de algoritmi de sortare Paralelizarea algoritmilor Obinerea de rezultate experimentale ale algoritmilor paraleli Construirea de algoritmi paraleli hibrizi Obinerea de rezultate experimentale ale algoritmilor hibrizi
Motivaia Fascinaia personal pentru algoritmi de sortare Dorina de a construi i rula astfel de algoritmi pe arhitecturi paralele Dorina de a construi algoritmi de sortare hibrizi i de a descoperi dac acetia ofer sporuri de performan Metoda de cercetare - predominant experimental
Categorii de algoritmi de sortare Dupa metoda general de lucru: Inserie (insertion sort, shellsort, cyclesort) Selecie (selection sort, heapsort) Partiionare (quicksort, introsort) Interclasare (mergesort, timsort) Am ales c但iva: Quicksort, Mergesort - divide et impera Selection sort, Heapsort
Quicksort, Mergesort Algoritmi recursivi mpart lista de intrare 樽n sub-liste T(n) T(n/2) T(n/2) Ruleaz recursiv pe aceste sub-liste T(n/4) T(n/4) T(n/4) T(n/4) n=1 cazul de baz T ( n/2 k ) Apelurile => arbore de recuren T(1) T(1) T(1) T(1) T(1) T(1) T(1) T(1) Quicksort i Mergesort: (nlog (n )) Quicksort: cazul nefavorabil: (n 2) - arborele de recuren devine liniar
Paralelizarea algoritmilor Algoritmii "divide et impera" - pot fi paralelizai cel mai uor Firele de execuie nu trebuie s se sincronizeze n n Nu facem paralelizarea 樽n funcie de nr. de procesoare ( p log( )) p Paralelizare 樽n funcie de nivelul de recuren La fiecare nivel de recuren putem lansa procese separate Arborele de procese se va suprapune arborelui de recuren al algoritmului
Paralelizarea algoritmilor N0 N1 N2 N3 N0 nivelul rdcin, apelul iniial al funciei N1 rezultatul a 21 apeluri ale funciei, fiecare pe c但te o sub-list N2 rezultatul a 2 2 apeluri, fiecare pe c但te o sub-list a nivelului anterior La fiecare nivel putem lansa 2i procese
Paralelizarea algoritmilor Ne vom limita la N0 - N3, respectiv 1, 2, 4 i 8 procese Dup ce acest nivel e depit, algoritmul la rula 樽n mod secvenial mai departe ntre procese separate - comunicare (IPC) printr-un obiect de tip coad Obiectul coad e accesibil de ctre procesul printe i cei doi copii ai si (local) ntre apeluri de funcie obinuite - return
Rezultate experimentale - cum am testat List aleatoare, list sortat cresctor, list sortat descresctor Fiecare algoritm a fost rulat de 10 ori pe fiecare list de intrare Fiecare algoritm a fost rulat pe liste de 10.000 (10k), 100.000 (100k), 1.000.000 (1M) i 5.000.000 (5M) de elemente, nr nat. Rulai: 樽n mod secvenial, pe 1 core 樽n mod paralel 2 cores i 6 cores Comparai pentru corectitudine cu implementarea standard Python (Timsort)
Rezultate experimentale secvenial secvenial: Quicksort, Mergesort i Heapsort, 100k elemente lista aleatoare lista sortata crescator lista sortata descrescator 1400 1200 1000 800 ms 600 400 200 0 quicksort_first quicksort_middle quicksort_avg3 quicksort_minmax mergesort heapsort Quicksort_first - depaete limita de recursivitate
Rezultate experimentale paralel Am selectat Quicksort_middle i Mergesort 2, 4 sau 8 procese pt. fiecare algoritm, 10k elemente, 2 cores lista aleatoare lista sortata crescator lista sortata descrescator 1200 1000 800 600 ms 400 200 0 quicksort_middle, 2p mergesort, 2p quicksort_middle, 4p mergesort, 4p quicksort_middle, 8p mergesort, 8p
Rezultate experimentale paralel 10k elemente, 6 cores lista aleatoare lista sortata crescator lista sortata descrescator 100 90 80 70 60 50 ms 40 30 20 10 0 quicksort_middle, 2p mergesort, 2p quicksort_middle, 4p mergesort, 4p quicksort_middle, 8p mergesort, 8p Diferenele sunt mult mai mici pe 6 cores Pe msur ce lista de intrare devine mai mare diferenele dispar
Rezultate experimentale secvenial vs. paralel Eliminm listele sortate cresctor i descrector. Random, 5M: secvential 2 cores 6 cores 70000 60000 50000 40000 30000 20000 10000 0 mergesort mergesort, 2p mergesort, 4p mergesort, 8p ms quicksort_middle quicksort_middle, 2p quicksort_middle, 4p quicksort_middle, 8p Mergesort paralel vs. secvenial: 56404ms vs. 31698ms Quicksort paralel - performane slabe
Construirea algoritmilor hibrizi Compui din doi algoritmi: unul de tip divide et impera unul secvenial Odat ce algoritmul principal trece de un anumit nivel va avea performane slabe - overhead De la un anumit nivel vom trece la un algoritm secvenial Cel secvenial va avea performane mai bune pe liste mici
Construirea algoritmilor hibrizi lista aleatoare 9 8 7 6 5 ms 4 3 2 1 0 quicksort_middle mergesort heapsort selection Selection sort va avea performane mai bune pe liste de 1000 el. Dup 4000 elemente, performanele sale se degradeaz
Construirea algoritmilor hibrizi Am ales nivelul de recuren 12, 212 =4096 Niveluri de recuren pt Lungimea listei sortate de fiecare lungime sub-algoritm 13 10k2 10k /40962 17 100k2 100k /409624 1M2 20 1M / 4096244 5M2 22 5M /40961220
Construirea algoritmilor hibrizi Descrierea complet a algoritmului: p但n la nivelul 1, 2 sau 3 vom lansa procese separate (2, 4 respectiv 8) p但n la nivelul 12 vom rula algoritmul secvenial de la nivelul 12 vom rula sub-algoritmul pe liste mici dac lista de intrare e mai mic de 4096, sub-algoritmul nu va intra 樽n funciune => algoritm adaptiv
Rezultate experimentale - algoritmi hibrizi Quicksort cu Heap i Selection Mergesort cu Heap i Selection secvential 2 cores 6 cores 16000 14000 12000 10000 8000 6000 4000 2000 0 ms mergesort mergesort P quick_heap H merge_heap H quicksort quicksort P quick_selection H merge_selection H 1M elemente, 2p
Concluzii ale experimentelor Quicksort - rezultate slabe Mergesort - i mai rapid dup hibridizare Mergesort cu selection sort - cel mai rapid: de 1.90 ori mai rapid dec但t mergesort secvenial 樽n medie, (2.14 max) de 1.10 ori mai rapid dec但t mergesort paralel simplu 樽n medie, (1.22 max) Varianta cu 4 procese - performane constante at但t pe 2 cores c但t i pe 6 cores, varianta cu 2 procese dispus la fluctuaii
Concluzii i posibiliti de 樽mbuntire Am construit un algoritm paralel hibrid adaptiv Odat ce avem acest algoritm putem s-l implementm pe arhitecturi cum este CUDA: programe generale rulate pe GPU procesoare puternic paralele un nr. mare de cores (480) mai rapid dec但t CPU pt asemenea task-uri
珂顎鉛顎馨艶壊界

More Related Content

Analiza Algoritmilor de Sortare pe Arhitecturi Paralele

  • 1. Analiza Algoritmilor de Sortare pe Arhitecturi Paralele Radu Potop
  • 2. Scopul Prezentarea i analiza a unei serii de algoritmi de sortare Paralelizarea algoritmilor Obinerea de rezultate experimentale ale algoritmilor paraleli Construirea de algoritmi paraleli hibrizi Obinerea de rezultate experimentale ale algoritmilor hibrizi
  • 3. Motivaia Fascinaia personal pentru algoritmi de sortare Dorina de a construi i rula astfel de algoritmi pe arhitecturi paralele Dorina de a construi algoritmi de sortare hibrizi i de a descoperi dac acetia ofer sporuri de performan Metoda de cercetare - predominant experimental
  • 4. Categorii de algoritmi de sortare Dupa metoda general de lucru: Inserie (insertion sort, shellsort, cyclesort) Selecie (selection sort, heapsort) Partiionare (quicksort, introsort) Interclasare (mergesort, timsort) Am ales c但iva: Quicksort, Mergesort - divide et impera Selection sort, Heapsort
  • 5. Quicksort, Mergesort Algoritmi recursivi mpart lista de intrare 樽n sub-liste T(n) T(n/2) T(n/2) Ruleaz recursiv pe aceste sub-liste T(n/4) T(n/4) T(n/4) T(n/4) n=1 cazul de baz T ( n/2 k ) Apelurile => arbore de recuren T(1) T(1) T(1) T(1) T(1) T(1) T(1) T(1) Quicksort i Mergesort: (nlog (n )) Quicksort: cazul nefavorabil: (n 2) - arborele de recuren devine liniar
  • 6. Paralelizarea algoritmilor Algoritmii "divide et impera" - pot fi paralelizai cel mai uor Firele de execuie nu trebuie s se sincronizeze n n Nu facem paralelizarea 樽n funcie de nr. de procesoare ( p log( )) p Paralelizare 樽n funcie de nivelul de recuren La fiecare nivel de recuren putem lansa procese separate Arborele de procese se va suprapune arborelui de recuren al algoritmului
  • 7. Paralelizarea algoritmilor N0 N1 N2 N3 N0 nivelul rdcin, apelul iniial al funciei N1 rezultatul a 21 apeluri ale funciei, fiecare pe c但te o sub-list N2 rezultatul a 2 2 apeluri, fiecare pe c但te o sub-list a nivelului anterior La fiecare nivel putem lansa 2i procese
  • 8. Paralelizarea algoritmilor Ne vom limita la N0 - N3, respectiv 1, 2, 4 i 8 procese Dup ce acest nivel e depit, algoritmul la rula 樽n mod secvenial mai departe ntre procese separate - comunicare (IPC) printr-un obiect de tip coad Obiectul coad e accesibil de ctre procesul printe i cei doi copii ai si (local) ntre apeluri de funcie obinuite - return
  • 9. Rezultate experimentale - cum am testat List aleatoare, list sortat cresctor, list sortat descresctor Fiecare algoritm a fost rulat de 10 ori pe fiecare list de intrare Fiecare algoritm a fost rulat pe liste de 10.000 (10k), 100.000 (100k), 1.000.000 (1M) i 5.000.000 (5M) de elemente, nr nat. Rulai: 樽n mod secvenial, pe 1 core 樽n mod paralel 2 cores i 6 cores Comparai pentru corectitudine cu implementarea standard Python (Timsort)
  • 10. Rezultate experimentale secvenial secvenial: Quicksort, Mergesort i Heapsort, 100k elemente lista aleatoare lista sortata crescator lista sortata descrescator 1400 1200 1000 800 ms 600 400 200 0 quicksort_first quicksort_middle quicksort_avg3 quicksort_minmax mergesort heapsort Quicksort_first - depaete limita de recursivitate
  • 11. Rezultate experimentale paralel Am selectat Quicksort_middle i Mergesort 2, 4 sau 8 procese pt. fiecare algoritm, 10k elemente, 2 cores lista aleatoare lista sortata crescator lista sortata descrescator 1200 1000 800 600 ms 400 200 0 quicksort_middle, 2p mergesort, 2p quicksort_middle, 4p mergesort, 4p quicksort_middle, 8p mergesort, 8p
  • 12. Rezultate experimentale paralel 10k elemente, 6 cores lista aleatoare lista sortata crescator lista sortata descrescator 100 90 80 70 60 50 ms 40 30 20 10 0 quicksort_middle, 2p mergesort, 2p quicksort_middle, 4p mergesort, 4p quicksort_middle, 8p mergesort, 8p Diferenele sunt mult mai mici pe 6 cores Pe msur ce lista de intrare devine mai mare diferenele dispar
  • 13. Rezultate experimentale secvenial vs. paralel Eliminm listele sortate cresctor i descrector. Random, 5M: secvential 2 cores 6 cores 70000 60000 50000 40000 30000 20000 10000 0 mergesort mergesort, 2p mergesort, 4p mergesort, 8p ms quicksort_middle quicksort_middle, 2p quicksort_middle, 4p quicksort_middle, 8p Mergesort paralel vs. secvenial: 56404ms vs. 31698ms Quicksort paralel - performane slabe
  • 14. Construirea algoritmilor hibrizi Compui din doi algoritmi: unul de tip divide et impera unul secvenial Odat ce algoritmul principal trece de un anumit nivel va avea performane slabe - overhead De la un anumit nivel vom trece la un algoritm secvenial Cel secvenial va avea performane mai bune pe liste mici
  • 15. Construirea algoritmilor hibrizi lista aleatoare 9 8 7 6 5 ms 4 3 2 1 0 quicksort_middle mergesort heapsort selection Selection sort va avea performane mai bune pe liste de 1000 el. Dup 4000 elemente, performanele sale se degradeaz
  • 16. Construirea algoritmilor hibrizi Am ales nivelul de recuren 12, 212 =4096 Niveluri de recuren pt Lungimea listei sortate de fiecare lungime sub-algoritm 13 10k2 10k /40962 17 100k2 100k /409624 1M2 20 1M / 4096244 5M2 22 5M /40961220
  • 17. Construirea algoritmilor hibrizi Descrierea complet a algoritmului: p但n la nivelul 1, 2 sau 3 vom lansa procese separate (2, 4 respectiv 8) p但n la nivelul 12 vom rula algoritmul secvenial de la nivelul 12 vom rula sub-algoritmul pe liste mici dac lista de intrare e mai mic de 4096, sub-algoritmul nu va intra 樽n funciune => algoritm adaptiv
  • 18. Rezultate experimentale - algoritmi hibrizi Quicksort cu Heap i Selection Mergesort cu Heap i Selection secvential 2 cores 6 cores 16000 14000 12000 10000 8000 6000 4000 2000 0 ms mergesort mergesort P quick_heap H merge_heap H quicksort quicksort P quick_selection H merge_selection H 1M elemente, 2p
  • 19. Concluzii ale experimentelor Quicksort - rezultate slabe Mergesort - i mai rapid dup hibridizare Mergesort cu selection sort - cel mai rapid: de 1.90 ori mai rapid dec但t mergesort secvenial 樽n medie, (2.14 max) de 1.10 ori mai rapid dec但t mergesort paralel simplu 樽n medie, (1.22 max) Varianta cu 4 procese - performane constante at但t pe 2 cores c但t i pe 6 cores, varianta cu 2 procese dispus la fluctuaii
  • 20. Concluzii i posibiliti de 樽mbuntire Am construit un algoritm paralel hibrid adaptiv Odat ce avem acest algoritm putem s-l implementm pe arhitecturi cum este CUDA: programe generale rulate pe GPU procesoare puternic paralele un nr. mare de cores (480) mai rapid dec但t CPU pt asemenea task-uri