An automated framework for concurrent graph processing on GPU

GPUs have become the bleeding edge in high-performance systems used for artificial intelligence and scientific computations. Running parallel jobs and algorithms on GPUs yields results that are orders of magnitude faster than running the same jobs on CPUs that employ fewer cores. A significant body of computational tasks incorporates graph traversals and computations associated with traversal of large graphs. These tasks are either graph traversal tasks in nature or are simplified or transformed into graph traversal tasks. Kernel fusion has been proposed in several bodies of research as a means of fusing computation cores (kernels) in parallel jobs so that the performance can be optimized. Specifically, kernel fusion is used to fuse accesses to same graph nodes and corresponding regions of memory by multiple parallel jobs so that memory caches are more efficiently utilized, resulting in performance improvements. As kernel fusion's fundamental idea is sharing resource access to increase utilization by multiple jobs, it is even better suited for GPUs that run hundreds of jobs in parallel than CPUs that run a few jobs in parallel. However, kernel fusion is a computationally expensive operation that incorporates control flow changes and manipulation of the order of execution for computational jobs. As such, kernel fusion is harder to utilize on GPUs compared to CPUs. This work introduces a streamlined kernel fusion framework for concurrent graph processing on GPUs. The framework enables definition and implementation of graph jobs that can be executed in parallel in GPUs, and are automatically fused by the kernel fusion algorithm implemented in the framework, to achieve better performance. The framework also introduces novel data handling structures, as well as a meta-compiler that enables static polymorphism for running multiple different jobs as a job queue on the GPU, without performance hits that are associated with typical polymorphism. The framework is then extensively evaluated by defining four common graph jobs (BFS, SSSP, PageRank, Label Propagation) and running up to 200 parallel instances of these jobs in homogeneous and heterogeneous manners, with and without kernel fusion. The evaluations show that kernel fusion provides about 5% to 10% performance improvement when job parallelism is reasonably high (i.e., more than 10 parallel jobs).