Download
PDF 2.21 MB
master's thesis
69   46
Parallelization of sorting algorithms
Krešimir Šuljug (2017)
Josip Juraj Strossmayer University of Osijek
Faculty of Electrical Engineering, Computer Science and Information Technology Osijek
Department of Software Engineering
Chair of Programming Languages and Systems
Cite this document

Šuljug, K. (2017). Paralelne izvedbe algoritama za sortiranje (Master's thesis). Retrieved from https://urn.nsk.hr/urn:nbn:hr:200:717944

Šuljug, Krešimir. "Paralelne izvedbe algoritama za sortiranje." Master's thesis, Josip Juraj Strossmayer University of Osijek, Faculty of Electrical Engineering, Computer Science and Information Technology Osijek, 2017. https://urn.nsk.hr/urn:nbn:hr:200:717944

Šuljug, Krešimir. "Paralelne izvedbe algoritama za sortiranje." Master's thesis, Josip Juraj Strossmayer University of Osijek, Faculty of Electrical Engineering, Computer Science and Information Technology Osijek, 2017. https://urn.nsk.hr/urn:nbn:hr:200:717944

Šuljug, K. (2017). 'Paralelne izvedbe algoritama za sortiranje', Master's thesis, Josip Juraj Strossmayer University of Osijek, Faculty of Electrical Engineering, Computer Science and Information Technology Osijek, accessed 19 November 2019, https://urn.nsk.hr/urn:nbn:hr:200:717944

Šuljug K. Paralelne izvedbe algoritama za sortiranje [Master's thesis]. Osijek: Josip Juraj Strossmayer University of Osijek, Faculty of Electrical Engineering, Computer Science and Information Technology Osijek; 2017 [cited 2019 November 19] Available at: https://urn.nsk.hr/urn:nbn:hr:200:717944

K. Šuljug, "Paralelne izvedbe algoritama za sortiranje", Master's thesis, Josip Juraj Strossmayer University of Osijek, Faculty of Electrical Engineering, Computer Science and Information Technology Osijek, Osijek, 2017. Available at: https://urn.nsk.hr/urn:nbn:hr:200:717944

Metadata
TitleParalelne izvedbe algoritama za sortiranje
Title (english)Parallelization of sorting algorithms
AuthorKrešimir Šuljug
MentorZdravko Krpić (mentor)
Committee memberZdravko Krpić (predsjednik povjerenstva)
Committee memberJosip Balen (član povjerenstva)
Committee memberTomislav Matić (član povjerenstva)
GranterJosip Juraj Strossmayer University of Osijek
Faculty of Electrical Engineering, Computer Science and Information Technology Osijek
(Department of Software Engineering)
(Chair of Programming Languages and Systems)
Osijek
Defense date and country2017, Croatia
Scientific / art field,
discipline and subdiscipline		TECHNICAL SCIENCES
Computing
Process Computing
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.
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.
Keywords
Keywords (english)
Languagecroatian
URN:NBNurn:nbn:hr:200:717944
Study programmeTitle: Graduate University Study Programme in Computer Engineering
Study programme type: university
Study level: graduate
Academic / professional title: magistar/magistra inženjer/inženjerka računarstva (magistar/magistra inženjer/inženjerka računarstva)
Type of resourceText
File originBorn digital
Access conditionsOpen access
Terms of usehttp://rightsstatements.org/vocab/InC/1.0/
Created on2017-01-24 08:24:02