JanP´ıro Efektivn´ıparalelizacealgoritmuTimsort Bakaláˇrskápráce

(1)

doc. Ing. Jan Janoušek, Ph.D.

vedoucí katedry doc. RNDr. Ing. Marcel Jiřina, Ph.D.

děkan

ZADÁNÍ BAKALÁŘSKÉ PRÁCE

Název: Efektivní paralelní Timsort algoritmus

Student: Jan Píro

Vedoucí: doc. Ing. Ivan Šimeček, Ph.D.

Studijní program: Informatika

Studijní obor: Teoretická informatika Katedra: Katedra teoretické informatiky Platnost zadání: Do konce letního semestru 2018/19

Pokyny pro vypracování

1) Nastudujte sekvenční verzi algoritmu Timsort. [1,2,3]

2) Diskutujte možnosti optimalizace a paralelizace tohoto algoritmu [4].

3) Implementujte vybrané optimalizace sekvenční i paralelní verze algoritmu.

4) Porovnejte výkonnost jednotlivých verzí optimalizace a paralelizace (navzájem a i s neoptimalizovanou sekvenční verzí) na školním serveru STAR a diskutujte dosažené výsledky.

Seznam odborné literatury

[1] http://www.drmaciver.com/2010/01/understanding-timsort-1adaptive-mergesort/

[2] https://hal-upec-upem.archives-ouvertes.fr/hal-01212839v2/document [3] https://mail.python.org/pipermail/python-dev/2002-July/026837.html [4] http://rabie-ben-atitallah.com/paper/hpcs-2017.pdf

(2)

(3)

Bakal´ aˇrsk´ a pr´ ace

Efektivn´ı paralelizace algoritmu Timsort

Jan P´ ıro

Katedra Teoretick´e Informatiky

Vedouc´ı pr´ace: doc. Ing. Ivan ˇSimeˇcek, Ph.D.

15. kvˇetna 2018

(4)

(5)

Podˇ ekov´ an´ı

Rád bych zde podˇekoval vedouc´ımu bakaláˇrské práce doc. Ing. Ivanu ˇSimeˇckovi, Ph.D. za jeho rady, ˇcas a trpˇelivost, kterou mi vˇenoval.

(6)

(7)

Prohl´ aˇ sen´ı

Prohlaˇsuji, ˇze jsem pˇredloˇzenou práci vypracoval(a) samostatnˇe a ˇze jsem uvedl(a) veˇskeré pouˇzité informaˇcn´ı zdroje v souladu s Metodickým pokynem o etické pˇr´ıpravˇe vysokoˇskolských závˇereˇcných prac´ı.

Beru na vˇedom´ı, ˇze se na moji práci vztahuj´ı práva a povinnosti vyplývaj´ıc´ı ze zákona ˇc. 121/2000 Sb., autorského zákona, ve znˇen´ı pozdˇejˇs´ıch pˇredpis˚u.

V souladu s ust.§46 odst. 6 tohoto zákona t´ımto udˇeluji nevýhradn´ı oprávnˇen´ı (licenci) k uˇzit´ı této moj´ı práce, a to vˇcetnˇe vˇsech poˇc´ıtaˇcových program˚u, jeˇz jsou jej´ı souˇcást´ı ˇci pˇr´ılohou, a veˇskeré jejich dokumentace (dále souhrnnˇe jen

”D´ılo“), a to vˇsem osobám, které si pˇrej´ı D´ılo uˇz´ıt. Tyto osoby jsou oprávnˇeny D´ılo uˇz´ıt jakýmkoli zp˚usobem, který nesniˇzuje hodnotu D´ıla, a za jakýmkoli

´

uˇcelem (vˇcetnˇe uˇzit´ı k výdˇeleˇcným úˇcel˚um). Toto oprávnˇen´ı je ˇcasovˇe, teri- toriálnˇe i mnoˇzstevnˇe neomezené. Kaˇzdá osoba, která vyuˇzije výˇse uvedenou licenci, se vˇsak zavazuje udˇelit ke kaˇzdému d´ılu, které vznikne (byt’ jen zˇcásti) na základˇe D´ıla, úpravou D´ıla, spojen´ım D´ıla s jiným d´ılem, zaˇrazen´ım D´ıla do d´ıla souborného ˇci zpracován´ım D´ıla (vˇcetnˇe pˇrekladu), licenci alespoˇn ve výˇse uvedeném rozsahu a zároveˇn zpˇr´ıstupnit zdrojový kód takového d´ıla ale- spoˇn srovnatelným zp˚usobem a ve srovnatelném rozsahu, jako je zpˇr´ıstupnˇen zdrojový kód D´ıla.

V Praze dne 15. kvˇetna 2018 . . . .

(8)

Cesk´ˇ e vysok´e uˇcen´ı technick´e v Praze Fakulta informaˇcn´ıch technologi´ı

c 2018 Jan P´ıro. Vˇsechna pr´ava vyhrazena.

Tato práce vznikla jako ˇskoln´ı d´ılo na ˇCeském vysokém uˇcen´ı technickém v Praze, Fakultˇe informaˇcn´ıch technologi´ı. Práce je chránˇena právn´ımi pˇredpisy a mezinárodn´ımi úmluvami o právu autorském a právech souvisej´ıc´ıch s právem autorským. K jej´ımu uˇzit´ı, s výjimkou bezúplatných zákonných licenc´ı a nad rámec oprávnˇen´ı uvedených v Prohláˇsen´ı na pˇredchoz´ı stranˇe, je nezbytný sou- hlas autora.

Odkaz na tuto pr´aci

P´ıro, Jan.Efektivn´ı paralelizace algoritmu Timsort. Bakaláˇrská práce. Praha:

Cesk´ˇ e vysok´e uˇcen´ı technick´e v Praze, Fakulta informaˇcn´ıch technologi´ı, 2018.

(9)

Abstrakt

Tato bakaláˇrská práce se zamˇeˇruje na tˇr´ıd´ıc´ı algoritmus Timsort. C´ılem bylo paralelizovat algoritmus tak, aby byl efektivnˇejˇs´ı neˇz jeho sekvenˇcn´ı verze a porovnat jeho rychlost s jinými algoritmy.

Kl´ıˇcov´a slova timsort, paraleln´ı timsort, tˇr´ıd´ıc´ı algoritmy, openMP, C++

Thread support library

Abstract

This thesis focuses on sorting algorithm Timsort. The goal is to paralelize the algorithm in a way to make it more efficient than its sequential version and compare its speed with other algorithms.

Keywords timsort, parallel timsort, sorting algorithms, openMP, C++ Thread support library

(10)

(11)

Obsah

Uvod´ 1

1 C´ıl pr´ace a z´akladn´ı pojmy 3

1.1 C´ıl a motivace . . . 3

1.2 Z´akladn´ı pojmy . . . 3

1.3 Pouˇzit´e technologie . . . 4

2 Algoritmus Timsort 5 2.1 Hled´an´ı run˚u . . . 5

2.2 Strategie sluˇcov´an´ı . . . 6

2.3 Algoritmy sluˇcov´an´ı . . . 7

2.4 Galloping . . . 8

3 Anal´yza a n´avrh 11 3.1 Moˇznosti optimalizace sekvenˇcn´ı verze . . . 11

3.2 Moˇznosti paralelizace . . . 11

4 Realizace 13 4.1 Kompilace . . . 13

4.2 Sekvenˇcn´ı verze . . . 13

4.3 Paraleln´ı verze 1 . . . 15

4.4 Paraleln´ı verze 2 . . . 16

4.5 Druhá fáze testován´ı . . . 17

5 Metody mˇeˇren´ı 19 5.1 server STAR . . . 19

5.2 Typy dat . . . 19

5.3 Metodika . . . 20

6 V´ysledky mˇeˇren´ı 21

(12)

6.1 Prvn´ı fáze . . . 21 6.2 Druhá fáze . . . 25

Z´avˇer 29

Literatura 31

A Obsah pˇriloˇzen´eho CD 33

x

(13)

Seznam obr´ azk˚ u

6.1 N´ahodn´a data . . . 21

6.2 M´alo ruzn´ych hodnot . . . 22

6.3 Seˇrazen´a data s v´yjimkami . . . 23

6.4 Vˇsechna data stejn´a . . . 23

6.5 Seˇrazen´a data . . . 24

6.6 C´ˇasteˇcnˇe seˇrazen´a data . . . 24

6.7 Náhodná data - Fáze 2 . . . 25

6.8 Málo r˚uzných hodnot - Fáze 2 . . . 26

6.9 Seˇrazená data s výjimkami - Fáze 2 . . . 27

6.10 Vˇschna data stejn´a - F´aze 2 . . . 27

6.11 Seˇrazen´a data - F´aze 2 . . . 28

6.12 ˇCásteˇcnˇe seˇrazená data - Fáze 2 . . . 28

(14)

(15)

Uvod ´

S problémem seˇradit za sebe nˇejaké prvky podle urˇcitých kritéri´ı se setkáváme v témˇeˇr kaˇzdém pracovn´ım odvˇetv´ı. Algoritmy zabývaj´ıc´ı se tˇemito problémy se nazývaj´ı tˇr´ıd´ıc´ı algoritmy a jsou jedny z nejpouˇz´ıvanˇejˇs´ıch algoritm˚u v˚ubec.

Pouˇz´ıvaj´ı se vˇsude od databáz´ı, pˇres umˇelou inteligenci aˇz po vojenské technologie. Toto odvˇetv´ı je tedy stále zkoumáno s c´ılem zrychlit a zefektivnit stávaj´ıc´ı algoritmy, pˇr´ıpadnˇe vymyslet nové.

Jejich sloˇzitost posuzujeme pˇredevˇs´ım dle poˇctu operac´ı srovnán´ı dvou prvk˚u (a tedy zjiˇstˇen´ım, který z prvk˚u má být ve výsledné ˇradˇe dˇr´ıve). Dále se posuzuj´ı podle operaˇcn´ı pamˇeti, kterou potˇrebuj´ı alokovat (tedy pamˇet’

alokovaná nad rámec zadané ˇrady prvk˚u).

Jedn´ım z takových algoritm˚u je Timsort, který byl navrˇzen roku 2002 Timem Petersem. Je pouˇz´ıván jako standardn´ı tˇr´ıd´ıc´ı algoritmus v Pythonu od verze 2.3 a v Javˇe SE 7. Jedná se o optimalizovanou kombinaci jiˇz známých algoritm˚u MergeSort a InsertionSort.

V teoretické ˇcásti je pospsán samotný algoritmus a jsou zde diskutovány moˇznosti jeho optimalizace a paralelizace. V praktické ˇcásti jsou vytvoˇreny verze s r˚uznými stupni optimalizace a paralelizace, mˇeˇreny jejich výkony a jednotlivé verze porovnány.

(16)

(17)

Kapitola 1

C´ıl pr´ ace a z´ akladn´ı pojmy

1.1 C´ıl a motivace

Timsort má operaˇcn´ı sloˇzitost v nejhorˇs´ım pˇr´ıpadˇe O(nlogn), ale v praxi provád´ı u ˇcásteˇcnˇe seˇrazených pol´ı mnohem ménˇe porovnáván´ı. Jeho nevýhoda je, ˇze podstatná ˇcást algoritmu je závislá na vykonáván´ı se v urˇcitém poˇrad´ı a tedy je sloˇzité ho paralelizovat.

Jeho efektivn´ı paralelizace by mohla vést ke zrychlen´ı standardn´ıch algoritm˚u v r˚uzných jazyc´ıch a t´ım i ke zrychlen´ı aplikac´ı, které je vyuˇz´ıvaj´ı.

Hlavn´ım c´ılem práce je tedy implementace paraleln´ı verze algoritmu Tim- sort a jej´ı porovnán´ı s jinými algoritmy, sekvenˇcn´ı verz´ı a r˚uznými paraleln´ımi verzemi. Mˇeˇren´ı chci provést pro r˚uzné typy dat abych mˇel o efektivitˇe ˇreˇsen´ı co nejpˇresnˇejˇs´ı pˇredstavu.

Pro paralelizaci budu vyuˇz´ıvat technologii OpenMP a C++ Thread support library, podle konkr´etn´ıho postupu paralelizace.

1.2 Z´ akladn´ı pojmy

V pr´aci budu pracovat s n´asleduj´ıc´ı term´ıny:

tˇr´ıd´ıc´ı algoritmy jsou skupina algoritm˚u zabývaj´ıc´ı se ˇrazen´ım pole prvk˚u dle urˇcitého kritéria, typicky podle jejich velikosti

vlákno je proud instrukc´ı, který je zpracováván jádrem CPU [1]

sekvenˇcn´ı algoritmus bˇeˇz´ı cel´y pouze na jednom vl´aknˇe

paraleln´ı algoritmus vyuˇz´ıvá v nˇekterých svých ˇcástech v´ıce vláken run seˇrazená ˇcást tˇr´ıdˇeného pole v algoritmu Timsort

(18)

1. C´ıl pr´ace a z´akladn´ı pojmy

mutex, condition variable a semaphore jsou synchronizaˇcn´ı typy, pou- ˇz´ıvané k zajiˇstˇen´ı výluˇcného pˇr´ıstupu k dat˚um, pˇr´ıpadnˇe synchronizace posloupnosti provádˇen´ı operac´ı na v´ıce vláknech [2][3][4]

Merge (sluˇcován´ı) je proces, pˇri kterém spoj´ıme dvˇe seˇrazená pole do jednoho vˇetˇs´ıho seˇrazeného pole

Galloping (cval) je metoda pouˇz´ıvaná pro rychlejˇs´ı zjiˇstˇen´ı délky seˇrazené posloupnosti menˇs´ı (resp. vˇetˇs´ı) neˇz daný prvek

cache je pamˇet’ na procesoru, slouˇz´ıc´ı k rychlejˇs´ımu pˇr´ıstupu k dat˚um, se kter´ymi procesor pracuje

1.3 Pouˇ zit´ e technologie

1.3.1 OpenMP

Pro naivn´ı paralelizaci algoritmu jsem vyuˇzil technologii OpenMP.

Je to soustava direktiv pro pˇrekladaˇc a knihovn´ıch procedur pro paraleln´ı programován´ı. Jedná se o standard pro programován´ı poˇc´ıtaˇc˚u se sd´ılenou pamˇet´ı. OpenMP usnadˇnuje vytváˇren´ı v´ıcevláknových program˚u v programo- vac´ıch jazyc´ıch Fortran, C a C++. [5]

D˚uvodem ke zvolen´ı této technologie byl fakt, ˇze pˇri pouˇzit´ı této technologie programátorovi staˇc´ı oznaˇcit blok kódu, který se má provádˇet paralelnˇe a pˇrekladaˇc to tak naimplementuje. [6]

1.3.2 C++ Thread support library

V komplikovanˇejˇs´ı druhé verzi paraleln´ıho algoritmu bych si s technologi´ı OpenMP nevystaˇcil a musel jsem paralelizovat manuálnˇe. Vyuˇz´ıvám k tomu C++ Thread support library. Tato knihovna obsahuje mimo jiné tˇr´ıdy a funkce pro správu vláken (vytvoˇren´ı a zruˇsen´ı), synchronizaci mezi nimi (uzamykán´ı kritických sekc´ı) a jejich plánován´ı a spouˇstˇen´ı. [7]

4

(19)

Kapitola 2

Algoritmus Timsort

V této práci vycház´ım z algoritmu tak jak byl pospán v p˚uvodn´ım Peter- sovˇe návrhu. Dále jsem ˇcerpal z text˚u Merge Strategies: from Merge Sort to TimSort a Understanding timsort, Part 1: Adaptive Mergesort. [8], [9], [10]

