New Approach for Graph Algorithms on GPU using CUDA
Gunjan Singla, Amrita Tiwari, Dhirendra Pratap Singh · 2013
Large Graph algorithms like Breadth-First Search (BFS), Depth-First Search(DFS), shortest path algorithms etc. used frequently in various engineering and real world applications that demand execution of these algorithms in large graphs having millions of edges and sequential implementation of these algorithms takes large amount of time. Today’s Graphics Processing Units (GPUs) provide a platform to implement such applications with high computation power and massively multithreaded architecture at low price. In this paper, we present parallel implementations of two basic graph algorithms breadth-first search and Dijkstra’s single source shortest path algorithm by using a new approach called edge based kernel execution on GPU. The performance analysis of parallel implementation over the serial execution gives a good speed-up.