A naive implementation of Topological Sort on GPU: A comparative study between CPU and GPU performance
Independent thesis Basic level (degree of Bachelor), 10 credits / 15 HE creditsStudent thesisAlternative title
En naiv implementation av topologisk sortering på GPU : En jämförande studie mellan CPU och GPU prestanda (Swedish)
Topological sorting is a graph problem encountered in various different areas in computer science. Many graph problems have benefited from execution on a GPU rather than a CPU due to the GPU's capability for parallelism. The purpose of this report is to determine if topological sorting may benefit from a naive implementation on the GPU compared to the CPU. This is accomplished by constructing a parallel implementation using the CUDA platform by NVIDIA for GPGPU programing. The runtime of this implementation running on several different graphs is compared to a sequential implementation in C running on the CPU. The results indicate that the GPU algorithm only works beneficially on large, shallow graphs.
Place, publisher, year, edition, pages
IdentifiersURN: urn:nbn:se:kth:diva-186417OAI: oai:DiVA.org:kth-186417DiVA: diva2:927255