Mapping of graph problems on GPU architecture – theory and practice


A.S. Kolganov


Last time graphics accelerators (GPUs) GPU are increasingly being used in non-graphical computations. They’re needed because of  their relatively high performance and lower cost. As you know,  the problems on structured grids where the parallelism is easily determined are solved well  on GPUs. But there are problems that require more computing power and use non-structured grids. The examples of such tasks are: Single Shortest Source Path problem (SSSP) – the problem to  find the shortest paths from a given vertex to all the others in a weighted graph, MST (minimum spanning tree) – finding the minimum spanning forest in a graph, BFS (breadth first search) – breadth-first search in the graph, Community detection – finding closely related communities in a graph, and others. These tasks are very often used in various fields of research: a recognition of various objects, computer vision, analysis and building of networks (for example, telephone, electrical, computer, road, etc.), chemistry and biology, and in many other areas.

Key words

GPU, parallel processing of graphs.