prikaz prve stranice dokumenta Pronalaženje najkraćih putova u grafu korištenjem hibridne CPU-GPU platforme
  Download
PDF 7.12 MB
master's thesis
Pronalaženje najkraćih putova u grafu korištenjem hibridne CPU-GPU platforme
Osijek: Josip Juraj Strossmayer University of Osijek, Department of Mathematics, 2017. urn:nbn:hr:126:948332
Karaula, Mislav
Josip Juraj Strossmayer University of Osijek
Department of Mathematics
Chair of Applied Mathematics and Computer Science
Computer Science and Machine Learning Research Group

Institutional repository: Repository of School of Applied Mathematics and Informatics

Cite this document

Karaula, M. (2017). Pronalaženje najkraćih putova u grafu korištenjem hibridne CPU-GPU platforme (Master's thesis). Osijek: Josip Juraj Strossmayer University of Osijek, Department of Mathematics. Retrieved from https://urn.nsk.hr/urn:nbn:hr:126:948332

Karaula, Mislav. "Pronalaženje najkraćih putova u grafu korištenjem hibridne CPU-GPU platforme." Master's thesis, Josip Juraj Strossmayer University of Osijek, Department of Mathematics, 2017. https://urn.nsk.hr/urn:nbn:hr:126:948332

Karaula, Mislav. "Pronalaženje najkraćih putova u grafu korištenjem hibridne CPU-GPU platforme." Master's thesis, Josip Juraj Strossmayer University of Osijek, Department of Mathematics, 2017. https://urn.nsk.hr/urn:nbn:hr:126:948332

Karaula, M. (2017). 'Pronalaženje najkraćih putova u grafu korištenjem hibridne CPU-GPU platforme', Master's thesis, Josip Juraj Strossmayer University of Osijek, Department of Mathematics, accessed 25 January 2025, https://urn.nsk.hr/urn:nbn:hr:126:948332

Karaula M. Pronalaženje najkraćih putova u grafu korištenjem hibridne CPU-GPU platforme [Master's thesis]. Osijek: Josip Juraj Strossmayer University of Osijek, Department of Mathematics; 2017 [cited 2025 January 25] Available at: https://urn.nsk.hr/urn:nbn:hr:126:948332

M. Karaula, "Pronalaženje najkraćih putova u grafu korištenjem hibridne CPU-GPU platforme", Master's thesis, Josip Juraj Strossmayer University of Osijek, Department of Mathematics, Osijek, 2017. Available at: https://urn.nsk.hr/urn:nbn:hr:126:948332

Metadata
TitlePronalaženje najkraćih putova u grafu korištenjem hibridne CPU-GPU platforme
Title (english)Solving All-pairs Shortest Path Problem on a Hybrid CPU-GPU Platform
AuthorMislav Karaula
MentorDomagoj Ševerdija (mentor)
Committee memberDomagoj Matijević (predsjednik povjerenstva)
Committee memberDomagoj Ševerdija (član povjerenstva)
Committee memberSlobodan Jelić (član povjerenstva)
GranterJosip Juraj Strossmayer University of Osijek
Department of Mathematics
(Chair of Applied Mathematics and Computer Science)
(Computer Science and Machine Learning Research Group)
Osijek
Defense date and country2017-01-20, Croatia
Scientific / art field,
discipline and subdiscipline		NATURAL SCIENCES
Mathematics
Mathematical Logic and Accounting
Abstract
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.
Abstract (english)
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.
Keywords
Keywords (english)
Languagecroatian
URN:NBNurn:nbn:hr:126:948332
Study programmeTitle: Mathematics; specializations in: Financial and Statistical Mathematics, Mathematics and Computer Science, Industrial and Applied Mathematics
Course: Mathematics and Computer Science
Study programme type: university
Study level: graduate
Academic / professional title: magistar/magistra matematike (magistar/magistra matematike)
Type of resourceText
File originBorn digital
Access conditionsOpen access
Terms of useLicence In copyright icon
Created on2017-02-17 06:52:39