Timsort je ve své podstatˇe modifikovaný Merge sort. Algoritmus hledá sekvence jiˇz seˇrazených dat (tˇemto se ˇr´ıká runy) a pr˚ubˇeˇznˇe je podle jistých pravidel sluˇcuje.

Dalˇs´ı modifikace algoritmu oproti mergesortu spoˇc´ıvá v minimáln´ı velikosti tˇechto run˚u, tato velikost (minrun) se spoˇc´ıtá na základˇe velikosti celého tˇr´ıdˇeného pole pomoc´ı jednoduché formule. Pokud je run menˇs´ı neˇz je velikost minrun, pak se umˇele zvˇetˇs´ı o následuj´ıc´ı prvky v poli pomoc´ı insertion sortu.

Ve vlastn´ım sluˇcován´ı je implementováno nˇekolik dalˇs´ıch heuristik, které zmenˇsuj´ı velikost sluˇcovaných pol´ı (nalezen´ı prvk˚u, které by se pˇri sluˇcován´ı nepohly) a sniˇzuj´ı poˇcet porovnáván´ı u ˇcásteˇcnˇe seˇrazených pol´ı.

2.1 Hled´ an´ı run˚ u

Nejprve algoritmus najde v poli postupným procházen´ım podpousloupnosti, které jsou bud’ neklesaj´ıc´ı

(a0<=a1<=a2<=...) nebo ostˇre klesaj´ıc´ı

(a0> a1> a2> ...)

Ostˇre klesaj´ıc´ı podposloupnost následnˇe otoˇc´ıme, postupným prohazová- n´ım prvk˚u na zaˇcátku a konci jeˇstˇe nesetˇr´ıdˇené podposloupnosti. Tato posloupnost mus´ı být ostˇre klesaj´ıc´ı, aby se zabránilo pˇr´ıpadné destabilizaci algoritmu.

Pˇri práci s náhodnými daty je velmi nepravdˇepodobné, ˇze naraz´ıme na dlouhé runy. Pokud algoritmus naraz´ı na run kratˇs´ı neˇz je daná hodnota minrun dopln´ı tento run do poˇzadované délky pomoc´ı insertion sortu.

(20)

2. Algoritmus Timsort

M inrun vol´ıme z intervalu (32,64) takové, aby N/minrun bylo pokud moˇzno rovné 2ⁱ, kde i∈N.N je zde celkový poˇcet prvk˚u v poli. Pokud toto nen´ı moˇzné, chceme aby se N/minrunbl´ıˇzilo nˇekteré mocninˇe dvou zezdola.

Tohoto dosáhneme snadno pomoc´ı následuj´ıc´ıho algoritmu. Vezmˇeme prvn´ıch 6 bit˚u zN a pokud nejsou vˇsechny zbývaj´ıc´ı bity rovny nule pˇriˇctˇeme jedniˇcku.

Tento výbˇer pokrývá vˇsechny pˇr´ıpady vˇcetnˇe malýchN.

V kódu 2.1 vid´ıme jak algoritmus pracuje. Promˇennárznaˇc´ı zda je nˇekterý z bit˚u po prvn´ıch 6 bitechN nastavený na 1. Konstantamax mergeje rovná 64 a slouˇz´ı k zajiˇstˇen´ı právˇe 6 prvn´ıch bit˚u ˇc´ıslaN.

Ukázka kódu 2.1: Poˇc´ıtán´ı hodnoty minrun i n t CountMinRun (i n t N) {

i n t r = 0 ;

while (N>= max merge ) { r |= (N & 1 ) ;

N >>= 1 ; }

return N + r ; }

2.2 Strategie sluˇ cov´ an´ı

Z d˚uvodu vyuˇz´ıván´ı ˇcásteˇcnˇe setˇr´ıdˇených dat m˚uˇzeme z´ıskat runy r˚uzných délek. S ohledem na stabilitu m˚uˇzeme sluˇcovat pouze soused´ıc´ı runy.

Kdyˇz nalezneme run, vloˇz´ıme jeho poˇcátek a délku na zásobn´ık. Poté se kontroluje stav, a rozhoduje se zda budeme runy sluˇcovat, ˇci nikoliv. Sluˇcován´ı nechceme pˇr´ıliˇs oddalovat, abychom nemˇeli pˇr´ıliˇs velký zásobn´ık a abychom vyuˇzili faktu, ˇze právˇe pˇridané runy jsou na vyˇsˇs´ı pozici v pamˇet’ové hiear- chii. Na druhou stranu chceme ale sluˇcovat co nejefektivnˇeji a tedy formovat strategii na zakládˇe informac´ı z´ıskaných z v´ıce run˚u.

Merge prob´ıhá rychleji na podobnˇe dlouhých pol´ıch. Abychom doc´ılili po- stupného vyrovnáván´ı délek snaˇz´ıme se na zásobn´ıku dodrˇzovat dvˇe nerovnice:

1. A > B+C 2. B > C

Kde A, B, C jsou velikosti posledn´ıch tˇr´ı run˚u vloˇzených, v tomto poˇrad´ı, na zásobn´ık. Druhá nerovnice zajiˇst’uje, ˇze na zásobn´ıku máme klesaj´ıc´ı posloupnost délek run˚u a prvn´ı zajiˇst’uje rychlost r˚ustu délek, poˇc´ınaje od posled- n´ıho prvku zásobn´ıku, je minimálnˇe taková, jako rychlost r˚ustu Fibonacciho posloupnosti, a tedy zajiˇstˇen´ı maximáln´ı velikosti zásobn´ıku rovnou log_φN, kdeφ≈1.618 je zlatý ˇrez.

6

(21)

2.3. Algoritmy sluˇcov´an´ı

Pokud jsou tyto nerovnice poruˇseny je B slouˇceno z kratˇs´ım z run˚uAaC.

Pokud jsou runy A i C stejnˇe dlouhé, sluˇcujeme B s C, z d˚uvodu ˇcerstvosti v pamˇeti a tedy vyuˇz´ıván´ım cache. Na zásobn´ıku slouˇcené runy nahrad´ıme jejich výsledným a znovu zkontrolujeme nerovnice.

2.3 Algoritmy sluˇ cov´ an´ı

Sluˇcujeme-li dva runy o délkách Aa B chceme uˇsetˇrit pomocnou pamˇet’ kterou vyuˇz´ıváme. Jeden z krok˚u, který proto podnikáme je oˇr´ıznut´ı tˇechto pol´ı o prvky, se kterými jiˇz nebudeme hýbat. Pomoc´ı binárn´ıho vyhledáván´ı nalezneme poziciB[0] vA aA[max] vB. Prvky vA, pˇred pozic´ıB[0], resp. prvky vB za pozic´ıA[max] jsou jiˇz setˇr´ıdˇené a tedy m˚uˇzeme pracovat s poli o tyto prvky zkrácenými.

Porovnáme délky zkrácených pol´ıA1 aB1 a vytvoˇr´ıme pomocnou pamˇet’ o délce kratˇs´ıho z nich, do které poté kratˇs´ı pole nahrajeme a zaháj´ıme sluˇcován´ı.

Podle toho, které pole jsme nahráli do pomocné pamˇeti budeme postupovat od nejmenˇs´ıho nebo nejvˇetˇs´ıho prvku a tedy sluˇcovat pole zleva respektive zprava. Obˇe tyto verze jsou v podstatˇe analogické, jen zrcadlovˇe obrácené.

Uk´azka k´odu 2.2: Merge void Merge ( Run ∗a , Run ∗b ) {

// H l e d e j a [ l a s t ] v b // H l e d e j b [ 0 ] v a // o r e z s l u c o v a n a p o l e i f ( l e n g t h A <= l e n g t h B ) {

MergeLo ( s t a r t A , s t a r t B , lengthA , l e n g t h B ) ; } e l s e {

MergeHi ( s t a r t A , s t a r t B , lengthA , l e n g t h B ) ; }

// S p o j runy na z a s o b n i k u }

(22)

2. Algoritmus Timsort

