Solving All-pairs Shortest Path Problem on a Hybrid CPU-GPU Platform

U ovom diplomskom radu definirani su osnovni pojmovi teorije grafova kao baza za problem najkraćeg puta u grafu. Opisane su varijante tog problema, te način reprezentacije grafova u računalu, a potom je detaljno analiziran Floyd-Warshall algoritam za rješavanje problema najkraćih putova među svim parovima vrhova. Definirano je dinamičko programiranje obzirom da je Floyd-Warshall algoritam primjer istog. Nakon toga, detaljno je analizirana CUDA platforma za hibridno CPU-GPU računarstvo - njena arhitektura, njene prednosti i mane, a obzirom da se radi o platformi za paralelno računarstvo dana je i povijest istog. Temeljem svih zaključaka, implementirane su tri verzije Floyd-Warshall algoritma: jednostavna C++ implementacija algoritma koja je analogon danom algoritmu pisanom u pseudojeziku, jednostavna CUDA implementacija koja je iskoristila prednosti arhitekture grafičke kartice, te napredna CUDA implementacija koja je na algoritamskoj razini dodatno paralelizirala Floyd-Warshall algoritam. Na kraju, izloženi su eksperimentalni rezultati sve tri implementacije na grafovima raznih veličina i razne gustoće.At the beginning of this thesis some elementary terms from graph theory are defined as a foundation for the shortest path problem. A few varieties of the aforementioned problem are described, as well as the method of representing graphs in computer memory. After that, Floyd-Warshall algorithm for all-pairs shortest-path problem is analized in detail. Dynamic programming is also defined as Floyd-Warshall algorithm is a prime example of such a method. Additionally, CUDA platform for hybrid CPU-GPU computing is analized - its architecture, its advantages and disadvantages, but also, since it is a parallel computing platform, the history of parallel computing is given. Based on all the conclusions, three versions of Floyd-Warshall algorithm have been implemented: a simple C++ implementation of the algorithm which is analogous to the given pseudocode, a simple CUDA implementation which used the advantages of the graphics card architecture and an advanced (blocked) CUDA implementation which further made use of the Floyd-Warshalls algorithm parallel nature. At the end, the experimental results of all three implementations on different sized graphs and graphs of various densities have been laid out