Implementacija algoritama na grafovima pomoću GPU

master's thesis

• Author: Loredana Musap
• Mentor: Zvonimir Bujanović (mentor)
• Committee member: Zvonimir Bujanović (predsjednik povjerenstva)
• Committee member: Goranka Nogo (član povjerenstva)
• Committee member: Marko Vrdoljak (član povjerenstva)
• Committee member: Miljenko Huzak (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2016-07-14, Croatia
• Scientific / art field, discipline and subdiscipline: NATURAL SCIENCES; Mathematics

Abstract

U ovom radu se analizira potencijal korištenja visoko paralelnih grafičkih procesora za implementaciju algoritama na grafovima, s naglaskom na Dijkstrin algoritam za nalaženje najkraćih puteva u grafu. Dan je opis tehnologije CUDA tvrtke NVidia, zajedno s pripadnim programskim modelom. Diskutiramo aspekte paralelizacije Dijkstrinog algoritma u okvirima ovog modela na GPU. Provedeni numerički testovi pokazuju značajno ubrzanje u odnosu na klasičnu implementaciju na CPU.

Abstract (english)

n this work we analyze the potential of using a highly parallel graphical processor in order to implement graph algorithms, in particular, Dijkstra's algorithm for finding shortest paths in a graph. We describe the CUDA technology which was introduced by NVidia, together with its programming model. We discuss aspects of parallelizing Dijkstra's algorithm within this GPU framework. Numerical experiments show that this approach achieves significant speedup compared to the classical CPU implementation.

• Keywords: visoko paralelni grafički procesor; algoritmi na grafovima; Dijkstrin algoritam; tehnologija CUDA; GPU
• Keywords (english): highly parallel graphical processor; graph algorithms; Dijkstra's algorithm; CUDA technology; GPU
• Language: croatian
• URN:NBN: urn:nbn:hr:217:615760
• Study programme: Title: Computer Science and Mathematics; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra računarstva i matematike (magistar/magistra računarstva i matematike)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Open access
• Created on: 2019-01-28 08:57:22