Uk´azka k´odu 2.3: MergeLo void MergeLo ( ) {

NahrajADoTmpArray ( ) ; while ( 1 ) {

i f ( g a l l o p > 0 ) { // p r o v e d g a l l o p i n g

// z k o n t r o l u j z d a s e g a l l o p i n g v y p l a t i l } e l s e {

// p r o v e d l i n a r n i p r i d a v a n i i f ( p r e k r o c e n m i n g a l l o p )

// p r e j d i do g a l l o p i n g u }

i f ( d o s a h l jsem konce j e d n o h o p o l e ) { // v y p i s z b y t e k d r u h e h o p o l e

break; }

} }

2.4 Galloping

Klasické sluˇcován´ı pouˇz´ıvá mezi A a A+B porovnáván´ı. Pokud jsou ovˇsem data ˇcásteˇcnˇe setˇr´ıdˇená, m˚uˇzeme pˇredpokládat ˇze budeme z obou pol´ı vyb´ırat vˇetˇs´ı celky najednou. Zde m˚uˇzeme uˇsetˇrit operace porovnáván´ı hledán´ım jak dlouhou sekvenci z jednoho pole budeme vyb´ırat. K tomu pouˇzijeme metodu tzv. cvalu (angl. galloping) neboli exponenciáln´ıho vyhledáván´ı.

Pˇri hledán´ı poziceA[0] vB, porovnávámeA[0] postupnˇe sB[0],B[1],B[3], . . . ,B[2ⁱ−1], . . . dokud nenaleznemek takové, ˇze

B[2^k−1−1]< A[0]≤B[2^k−1]

Poté ve vyhledaném úseku nalezneme pozici A[0] pomoc´ı bin´arn´ıho vy- hledáván´ı.

Problém s t´ımto vyhledáván´ım je ten, ˇze pro k ≤ 6 provád´ı lineárn´ı vy- hledáván´ı stejnˇe, nebo dokonce ménˇe porovnán´ı. Z tohoto d˚uvodu nechceme provádˇet exponenc´ıáln´ı vyhledáván´ı pokud bychom nemˇeli alespoˇn urˇcité ná- znaky, ˇze se nám vyplat´ı. Do módu cvalu se tedy bude algoritmus pˇrep´ınat pouze tehdy, bude-li brát M IN GALLOP poˇcet prvk˚u z jednoho pole za sebou.

8

(23)

2.4. Galloping

Uk´azka k´odu 2.4: Galloping i n t GallopLeftInTmp ( ) {

// n a j d i k t a k o v e , z e :

//B[ 2 ˆ{k−1}−1] < A [ 0 ] <= B[ 2 ˆ k−1]

// pomoci b i n a r n i h o h l e d a n i n a j d i // v danem u s e k u m

// t a k o v e , z e B [m−1]<A[0]<=B [m]

return m;

}

Promˇenná M IN GALLOP bude m´ıt výchoz´ı hodnotu rovnou 7, tedy k takové, pro které cval v´ıtˇez´ı nad lineárn´ım vyhledáván´ım. Tuto promˇennou zvýˇs´ıme kdykoli se nám pˇrepnut´ı na cval nevyplatilo (abychom pˇredeˇsli ná- hodným pˇrepnut´ım v pol´ıch, kde se zjevnˇe nevyplat´ı) a naopak sn´ıˇz´ı pokud se nám vyplat´ı, abychom se do módu mohli snadnˇeji vrátit, pokud bychom z nˇej vypadli v poli, kde se nám celkovˇe vyplác´ı.

(24)

(25)

Kapitola 3

Anal´ yza a n´ avrh

Pˇri n´avrhu jsem se snaˇzil o to, aby timsort nab´ızel stejn´e vyuˇzit´ı jako std ::

sort. Pracoval jsem ve dvou f´az´ıch.

3.1 Moˇ znosti optimalizace sekvenˇ cn´ı verze

Timsort je ve své podstatˇe velice dobˇre softwarovˇe optimalizovaný pro sek- venˇcn´ı bˇeh programu. Zde se tedy nab´ız´ı pouze vyuˇzit´ı pˇrekladaˇcových opti- malazic´ı.

Z výhod sekvenˇcn´ı verze Timsortu zm´ın´ım efektivn´ı práci s cache na procesoru (pracuje se primárnˇe na datech která byla v nedávné dobˇe zkoumána a tedy je velká pravdˇepodobnost, ˇze se stále v cache nacház´ı) a efektivn´ı volen´ı sluˇcován´ı run˚u stejné délky.

3.2 Moˇ znosti paralelizace

Moˇznost´ı paralelizace se nab´ız´ı nˇekolik:

3.2.1 Naivn´ı verze

Zjevný a na prvn´ı pohled nejsp´ıˇse i nejúspˇeˇsnˇejˇs´ı postup je u velkého pole (u malých by paralelizace naopak sp´ıˇs zdrˇzovala) rozdˇelen´ı na X zhruba stejnˇe velkých ˇcást´ı (X je poˇcet CPU které máme k dispozici) a následném spuˇstˇen´ı algoritmu paralelnˇe na kaˇzdé ˇcásti zvláˇst’, tyto ˇcásti nakonec pˇridám jako runy do klasického Timsortu kde dojde k jejich, ted’ uˇz sekvenˇcn´ımu, slouˇcen´ı.

3.2.2 Pokroˇcil´a verze

Druhou moˇznost´ı je zavrhnout pravidla pro postupn´e sluˇcov´an´ı a sluˇcovat runy najednou, jak navrhuje Saurabh Sood [11] Zde sice m˚uˇze nastat situ-

(26)

3. Anal´yza a n´avrh

ace neefektivn´ıho sluˇcován´ı (dlouhý run s krátkým), nicménˇe zisk obdrˇzený paralelizac´ı by toto mˇel v´ıce neˇz vykompenzovat.

Pro kaˇzdý run vytvoˇr´ıme samostatné vlákno, kterému pˇridˇel´ım poˇradové ˇc´ıslo i. Toto vl´akno spust´ı metodu Check, kter´e pˇredá i a ukazatel na run, a po jej´ım proveden´ı uvoln´ı run ke zpracován´ı ostatn´ımi vlákny a ukonˇc´ı se.

MetodaCheckpro licháineprovede nic a ukonˇc´ı se. Pro sudáivlákno slouˇc´ım s runem pˇredchoz´ım (runy jsou ukládány ve spojovém seznamu) a rekurzivnˇe opˇet zavolám metodu Checktentokrát s parametrem i/2. n

3.2.3 Dalˇs´ı moˇznosti

Zvaˇzoval jsem i moˇznost paralelizace algoritmu Timsort tak jak je, tedy nechat bˇeˇzet hledán´ı run˚u na jednom vláknˇe nicménˇe bˇehem analýzy jsem dospˇel k tomu, ˇze pˇri ˇr´ızen´ı se postupným sluˇcován´ım run˚u bych paralelizaci poˇrádnˇe nevyuˇzil. Mohl bych ji vyuˇz´ıt k prohledáván´ı pole zároveˇn se sluˇcován´ım prvn´ıch nalezených run˚u, nicménˇe u této varianty by mi bˇeˇzeli maximálnˇe dvˇe vlákna najednou a bˇeh vlákna hledaj´ıc´ıho runy je mnohonásobnˇe kratˇs´ı, neˇz bˇeh vlákna které by nalezené runy sluˇcovalo a tak jsem tuto variantu zavrhl.

12

(27)

Kapitola 4

Realizace

Implementoval jsem tˇri verze algoritmu:

• Sekvenˇcn´ı verze

• Paraleln´ı verze s OpenMP

• Paraleln´ı verze s C++ Thread

Tyto jsem porovn´aval s verz´ı Timsortu podle gfx [12] a funkc´ı sort z knihovny std. [13]

4.1 Kompilace

Pro dodateˇcné kompilátorové optimalizace a vyuˇzit´ı moˇznost´ı procesor˚u v testovaném prostˇred´ı jsem vˇsechny verze kompiloval s pˇrep´ınaˇci -std=c++11 -O3 -march=corei7-avx.

D´ale jsem z d˚uvod˚u vyuˇzit´ı technologie OpenMP pˇri kompilaci naivn´ı paraleln´ı verze pˇridal pˇrep´ınaˇc -fopenmp.

U pokroˇcil´e paraleln´ı verze jsem pouˇzil pˇrep´ınaˇc -pthreads.

4.2 Sekvenˇ cn´ı verze

Sekvenˇcn´ı verzi jsem implementoval pˇresnˇe podle algoritmu popsaného ve tˇret´ı kapitole. Pro algoritmus implementuji tˇr´ıdu TimSort, která implementuje funkce slouˇz´ıc´ı k hledán´ı run˚u, tˇr´ıdu StackTimSort, které implementuje funkce sluˇcován´ı a udrˇzuje zásobn´ık s runy, a tˇr´ıdu RunTimSort, která reprezentuje jednotlivé runy a udrˇzuje informaci o nich.

Pro dodateˇcné kompilátorové optimalizace a vyuˇzit´ı moˇznost´ı procesor˚u v testovaném prostˇred´ı jsem tuto verzi kompiloval s pˇrep´ınaˇci -std=c++11 -O3 -march=corei7-avx.

(28)

4. Realizace

4.2.1 Tˇr´ıda TimSort

Tˇr´ıda TimSort má na starosti hledán´ı run˚u a jejich pˇridáván´ı na zásobn´ık, implementuje tyto metody:

Sort Hlavn´ı metoda, kde se spouˇst´ı hledán´ı run˚u a dále se, po projet´ı celého seznamu, slouˇc´ı jeˇstˇe neslouˇcené runy

SearchForRuns Metoda, která vyhledává runy a pˇridává je na zásobn´ık implementovaný tˇr´ıdou StackTimSort

CountMinRun Pomocná metoda, která vypoˇc´ıtá velikost minrun pro da- nou délku pole

InsertUntilMinRun Metoda, která pomoc´ı insertion sort prodluˇzuje nale- zený run na délkuminrun

BinarySearch Pomocná metoda, pouˇzitá v metodˇe InsertUntilMinrun, vy- hledává pozici pˇridáváného prvku v jiˇz seˇrazené ˇcásti runu

Reverse Pokud je nalezený run sestupný, tato metoda ho obrát´ı

RunLength Hledá sekvenci jiˇz seˇrazených prvk˚u, vrac´ı délku sekvence a informaci o tom, zda je sekvence klesaj´ıc´ı, ˇci neklesaj´ıc´ı

a uchovává tyto promˇenné:

array ukazatel na zaˇcátek tˇr´ıdˇeného pole length délka tˇr´ıdˇeného pole

stack ukazatel na tˇr´ıdu reprezentuj´ıc´ı z´asobn´ık 4.2.2 Tˇr´ıda StackTimSort

Tˇr´ıda StackTimSort reprezentuje zásobn´ık nalezených run˚u a má na starosti kontrolován´ı pravidel na vrcholu zásobn´ıku a sluˇcován´ı run˚u. Implementuje tyto metody:

AddRun Metoda, která pˇridá na zásobn´ık nalezený run s danými parametry a poté zavolá metoduCheck

Check Meto, která kontroluje dodrˇzován´ı pravidel na vrcholu zásobn´ıku (a t´ım omezuje jeho maximáln´ı velikost), pokud jsou pravidla poruˇsena, zavolá metoduM erge

Merge Metoda, která provede pˇr´ıpravné operace pˇred vlastn´ım sluˇcován´ım, které provád´ı metody M ergeHi a M ergeLo, a n´aslednˇe spoj´ı runy do toho novˇejˇs´ıho a starˇs´ı vymaˇze.

14

(29)

4.3. Paraleln´ı verze 1

MergeHi + MergeLo Metody, které provád´ı samotné sluˇcován´ı, liˇs´ı se v tom zda postupuj´ı zleva ˇci zprava.

ExponentialSearchLeft + ExponentialSearchRight Metody tzv. cvalu, pro nalezen´ı pozice prvku v poli

GallopLeftInTmp + GallopRightInTmp Metody tzv. cvalu, pro nalezen´ı pozice prvku v poli, na rozd´ıl od ExponentialSearchhledá ve vy- tvoˇreném pomocném poli

Dále uchovává tyto promˇenné:

array ukazatel na zaˇcátek tˇr´ıdˇeného pole length délka tˇr´ıdˇeného pole

last ukazatel na posledn´ı run na z´asobn´ıku count poˇcet run˚u na z´asobn´ıku

min gallop udává po kolika pˇridán´ı ze stejného pole se pˇreskoˇc´ı na mód cvalu 4.2.3 Tˇr´ıda RunTimSort

Tˇr´ıda RunTimSort udrˇzuje informace o jednotlivých runech a skládá se z tˇechto promˇenných:

start pozice zaˇcátku setˇr´ıdˇeného run v poli length délka setˇr´ıdˇeného runu

previous ukazatel na pˇredchoz´ı run na z´asobn´ıku next ukazatel na n´asleduj´ıc´ı run (defaultnˇe nullptr)

4.3 Paraleln´ı verze 1

V t´eto verzi jsem vyuˇzil technologii OpenMP. Vlastn´ı pole jsem pˇri pˇrekroˇcen´ı P ARALLEL M IN prvk˚u, rozdˇelil naN U M T HREADS ˇc´ast´ı.

P ARALLEL M IN aN U M T HREADSjsou konstanty, které je potˇreba volit podle hardwaru na kterém má algoritmus bˇeˇzet.

Kaˇzdá ˇcást pracuje se svým vlastn´ım zásobn´ıkem. Tyto seˇrazené ˇcásti jsou pak pˇridávány na hlavn´ı zásobn´ık, který je postupnˇe sluˇcuje podle pravidel Timsortu. Následnˇe se slouˇc´ı jeˇstˇe neslouˇcené ˇcásti. Vzhledem k tomu, ˇze poˇcet ˇ

cást´ı je stejný jako poˇcet vláken, a tedy bude kaˇzdé vlákno zpracovávat právˇe jednu iteraci for cyklu, nemus´ım ˇreˇsit zp˚usob pˇridˇelován´ı práce vlákn˚um.

Vnitˇrek algoritmu funguje obdobnˇe jako sekvenˇcn´ı verze.

(30)

4. Realizace

Uk´azka k´odu 4.1: Parallel Sort

#pragma omp p a r a l l e l f o r n u m t h re a d s (NUM THREADS) f o r (i n t i =0; i < NUM THREADS ; i ++) {

1 . v y t v o r e n i z a s o b n i k u pro t e n t o beh Timsortu 2 . p r o v e d e n i Timsortu na danem useku

3 . smazani z a s o b i k u }

