Vzporedni algoritmi za urejanje podatkovBOŽIDAR, DARKO (Avtor) Dobravec, Tomaž (Mentor) vzporedni algoritmiprimerjava algoritmovurejanje podatkovgrafična karticaCUDAV 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.20152015-07-07 09:55:00Magistrsko delo/naloga30863sl