Implementacija algoritama na grafovima pomoću GPU

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.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