4.4 Paraleln´ı verze 2

V druhé paraleln´ı verzi vlákna implementuji manuálnˇe pomoc´ı C++ Thread support library. Vyuˇz´ıvám knihovny thread, mutexacondition variable. Vy- uˇzil jsem také tˇr´ıdu Semaphore podle StackOverflow. [14] K implementaci mi pˇribyla tˇr´ıda TimSortTask, která uchovává informace o zadané práci pro jednotlivá vlákna. Tato informace je ve tˇr´ıdˇe uloˇzena ve formˇe ukazatele na run, který bude pro operace sluˇcován´ı výchoz´ı a ˇc´ısla num, kter´e v sobˇe má uloˇzenou informaci o zda a kolikrát se má run slouˇcit s pˇredchoz´ım runem, jak bude vysvˇetleno pozdˇeji. Jedná se v podstatˇe o implementaci problému producenta a konzumenta. [2]

Uk´azka k´odu 4.2: TimSortTask c l a s s TimSortTask {

public:

RunTimSort ∗ run ; i n t num ;

};

MetodaSortnejprve vygenerujeN U M T HREADS−1 vláken na kterých bˇeˇz´ı metoda T hreadRun. N´aslednˇe se na hlavn´ım vláknˇe, stejnˇe jako v sek- venˇcn´ı verzi, zavolá metoda SearchF orRuns, kter´a nalezené runy pˇridá na zásobn´ık a zároveˇn pˇridá do fronty úkol˚u ukazatel na tento run, spoleˇcnˇe s ˇc´ıslemnum, které v tuto chv´ıli nen´ı nic jiného neˇz poˇradové ˇc´ıslo nalezeného runu. Tedynum≥1.

