Implementation of Kruskal's algorithm on CUDA technologies

Cilj ovog rada je opis implementacije Kruskalovog algoritma primjenom CUDA tehnologije. CUDA je pokrenuta 2007. godine kao platforma za GPGPU (General-Purpose computing on graphics processing units). Isprva kao polazna točka u izvođenju operacija vezanih za sliku, video snimke i video igrice, GPU danas može služiti kao odličan alat za izvođenje operacija druge vrste, tipa numeričkih. Sposobnost paralelizacije daje GPU-u veliku prednost u odnosu na ostale vrste procesora. Pravi izazov paralelizacije primjenom CUDA tehnologije leži u pokušaju implementacije apstraktnih i neregularnih algoritama. Jedan od takvih algoritama je i Kruskalov algoritam. Njegova prirodna proceduralnost i pripadnost grupi pohlepnih algoritama umanjuje šanse za potpunu paralelizaciju, no čak i dosadašnji pokušaji pokazali zavidne rezultate u štednji memorije i brzini izvođenja operacija. Da bi se moglo pristupiti implementaciji, treba znati osnove teorije grafova, arhitekturu GPU-a i osnove programiranja u CUDA okolini. Bez obzira na poteškoće, vrlo vjerojatno se neće odustati od novih pokušaja stvaranja boljeg oblika Kruskalovog algoritma zbog njegove moćne optimizacije