20.500.12556/RUL-30863 Vzporedni algoritmi za urejanje podatkov Comparison of parallel sorting algorithms V magistrskem delu smo preučili, implementirali in medsebojno primerjali zaporedne in vzporedne algoritme za urejanje podatkov. Implementirali smo sedem algoritmov, in sicer bitono urejanje, večkoračno bitono urejanje, prilagodljivo bitono urejanje, urejanje z zlivanjem, hitro urejanje, urejanje po delih in urejanje z vzorci. Zaporedne algoritme smo implementirali na centralno procesni enoti s pomočjo jezika C++, vzporedne pa na grafično procesni enoti s pomočjo arhitekture CUDA. Naštete implementacije vzporednih algoritmov smo delno tudi izboljšali. Poleg tega smo tudi zagotovili, da lahko urejajo zaporedja poljubne dolžine. Algoritme smo primerjali na zaporedjih števil različnih dolžin, porazdeljenih po šestih različnih porazdelitvah, ki so bila sestavljena iz 32-bitnih števil, 32-bitnih parov ključ-vrednost, 64-bitnih števil in 64-bitnih parov ključ-vrednost. Ugotovili smo, da je med zaporednimi algoritmi najhitrejše urejanje po delih, medtem ko je pri vzporednih algoritmih najhitrejše urejanje po delih ali urejanje z zlivanjem (odvisno od vhodne porazdelitve). Z vzporednimi implementacijami smo dosegli tudi do 157-kratno pohitritev v primerjavi z zaporednimi implementacijami. In this master's thesis we studied, implemented and compared sequential and parallel sorting algorithms. We implemented seven algorithms: bitonic sort, multistep bitonic sort, adaptive bitonic sort, merge sort, quicksort, radix sort and sample sort. Sequential algorithms were implemented on a central processing unit using C++, whereas parallel algorithms were implemented on a graphics processing unit using CUDA architecture. We improved the above mentioned implementations and adopted them to be able to sort input sequences of arbitrary length. We compared algorithms on six different input distributions, which consist of 32-bit numbers, 32-bit key-value pairs, 64-bit numbers and 64-bit key-value pairs. The results show that radix sort is the fastest sequential sorting algorithm, whereas radix sort and merge sort are the fastest parallel algorithms (depending on the input distribution). With parallel implementations we achieved speedups of up to 157-times in comparison to sequential implementations. vzporedni algoritmi primerjava algoritmov urejanje podatkov grafična kartica CUDA parallel algorithms algorithm comparison sorting graphics card CUDA true false false Slovenski jezik Angleški jezik Magistrsko delo/naloga 2015-07-07 09:55:00 2015-07-07 09:55:01 2022-08-01 11:18:19 0000-00-00 00:00:00 2015 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 1970-01-01 14083 Bozidar_Darko_-_Vzporedni_algoritmi_za_urejanje_podatkov.pdf Bozidar_Darko_-_Vzporedni_algoritmi_za_urejanje_podatkov.pdf 1 8D6AE1474BBFDEC9CC368B441FC20F89 39f36491ef1ab262cb4f7bd68b571c9cc88f439de5fbc03df607f639a85cc79c 54f89fcc-a1ad-11eb-a523-00155dcfd717 20.500.12556/rul/60dd5ee9-fea6-415b-8140-8a035187b64e https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=30872 Fakulteta za računalništvo in informatiko 0 0 0