Poté co dobˇehne metoda SearchF orRuns se i na hlavn´ım vláknˇe spust´ı metoda T hreadRun. T´ımto zp˚usobem mohu m´ıt neustále zamˇestnaných aˇz N U M T HREADSvláken. Ke konci bˇehu algoritmu ovˇsem uˇz nen´ı pro vlákna tolik úkol˚u a nemus´ı bˇeˇzet vˇsechna.

Význam ˇc´ısla numje následuj´ıc´ı. Pro poˇrad´ı sluˇcován´ı run˚u nemám nyn´ı ˇzádná pravidla, a mohl bych tedy sluˇcovat runy postupnˇe jak pˇricházej´ı, tento postup ale neumoˇzˇnuje paralelizaci. Nicménˇe pokud zde napodob´ım mergesort, a budu runy sluˇcovat po párech, paralelizace je nejen moˇzná, ale je dokonce i vhodná. Abych tohoto doc´ılil pˇredávám úkolu právˇe i poˇradové ˇc´ıslo 16

(31)

4.5. Druhá fáze testován´ı

daného runu. Pokud je toto ˇc´ıslo liché, v´ım, ˇze tento run s jemu pˇredcházej´ıc´ım runem nemám sluˇcovat, jelikoˇz sluˇcuji právˇe kaˇzdý druhý run s runem pˇred- choz´ım. Nav´ıc, po slouˇcen´ı - a tedy zmˇenˇe pˇredchoz´ıho runu - toto ˇc´ıslo vydˇel´ım dvˇemi a opˇet zkoumám jeho sudost. Nacház´ı se totiˇz o jednu hladinu bl´ıˇze vrcholu pomyslného binárn´ıho stromu, kterým se toto sluˇcován´ı dá reprezen- tovat.

Na následuj´ıc´ım pˇr´ıkladu vid´ıme jak do sebe struktury uchovávaj´ıc´ı runy se sudým ˇc´ıslem bˇehem sluˇcován´ı pojmou pˇredcházej´ıc´ı runy.

run1(num= 1)→run2(num= 2) run3(num= 3)→run4(num= 4)

& .

run2(num= 1)→run4(num= 2)

↓

run4(num= 1)

Toto s sebou pˇri paralelizaci nese riziko, ˇze se run bude snaˇzit slouˇcit s runem, který jeˇstˇe nedobˇehl svou sekvenci sluˇcován´ı. Tento problém ˇreˇs´ım pomoc´ı semaforu, který se odemkne aˇz ve chv´ıli, kdy je tento run oznaˇcený za uzavˇrený. T´ım upozorn´ı vlákno, které na nˇej pˇr´ıpadnˇe ˇceká, ˇze je jiˇz k dispozici a sluˇcován´ı m˚uˇze zaˇc´ıt.

4.5 Druh´ a f´ aze testov´ an´ı

Pˇred druhou fázi testován´ı jsem algoritmy pˇrebudouval na formátstd::sort, tedy aby pro tˇr´ıdˇen´ıˇsli pouˇz´ıt r˚uzné kontejnery, aby algoritmus pˇrij´ımal srovnávác´ı funkce apod. Hlavn´ı ˇcásti algoritm˚u jsem ovˇsem ponechal v p˚uvodn´ı podobˇe.

(32)

(33)

Kapitola 5

Metody mˇ eˇ ren´ı

5.1 server STAR

Server na kterém mˇeˇr´ım rychlosti jednotlivých verz´ı má dva ˇsestijádrové proce- sory Intel^R Xeon^R Processor E5-2620 v2. [15] [16] Celkovˇe tedy m˚uˇze souˇcasnˇe bˇeˇzet aˇz 12 vláken, odtud se odv´ıj´ı mnou zvolené konstanty pro poˇcet vláken.

Velikost RAM je 32 GB a tedy se na n´ı s velkou rezervou vejdou vˇsechna data, kter´a jsem pro mˇeˇren´ı v´ykon˚u pouˇzil.

5.2 Typy dat

Pro testov´an´ı jsem si vytvoˇril data nˇekolika typ˚u:

Seˇrazená data Data jsou seˇrazena vzestupnˇe Náhodná data Data jsou generována náhodnˇe

C´ˇasteˇcnˇe seˇrazená data Data jsou rozdˇelena do nˇekolika blok˚u, které jsou seˇrazené vzestupnˇe

Málo r˚uzných hodnot Data jsou generována náhodnˇe z malého poˇctu r˚uzných hodnot

Seˇrazená data s výjimkami Data jsou ˇrazena vzestupnˇe s 1% pravdˇepo- dobnost´ı náhodného ˇc´ısla na kaˇzdé pozici

Vˇsechna data stejn´a Vˇsechna data jsou maj´ı stejnou hodnotu

Data jsem ukládal v binárn´ıch souborech, kv˚uli úspoˇre m´ısta na disku (i tak jsem pracoval s nˇekolika GB dat). Na jejich vytvoˇren´ı jsem si pˇripravil programdata creator. Tento program vygeneruje zadané mnoˇzstv´ı dat daného typu.

(34)

5. Metody mˇeˇren´ı

5.3 Metodika

K mˇeˇren´ıˇcasu jsem vyuˇzil knihovnychrono, ratioaotime. ˇR´ıd´ım se n´avodem z pˇredmˇetu BI-EIA. [17]

Testoval jsem ve dvou f´az´ıch.

5.3.1 Prvn´ı f´aze

V prvn´ı fázi jsem testoval nezobecnˇené algoritmy na poli integer˚u s operátorem

<. Toto mˇeˇren´ı bylo d˚uleˇzité pro základn´ı odhad efektivnosti jednotlivých verz´ı a porovnával jsem ho s ciz´ı implementac´ı sekvenˇcn´ı verze timsortu a std::sortem.

Pro testy jsem si vygeneroval data velikost´ı 1 000 000, 5 000 000, 10 000 000, 50 000 000, 100 000 000 a 500 000 000 prvk˚u.

Nad tˇemito daty jsem provedl tˇr´ıdˇen´ı kaˇzdou metodou 5× pro z´ıskán´ı pˇresnˇejˇs´ıch výsledk˚u. Tyto výsledné hodnoty jsem následnˇe porovnal s výsledky tˇr´ıdˇen´ı pomoc´ı std :: sort a vytvoˇril grafy pomˇeru rychlosti jednotlivých verz´ı právˇe v˚uˇci std :: sort. Tento zp˚usob zobrazován´ı výsledk˚u je v grafu pˇrehlednˇejˇs´ı, neˇz pouhé ˇcasy, nebot’ ˇcas tˇr´ıdˇen´ı je velmi odliˇsný pro jednotlivé velikosti dat i verze algoritmu.

5.3.2 Druh´a f´aze

V druhé fázi jsem mˇeˇril na stejných typech dat, nicménˇe jsem je pro úˇcely mˇeˇren´ı reprezentoval jinak. Vˇsechny verze jsem jiˇz mˇel zobecnˇené pro stejné uˇzit´ı jako std :: sort. Srovn´aval jsem vector tˇr´ıdy MyClass, která reprezen- tovala data pomoc´ı pole 32 boolean˚u. Pouˇzitý komparátor nejprve poskládal z pole boolean˚u p˚uvodn´ı integer zpˇet a aˇz poté provedl samotné porovnán´ı.

Tento postup mˇel simulovat ˇrazen´ı sloˇzitˇejˇs´ıch objekt˚u.

Pro testy jsem si vygeneroval data velikost´ı 1 000 000, 5 000 000, 10 000 000 a 50 000 000 prvk˚u. S v´ıce prvky jsem jiˇz netestoval, jelikoˇz tˇr´ıdit velk´a pole s velice pomalou srovn´avac´ı funkc´ı by trvalo pˇr´ıliˇs dlouho.

