diplomsko delo
Jernej Erker (Author), Tomaž Dobravec (Mentor)

Abstract

Izvedbe hitrega urejanja za CPE in GPE

Keywords

hitro;vzporedno;urejanje;algoritmi;CUDA;računalništvo;univerzitetni študij;diplomske naloge;

Data

Language: Slovenian
Year of publishing:
Typology: 2.11 - Undergraduate Thesis
Organization: UL FRI - Faculty of Computer and Information Science
Publisher: [J. Erker]
UDC: 004.424.5.021(043.2)
COBISS: 9986644 Link will open in a new window
Views: 33
Downloads: 1
Average score: 0 (0 votes)
Metadata: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

Other data

Secondary language: English
Secondary title: Quicksort algorithms for the CPU and GPU
Secondary abstract: Quicksort algorithm was discovered in 1960 and is present for more than half a century, nevertheless it is still very popular and fast. Different versions of the algorithm are being used in standard libraries of a number of programming languages. The algorithm is fairly simple to understand, robust in the sense that it is efficient in most cases and it does not need a lot of resources. It is based on the Divide and Conquer principle which means that we solve the problem by recursively breaking it down into two or more sub-problems, which we solve and combine the solutions to form a solution to the original problem. There were many attempts of improving the algorithm, so there are a lot of different implementations. The main difference between them is the manner in which they partition the elements of the array. NVIDIA Corporation presented the parallel computing platform CUDA in 2006. It makes GPUs accessible for computation like CPUs. Main advantage of executing algorithms on the GPU is the use of massive parallelism. Actually making good use of this parallelism is another thing altogether. The purpose of this thesis is to present different partitioning methods and introduce the consequences of using a different number of pivots or partitioning the array into a different number of sub-arrays. We will review analyses of the time complexities of all the cases and describe the quicksort algorithm, prepared for execution on the GPU. In the end we will compare presented algorithms and state our interpretations of the results.
Secondary keywords: quicksort;parallel;sorting;algorithms;CUDA;computer science;diploma;
File type: application/pdf
Type (COBISS): Undergraduate thesis
Thesis comment: Univ. v Ljubljani, Fak. za računalništvo in informatiko
Pages: 72 str.
ID: 24168168