Hanjun Kim  

Professor
School of Electrical and Electronic Engineering, Yonsei University

Ph.D. 2013, Department of Computer Science, Princeton University

Office: Engineering Hall #3-C415
Phone: +82-2-2123-2770
Email: first_name at yonsei.ac.kr
 
 
[Home]   [Curriculum Vitae]   [Publications]   [CoreLab]   [Korean]  

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 CR2 . First, CR2 extracts community-aware subgraphs from a graph by clustering densely-connected vertices together. For the community-aware subgraphs, CR2 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, CR2 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 CR2 with four commonly used graph algorithms and shows that CR2 achieves 1.53 times performance speedup while using 32.1% less memory on the geomean average compared to the state-of-the-art techniques.