Opˇet jsem provedl mˇeˇren´ı nad tˇemito daty 5× a v´ysledn´e hodnoty zanesl do grafu jako pomˇer v˚uˇcistd::sort.

20

(35)

Kapitola 6

V´ ysledky mˇ eˇ ren´ı

6.1 Prvn´ı f´ aze

6.1.1 N´ahodn´a data

Pˇri pohledu na graf náhodných dat 6.1 si m˚uˇzeme vˇsimnout, ˇzestd::sort je kromˇe naivn´ı paraleln´ı verze nejrychlejˇs´ı. Toto pozorován´ı odpov´ıdá výsled- k˚um, které namˇeˇril Tim Peters. [18]

Obrázek 6.1: Náhodná data

6.1.2 M´alo r˚uzn´ych hodnot

Na grafu mˇeˇren´ı dat s málo r˚uznými hodnotami 6.2 opˇet vid´ıme, ˇzestd::sort je rychlejˇs´ı. Opˇet m˚uˇzeme stejný trend pozorovat i u Petersových výsledk˚u.

(36)

6. V´ysledky mˇeˇren´ı

[18]

Obrázek 6.2: Málo ruzných hodnot

6.1.3 Seˇrazen´a data s v´yjimkami

Na grafu mˇeˇren´ı dat s vyj´ımkami 6.3 je naivn´ı paralelizace suverénˇe nejrych- lejˇs´ı, pokroˇcilá paralelizace je zde podobnˇe rychlá jako std :: sort a tedy nˇekolikanásobnˇe pomalejˇs´ı, neˇz sekvenˇcn´ı verze.

6.1.4 Seˇrazen´a a stejn´a data

Za povˇsimnut´ı stoj´ı témˇeˇr stejný graf pro seˇrazená data 6.5 a graf stejných hodnot 6.4. Pro timsort jsou tato data prakticky totoˇzná, pole stejných hodnot je totiˇz také jiˇz seˇrazené a timsort tedy celé pole projde jen jednou. Zrychlen´ı oprotistd::sort je témˇeˇr desetinásobné u vˇsech variant.

6.1.5 C´ˇasteˇcnˇe seˇrazen´a

To samé se dá ˇr´ıct i o mˇeˇren´ı na ˇcásteˇcnˇe seˇrazených datech 6.3 s t´ım rozd´ılem, ˇze na tˇechto datech je pokroˇcilá paralelizace rychlejˇs´ı, neˇz ta naivn´ı. Tento jev bude zp˚usobený t´ım, ˇze pˇri naivn´ı paralelizaci dˇel´ıme pole na v´ıce ˇcást´ı, neˇz kolik máme v datech vnoˇrených seˇrazených podposloupnost´ı. Z tohoto d˚uvodu provád´ı naivn´ı paralelizace v´ıce sluˇcován´ı. Nicménˇe, jak je vidˇet, zrychlen´ı v˚uˇci sekvenˇcn´ı verzi nen´ıpˇr´ıliˇs znatelné.

22

(37)

6.1. Prvn´ı f´aze

Obrázek 6.3: Seˇrazená data s výjimkami

Obr´azek 6.4: Vˇsechna data stejn´a

6.1.6 Shrnut´ı prvn´ı f´aze

Z namˇeˇrených dat mi vyplynula jako nejlepˇs´ı ˇreˇsen´ı naivn´ı paralelizace. Po- kroˇcilá verze se ukázala jako dosti nevhodná. Naivn´ı paralelizace ji pˇredˇcila na vˇsech typech dat, kromˇe ˇcásteˇcnˇe seˇrazených, a nav´ıc se u náhodných dat, seˇrazených s nˇekolika výjimkami a na datech s malým poˇctem r˚uzných hodnot ukázala jako naprosto neefektivn´ı.

(38)

Obr´azek 6.5: Seˇrazen´a data

Obrázek 6.6: ˇCásteˇcnˇe seˇrazená data

Toto m˚uˇze být d˚usledek spojován´ı r˚uznˇe velkých podposloupnost´ı a také plným nevyuˇzit´ım vˇsech vláken u nˇekolika posledn´ıch, a tedy i nejnároˇcnˇejˇs´ıch, sluˇcován´ı.

Vlákna nejsou plnˇe vyuˇzita z d˚uvodu, ˇze pˇri sluˇcován´ı nˇekolika posledn´ıch run˚u máme ménˇe ˇcást´ı, neˇz vláken a tedy pro vlákna nemáme práci. Práce nad stejnou frontou úkol˚u také m˚uˇze algoritmus zdrˇzovat, jelikoˇz mus´ıme zabránit 24

(39)

6.2. Druh´a f´aze

pˇr´ıstupu k frontˇe v´ıce vlákn˚um najednou a tedy roste ˇcas kdy vlákna ˇcekaj´ı a nepracuj´ı. Ztráty zp˚usobené sluˇcován´ım run˚u, které nemus´ı být v cache a které nemus´ı být podobnˇe dlouhé algoritmus také zdrˇzuj´ı. Zaj´ımavá byla neefektivita tohoto zp˚usobu algoritmu u seˇrazených dat s vyj´ımkami, zde jsem oˇcekával od pokroˇcilé paralelizace mnohem lepˇs´ı vlastnosti. Zdá se ale, ˇze procento náhodných dat pˇrebije mnoˇzstv´ı ˇcásteˇcnˇe seˇrazených posloupnost´ı.

6.2 Druh´ a f´ aze

Ve druhé fázi testován´ı byly výsledky mnohem uspokojivˇejˇs´ı. Naivn´ı paraleln´ı verze se opˇet ukázala jako lepˇs´ı, nicménˇe i pokroˇcilá verze paraleln´ıho algoritmu pˇredvedla své kvality.

6.2.1 N´ahodn´a data

Na náhodných datech se opakuje pozorován´ı z prvn´ı fáze a totiˇz, ˇze ˇcistˇe náhodná data nejsou pro timsort to pravé. Obˇe dvˇe sekvenˇcn´ı verze poráˇz´ı std::sort.

Oproti prvn´ı fázi ale vid´ıme znatelné zlepˇsen´ı ve výkonu 2. paraleln´ı verze.

Vysvˇetluji si to t´ım, ˇze na jednoduché porovnávac´ı operace byla nároˇcnost na reˇzii pˇr´ıliˇs vysoká. Zde trvá srovnán´ı o nˇeco déle a tedy vlákno stráv´ı vˇetˇs´ı ˇ

cást svého ˇcasu aktivn´ı prac´ı, nam´ısto ˇcekán´ım.

Obrázek 6.7: Náhodná data - Fáze 2

(40)

6.2.2 M´alo r˚uzn´ych hodnot

Opˇet zde vid´ıme výrazné zlepˇsen´ı druhé verze paralelizace, skuteˇcnˇe se projevuje vˇetˇs´ı pomˇer aktivn´ıho ˇcasu. Za zm´ınku stoj´ı výrazné zlepˇsen´ı obou sekvenˇcn´ıch verz´ı - projevuje se zde úspornost Timsortu na porovnávac´ıch operac´ıch.

Obrázek 6.8: Málo r˚uzných hodnot - Fáze 2

6.2.3 Seˇrazen´a data s v´yjimkami

Naivn´ı verze je pro tyto data aˇz 100× rychlejˇs´ı, neˇz std::sort. Oproti prvn´ı fázi se zde jako velmi rychlá verze ukázala i druhá paraleln´ı.

6.2.4 Vˇsechna data stejn´a a Seˇrazen´a data

Podobný efekt pozorujeme i u dalˇs´ıch dvou typ˚u dat. Rozdˇelen´ı pole na stejné ˇcásti, které jsou následnˇe zpracovávány timsortem se jednoznaˇcnˇe vyplác´ı.

