Vzporedni algoritmi za urejanje podatkov

BOŽIDAR, DARKO (author), Dobravec, Tomaž (mentor)

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.

• Language: Slovenian
• Keywords: vzporedni algoritmi, primerjava algoritmov, urejanje podatkov, grafična kartica, CUDA
• Work type: Master's thesis/paper
• Organization: FRI - Faculty of Computer and Information Science
• Year: 2015
• PID: 20.500.12556/RUL-30863
• Publication date in RUL: 07.07.2015

Secondary language

• Language: English
• Title: Comparison of parallel sorting algorithms

Abstract

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.

• Keywords: parallel algorithms, algorithm comparison, sorting, graphics card, CUDA