Refereed International Conference Publications

Matrix Pattern-aware Partitioning and Auto-tuning Space Pruning for Graph Processing on GPU [abstract]
Shinnung Jeong and Hanjun Kim
The 9th International Conference On Consumer Electronics Asia (ICCE-ASIA), November 2024.

Auto-tuning for graph processing on GPU enables efficient processing for large real-world graphs. Existing auto-tuners find optimal combinations of optimization options such as schedule, storage format, and graph traverse method by iterative search. However, while using graph partitioning, which can play a critical role in improving the performance of topology-driven applications traversing all the edges, finding optimal options for each graph partition often induces massive tuning space. Therefore, existing works use the same options for each graph partition, even though each partition often has different graph characteristics. To reduce the tuning space and improve processing performance with graph partitioning, this work suggests a Matrix pattern-aware partitioning and auto-tuning space pruning algorithm for topology-driven applications. We observe that matrix patterns, such as dense diagonal and line patterns, can be a clue for finding optimal combinations. Therefore, this work detaches diagonals as different partitions and prunes tuning options by partition characteristics such as density and degree skewness reflecting the line patterns. Through this approach, We show a 20.3% geomean speedup compared to applying the same tuning space across the entire graph partition. To find the optimal tuning options for each partition, we execute only 27% tuning options compared to performing all tuning options for each partition.