Zaj´ımavé je ovˇsem pozorován´ı, ˇze zat´ımcogf x::timsortmá na obou typech dat zhruba stejné ˇcasy, moje implementace je na seˇrazených datech o 1/4 rychlejˇs´ı neˇz na datech navzájem rovných. Zat´ımco tedy na seˇrazených datech je moje sekvenˇcn´ı verze rychlejˇs´ı neˇz gf x :: timsort, na rovn´ych datech je tomu obrácenˇe.

6.2.5 C´ˇasteˇcnˇe seˇrazen´a

U ˇcásteˇcnˇe seˇrazených dat opˇet pozorujeme ty samé tendence jako u dat seˇrazených plnˇe, s t´ım rozd´ılem, ˇze pokroˇcilá paraleln´ı verze je zde rychlejˇs´ı.

26

(41)

6.2. Druh´a f´aze

Obrázek 6.9: Seˇrazená data s výjimkami - Fáze 2

Obrázek 6.10: Vˇschna data stejná - Fáze 2

Je to t´ım, ˇze na seˇrazených datech pracuje celou dobu vlastnˇe pouze jedno vlákno, zde se dostane ke slovu vláken v´ıce.

(42)

Obrázek 6.11: Seˇrazená data - Fáze 2

Obrázek 6.12: ˇCásteˇcnˇe seˇrazená data - Fáze 2

6.2.6 Shrnut´ı druh´e f´aze

Druhá fáze potvrdila pozorován´ı z prvn´ı a tedy, ˇze naivn´ı verze je funkˇcn´ı a efektivn´ı. Také pokroˇcilá verze se na sloˇzitých porovnávac´ıch funkc´ıch ukázala jako efektivn´ı.

28

(43)

Z´ avˇ er

Bˇehem návrhu paraleln´ı verze jsem narazil na ˇradu slepých uliˇcek, ve výsledku jsem tedy musel pˇristoupit k paraleln´ı verzi algoritmu, která nˇekteré principy Timsortu pop´ırá. Bohuˇzel ani ta se nejprve neukázala jako pˇr´ıliˇs efektivn´ı. Pro nˇekteré typy dat byla dokonce i pomalejˇs´ı, neˇz verze sekvenˇcn´ı. Ve druhé fázi testován´ı, totiˇz na datech s drahou porovnávac´ı funkc´ı se ale pokroˇcilá verze algoritmu o nˇeco lépe a jej´ı vývoj tak nebyl úplnou ztrátou ˇcasu.

Z d˚uvodu pˇr´ıliˇsného lpˇen´ı na dodrˇzen´ı vˇsech pravidel Timsortu bˇehem poˇcátku návrhu a celkového vˇetˇs´ıho zamˇeˇren´ı na algoritmickou stránku pro- blému, oproti stránce implementaˇcn´ı mi nezbylo pˇr´ıliˇs ˇcasu na podrobné pro- zkoumán´ı moˇznost´ı implementace pomoc´ı r˚uzných technologi´ı.

Za úspˇech ale naopak povaˇzuji namˇeˇren´ı vysoké efektivity naivn´ı paraleln´ı verze, která si na vˇsech typech dat, s jedinou výjimkou, poˇc´ınala nejlépe.

Navázat na tuto práci se dá tedy ve dvou smˇerech: zdokonalit a zobec- nit naivn´ı verzi pro bˇeˇzné pouˇz´ıván´ı nebo prozkoumat úskal´ı verze pokroˇcilé, nejsp´ıˇse pˇr´ıliˇs drahou reˇzii pˇri obsluze jednotlivých vláken.

(44)

(45)

Literatura

[1] Trdliˇcka, J.: Procesy a vl´akna. [online], [cit. 2018-05-10]. Dostupn´e z: https://edux.fit.cvut.cz/courses/BI-OSY/_media/lectures/02/

bi-osy-p02-threads.pdf

[2] Trdliˇcka, J.: Synchronizace proces˚u/vl´aken. [online], [cit. 2018-05- 10]. Dostupn´e z: https://edux.fit.cvut.cz/courses/BI-OSY/_media/

lectures/03/bi-osy-p03-ipc-1.pdf

[3] std::mutex. [online], [cit. 2018-05-10]. Dostupn´e z: http:

//en.cppreference.com/w/cpp/thread/mutex

[4] std::condition variable. [online], [cit. 2018-05-10]. Dostupn´e z: http://

en.cppreference.com/w/cpp/thread/condition_variable

[5] OpenMP. [online], [cit. 2018-05-14]. Dostupn´e z: https:

//cs.wikipedia.org/wiki/OpenMP

[6] ˇSimeˇcek, I.:Modern´ı poˇc´ıtaˇcové architektury a optimalizace implementace algoritm˚u. Praha: ˇCeská Technika - nakladatelstv´ı ˇCVUT, prvn´ı vydán´ı, 2015, ISBN 978-80-01-05658-5.

[7] Thread Support Library. [online], [cit. 2018-05-10]. Dostupn´e z: http:

//en.cppreference.com/w/cpp/thread

[8] Peters, T.: TimSort. [online], [cit. 2018-04-25]. Dostupn´e z: https://

bugs.python.org/file4451/timsort.txt

[9] Auger, N.; Nicaud, C.; Pivoteau, C.: Merge Strategies: from Merge Sort to TimSort. 2015, [cit. 2018-04-25]. Dostupn´e z: https://hal-upec- upem.archives-ouvertes.fr/hal-01212839v2/document

[10] MacIver, D. R.: Understanding timsort, Part 1: Adaptive Mergesort.

[cit. 2018-04-25]. Dostupn´e z: https://www.drmaciver.com/2010/01/

understanding-timsort-1adaptive-mergesort/

(46)

Literatura

[11] Sood, S.: Parallelizing Timsort. Saurabh Sood’s Blog, [cit. 2015-10- 31]. Dostupn´e z: https://saurabhsoodweb.wordpress.com/2017/04/

18/parallelizing-timsort/

[12] gfx::Timsort. [online], [cit. 2018-04-25]. Dostupn´e z: https:

//github.com/gfx/cpp-TimSort

[13] std::sort. [online], [cit. 2018-04-25]. Dostupn´e z: https://

en.cppreference.com/w/cpp/algorithm/sort

[14] Semaphore. [online], [cit. 2018-05-06]. Dostupn´e z: https:

//stackoverflow.com/questions/4792449/c0x-has-no-semaphores- how-to-synchronize-threads

[15] Intel^R Xeon^R Processor E5-2620 v2. [online], [cit. 2018-05-10]. Dostupn´e z: https://ark.intel.com/products/75789/Intel-Xeon-Processor- E5-2620-v2-15M-Cache-2_10-GHz

[16] ˇSimeˇcek, I.: V´ypoˇcetn´ı prostˇredky. [online], [cit. 2018-05-10]. Dostupn´e z: https://edux.fit.cvut.cz/courses/MI-PAP/labs/vypocetni_

prostredky

[17] ˇSimeˇcek, I.: Mˇeˇren´ı ˇcasu. Dostupn´e z: https://edux.fit.cvut.cz/

courses/BI-EIA/tutorials/cas

[18] [Python-Dev] Sorting. [online], [cit. 2018-05-11]. Dostupn´e z: https://

mail.python.org/pipermail/python-dev/2002-July/026837.html

32

(47)

Pˇ r´ ıloha A

Obsah pˇ riloˇ zen´ eho CD

contents.txt ...struˇcný popis obsahu CD readme.txt ...návod ke kompilaci a spuˇstˇen´ı aplikace Makefile...makefile ke kompilaci a spuˇstˇen´ı aplikace exe ...adresáˇr se spustitelnou formou implementace src

impl...zdrojové kódy implementace Phase1...zdrojové kódy testován´ı prvn´ı fáze Phase2 ...zdrojové kódy testován´ı druhé fáze thesis ...zdrojová forma práce ve formátu LÂTEX text ...text práce thesis.pdf ...text práce ve formátu PDF zadani.pdf...zadán´ı práce ve formátu PDF results ...výsledky mˇeˇren´ı Phase1...v prvn´ı fázi Phase2 ...ve druhé fázi