Refereed International Conference Publications

CR2: Community-aware Compressed Regular Representation for Graph Processing on a GPU [abstract] (ACM)
Shinnung Jeong, Sungjun Cho, Yongwoo Lee, Hyunjun Park, Seonyeong Heo, Gwangsun Kim, Youngsok Kim, and Hanjun Kim
Proceedings of the 53rd International Conference on Parallel Processing (ICPP), August 2024.

Thanks to its massive parallel resources, a GPU is a promising platform for graph processing. However, the increasing size and skewed characteristics of the real-world graphs limit the performance improvement. Prior work proposes locality-enhancing graph transformations and load balancing techniques to improve performance, but they still suffer from excessive memory usage and inefficient parallel resource utilization because their graph representations are not fully tailored for a GPU. To efficiently utilize the GPU resource with less memory, this work proposes a new graph representation, called CR² . First, CR² extracts community-aware subgraphs from a graph by clustering densely-connected vertices together. For the community-aware subgraphs, CR² decomposes a vertex ID into a cluster ID and a local ID and represents each vertex only with the local ID, thus reducing memory usage. Second, CR² additionally partitions the graph into multiple degree-ordered subgraphs in which all the vertices have the same regularized number of edges, thus making parallel workload balanced across GPU warps. This work evaluates CR² with four commonly used graph algorithms and shows that CR² achieves 1.53 times performance speedup while using 32.1% less memory on the geomean average compared to the state-of-the-art techniques.