We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham e-Theses
You are in:

All-Pairs Shortest Path Algorithms Using CUDA

KEMP, JEREMY,MARK (2012) All-Pairs Shortest Path Algorithms Using CUDA. Masters thesis, Durham University.

PDF (Final Masters Thesis.) - Accepted Version


Utilising graph theory is a common activity in computer science. Algorithms that perform computations on large graphs are not always cost effective, requiring supercomputers to achieve results in a practical amount of time. Graphics Processing Units provide a cost effective alternative to supercomputers, allowing parallel algorithms to be executed directly on the Graphics Processing Unit. Several algorithms exist to solve the All-Pairs Shortest Path problem on the Graphics Processing Unit, but it can be difficult to determine whether the claims made are true and verify the results listed. This research asks "Which All-Pairs Shortest Path algorithms solve the All-Pairs Shortest Path problem the fastest, and can the authors' claims be verified?" The results we obtain when answering this question show why it is important to be able to collate existing work, and analyse them on a common platform to observe fair results retrieved from a single system. In this way, the research shows us how effective each algorithm is at performing its task, and suggest when a certain algorithm might be used over another.

Item Type:Thesis (Masters)
Award:Master of Science
Keywords:CUDA;GPGPU;Parallel Computing;Graph Theory
Faculty and Department:Faculty of Science > Engineering and Computing Science, School of (2008-2017)
Thesis Date:2012
Copyright:Copyright of this thesis is held by the author
Deposited On:01 Nov 2012 11:32

Social bookmarking: del.icio.usConnoteaBibSonomyCiteULikeFacebookTwitter