master's thesis
Parallelization of sorting algorithms

Krešimir Šuljug (2017)
Sveučilište Josipa Jurja Strossmayera u Osijeku
Fakultet elektrotehnike, računarstva i informacijskih tehnologija Osijek
Zavod za programsko inženjerstvo
Katedra za programske jezike i sustave
Metadata
TitleParalelne izvedbe algoritama za sortiranje
AuthorKrešimir Šuljug
Mentor(s)Zdravko Krpić (thesis advisor)
Abstract
Postoji više načina za paraleliziranje kodova ili algoritama. Neki od njih su MPI (engl. MessagePassing Interface) i OpenMP (engl. Open Multi-Processing). U radu se koristio OpenMP zbogjednostavnosti svoje upotrebe. OpenMP je zapravo API (engl. Application ProgrammingInterface) koji podržava multiprocesorsko programiranje s dijeljenom memorijom.U radu je prikazano koliko se paralelizam isplati na velikom broju podataka te je testirano srazličitim metodama paralelizacije da bi utvrdili koja se više isplati, kada, i zašto. Utvrđeno je dasu Radix sort i Merge sort, koji su paralelizirani s OpenMP smjernicom sections imali i do 3,31puta brže izvođenje koda nego njihova serijska verzija.S druge strane, Quick sort je paraleliziran pomoću smjernice task čije je ubrzanje paralelneverzije u odnosu na serijsku bilo čak 3,48 puta brže. Glavna karakteristika kod task-ova je što ćese broj niti podijeliti po taskovima i ako neka nit završi prije, pomoći će drugoj koja nije završila.
KeywordsMPI OpenMP directive speedup parallelism.
Parallel title (English)Parallelization of sorting algorithms
Committee MembersZdravko Krpić (committee chairperson)
Josip Balen (committee member)
Tomislav Matić (committee member)
GranterSveučilište Josipa Jurja Strossmayera u Osijeku
Fakultet elektrotehnike, računarstva i informacijskih tehnologija Osijek
Lower level organizational unitsZavod za programsko inženjerstvo
Katedra za programske jezike i sustave
PlaceOsijek
StateCroatia
Scientific field, discipline, subdisciplineTECHNICAL SCIENCES
Computing
Process Computing
Study programme typeuniversity
Study levelgraduate
Study programmeGraduate University Study Programme in Computer Engineering
Academic title abbreviationmag.ing.comp.
Genremaster's thesis
Language Croatian
Defense date2017
Parallel abstract (English)
There are several ways to paralelize a program code or an algorithm. Some of them are MPI(Message passing interface) and OpenMP (Open Multi-Processing). In this thesis OpenMP isused due to the simplicity of its use. OpenMP is actually an API (Application ProgrammingInterface) that supports multiprocessing programming with shared memory.The thesis describes how much parallelism is worth on a large number of data and has beentested with different methods of parallelization in order to give the best (fastest) solution for eachof the test cases. The conclusion is that Radix sort and Merge sort, which were parallelized withthe OpenMP directives sections, had up to 3.31 times faster execution of the program code thantheir standard version.On the other hand, Quick sort is parallelized using the directive called task, bringing even fasterspeedups of up to 3.48. The main characteristics of the tasks is that the number of threads isshared among tasks and if one thread finishes before the other, it will help another which has notfinished.
Parallel keywords (Croatian)MPI OpenMP smjernica ubrzanje paralelizam
Resource typetext
Access conditionOpen access
Terms of usehttp://rightsstatements.org/vocab/InC/1.0/
URN:NBNhttps://urn.nsk.hr/urn:nbn:hr:200:717944
CommitterAnka Ovničević