Characterization of Sparsity-aware Parallelization of Jaccard Similarity in Graph Datasets

The unpredictability of real-world graph workloads complicates the realization of high-performance graph analytics on the GPU. For example, variance in sparsity and neighbor commonality can dramatically alter computing costs and memory-access patterns, even within different regions of the same graph.In this paper, we investigate Jaccard similarity, a metric that measures the similarity of two sets. We compare and contrast the performance an edge-centric parallelization of Jaccard similarity with respect to the vertex-centric approach from NVIDIA’s cuGraph library. We then characterize the impact of graph metrics (e.g., average degree, maximum degree, Gini index) on the performance of edge-centric and vertex-centric kernels. By combining the above graph metrics with performance metrics (e.g., bandwidth utilization and thread activity), we deliver insight into why certain graphs benefit from edge-centric over vertex-centric parallelization, while other graphs benefit conversely. Finally, based on these results, we make a case for sparsity-aware parallelization, i.e., choosing between an edge-centric or a vertex-centric parallelized kernel, for improved performance by showing that selecting the best-performing parallelized kernel can deliver a geometric mean speedup of 3.2× over the reference cuGraph kernel on an NVIDIA A100 GPU.