PICO: Accelerating All k-Core Paradigms on GPU
Open Access
- 3 August 2024
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 221-222
Abstract
Core decomposition is a well-established graph mining problem that involves a widely-used subgraph model k-core in network analysis. Solutions to this problem have been developed using the Peel and Index paradigms. However, existing studies have not effectively harnessed GPU performance to expedite core decomposition, despite the growing need for enhanced performance. This paper introduces an efficient GPU acceleration framework, PICO, for both the Peel and Index paradigms of k-core decomposition. We propose a Peel-based algorithm, named PeelOne, which reduces the frontiers searching cost and redundant memory footprint of the frontiers by virtual small graph transformation and kernel fusion. Moreover, we design a GPU-friendly hybrid frontier queues architecture to balance the performance and the memory usage and quickly handle any overflow of the queues. We also propose an Index-based algorithm, named HistoCore, which addresses the issue of extensive redundant computations across both vertices and edges. Extensive experiments on NVIDIA RTX 3090 GPU show that PeelOne outperforms the SOTA Peel-based algorithm by 1.4 × ∼3.5 × speedup, and HistoCore outperforms the existing Index-based algorithm by 9.4 × ∼26.3 × speedup.Keywords
All Related Versions
Funding Information
- National Natural Science Foundation of China (62372333)
- National Key Research and Development Program of China (2023YFC2705700)
This publication has 4 references indexed in Scilit: