5. High Performance and Scalable Graph Computation on GPUs

High compute power provided by the many-threaded SIMT model of Graphics Processing Units (GPUs) accompanied with the recent advancements in their programmability has allowed expression of massively parallel computations. Graph processing is one of the applications that expose such parallelism, and hence, candidates GPUs as attractive execution platforms. However, irregularities in large real-world graphs makes effective and scalable utilization of symmetric GPU architecture a challenging task. While degree distribution in graphs extracted from real-world origins is usually power law, GPUs demand homogeneous computation patterns on consecutive data elements. This article summarizes recent research advancements to overcome this challenge. We first overview the main concepts in the field of graph processing on GPUs. Then, we introduce novel graph representations that, unlike conventional storage formats, are a better match for GPUs. We then present a GPU-friendly decomposition scheme that provides balanced thread to task assignment and enhances the scalability and the execution performance. Finally, we discuss a set of techniques that allow scaling the computation over multiple GPUs efficiently.