prikaz prve stranice dokumenta Pronalaženje najkraćih putova u grafu korištenjem hibridne CPU-GPU platforme
  Preuzmi
PDF 7.12 MB
diplomski rad
Pronalaženje najkraćih putova u grafu korištenjem hibridne CPU-GPU platforme
2017. urn:nbn:hr:126:948332
Karaula, Mislav
Sveučilište Josipa Jurja Strossmayera u Osijeku
Odjel za matematiku
Zavod za primijenjenu matematiku i računarstvo
Katedra za računarstvo i strojno učenje

Citirajte ovaj rad

Karaula, M. (2017). Pronalaženje najkraćih putova u grafu korištenjem hibridne CPU-GPU platforme (Diplomski rad). Osijek: Sveučilište Josipa Jurja Strossmayera u Osijeku, Odjel za matematiku. Preuzeto s https://urn.nsk.hr/urn:nbn:hr:126:948332

Karaula, Mislav. "Pronalaženje najkraćih putova u grafu korištenjem hibridne CPU-GPU platforme." Diplomski rad, Sveučilište Josipa Jurja Strossmayera u Osijeku, Odjel za matematiku, 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." Diplomski rad, Sveučilište Josipa Jurja Strossmayera u Osijeku, Odjel za matematiku, 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', Diplomski rad, Sveučilište Josipa Jurja Strossmayera u Osijeku, Odjel za matematiku, citirano: 09.11.2024., https://urn.nsk.hr/urn:nbn:hr:126:948332

Karaula M. Pronalaženje najkraćih putova u grafu korištenjem hibridne CPU-GPU platforme [Diplomski rad]. Osijek: Sveučilište Josipa Jurja Strossmayera u Osijeku, Odjel za matematiku; 2017 [pristupljeno 09.11.2024.] Dostupno na: https://urn.nsk.hr/urn:nbn:hr:126:948332

M. Karaula, "Pronalaženje najkraćih putova u grafu korištenjem hibridne CPU-GPU platforme", Diplomski rad, Sveučilište Josipa Jurja Strossmayera u Osijeku, Odjel za matematiku, Osijek, 2017. Dostupno na: https://urn.nsk.hr/urn:nbn:hr:126:948332

Za citiranje koristite ovu mrežnu adresu: https://urn.nsk.hr/urn:nbn:hr:126:948332
Prijavite se u repozitorij kako biste mogli spremiti objekt u svoju listu.
Podaci o radu
NaslovPronalaženje najkraćih putova u grafu korištenjem hibridne CPU-GPU platforme
Naslov (engleski)Solving All-pairs Shortest Path Problem on a Hybrid CPU-GPU Platform
AutorMislav Karaula
MentorDomagoj Ševerdija (mentor)
Član povjerenstvaDomagoj Matijević (predsjednik povjerenstva)
Član povjerenstvaDomagoj Ševerdija (član povjerenstva)
Član povjerenstvaSlobodan Jelić (član povjerenstva)
Ustanova koja je dodijelila
akademski / stručni stupanj		Sveučilište Josipa Jurja Strossmayera u Osijeku
Odjel za matematiku
(Zavod za primijenjenu matematiku i računarstvo)
(Katedra za računarstvo i strojno učenje)
Osijek
Datum i država obrane2017-01-20, Hrvatska
Znanstveno / umjetničko
područje, polje i grana		PRIRODNE ZNANOSTI
Matematika
Matematička logika i računarstvo
Sažetak
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.
Sažetak (engleski)
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.
Ključne riječi
Ključne riječi (engleski)
Jezikhrvatski
URN:NBNurn:nbn:hr:126:948332
Studijski programNaziv: Matematika; smjerovi: Financijska matematika i statistika, Matematika i računarstvo, Industrijska i primijenjena matematika
Smjer: Matematika i računarstvo
Vrsta studija: sveučilišni
Stupanj studija: diplomski
Akademski / stručni naziv: magistar/magistra matematike (mag.math.)
Vrsta resursaTekst
Način izrade datotekeIzvorno digitalna
Prava pristupaOtvoreni pristup
Uvjeti korištenjaIkona licence Zaštićeno autorskim pravom.
Datum i vrijeme pohrane2017-02-17 06:52:39