A naive implementation of Topological Sort on GPU : A comparative study between CPU and GPU performance

Abstract: 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.