izpis_h1_title_alt

Vzporedni algoritmi za urejanje podatkov
BOŽIDAR, DARKO (Avtor), Dobravec, Tomaž (Mentor) Več o mentorju... Povezava se odpre v novem oknu

.pdfPDF - Predstavitvena datoteka, prenos (4,57 MB)
MD5: 8D6AE1474BBFDEC9CC368B441FC20F89

Izvleček
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.

Jezik:Slovenski jezik
Ključne besede:vzporedni algoritmi, primerjava algoritmov, urejanje podatkov, grafična kartica, CUDA
Vrsta gradiva:Magistrsko delo/naloga (mb22)
Organizacija:FRI - Fakulteta za računalništvo in informatiko
Leto izida:2015
Število ogledov:855
Število prenosov:310
Metapodatki:XML RDF-CHPDL DC-XML DC-RDF
 
Skupna ocena:(0 glasov)
Vaša ocena:Ocenjevanje je dovoljeno samo prijavljenim uporabnikom.
:
Objavi na:AddThis
AddThis uporablja piškotke, za katere potrebujemo vaše privoljenje.
Uredi privoljenje...

Sekundarni jezik

Jezik:Angleški jezik
Naslov:Comparison of parallel sorting algorithms
Izvleček:
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.

Ključne besede:parallel algorithms, algorithm comparison, sorting, graphics card, CUDA

Podobna dela

Podobna dela v RUL:
Podobna dela v drugih slovenskih zbirkah:

Komentarji

Dodaj komentar

Za komentiranje se morate prijaviti.

Komentarji (0)
0 - 0 / 0
 
Ni komentarjev!

Nazaj