Change search
ReferencesLink to record
Permanent link

Direct link
A naive implementation of Topological Sort on GPU: A comparative study between CPU and GPU performance
KTH, School of Computer Science and Communication (CSC).
KTH, School of Computer Science and Communication (CSC).
2016 (English)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)
Abstract [en]

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
National Category
Computer Science
URN: urn:nbn:se:kth:diva-186417OAI: diva2:927255
Available from: 2016-05-18 Created: 2016-05-11 Last updated: 2016-05-18Bibliographically approved

Open Access in DiVA

fulltext(1089 kB)43 downloads
File information
File name FULLTEXT01.pdfFile size 1089 kBChecksum SHA-512
Type fulltextMimetype application/pdf

By organisation
School of Computer Science and Communication (CSC)
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 43 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 26 hits
ReferencesLink to record
Permanent link

Direct link