Lock-Free Triangle Counting on GPU
- 21 November 2024
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. 74 (3) , 1040-1052
Abstract
Finding the triangles of large scale graphs is a fundamental graph mining task in many applications, such as motif detection, microscopic evolution, and link prediction. The recent works on triangle counting can be classified into merge-based or binary search-based paradigms. The merge-based triangle counting paradigm locates the triangles using the set intersection operation, which suffers from the random memory access problem. The binary search-based triangle counting paradigm sets the neighbors of the source vertex of an edge as the lookup array and searches the neighbors of the destination vertex. There are lots of expensive lock operations needed in the binary search-based paradigm, which leads to low thread efficiency. In this paper, we aim to improve the triangle counting efficiency on GPU by designing a lock-free policy named Skiff to implement a hash-based triangle counting algorithm. In Skiff, we first design a hash trie data layout to meet the coalesced memory access model and then propose a lock-free policy to reduce the conflicts of the hash trie. In addition, we use a level array to manage the index of the hash trie to make sure the nodes of the hash trie can be quickly located. Furthermore, we implement a CTA thread organization model to reduce the load imbalance of the real-world graphs. We conducted extensive experiments on NVIDIA GPUs to show the performance of Skiff. The results show that Skiff can achieve a good system performance improvement than the state-of-the-art (SOTA) works.Keywords
Funding Information
- National Key Research and Development Program of China (2023YFC2705700)
- National Natural Science Foundation of China (62225113, 62372333)
- Fundamental Research Funds for the Central Universities (2042023kf0135)
- Key Research and Development Program of Hubei Province (2024BAB044, 2023BAB078)
- Project Funded by China Postdoctoral Science Foundation (2022M722459)
- Knowledge Innovation Program of Wuhan - Basic Research (2023010201010063)
This publication has 40 references indexed in Scilit:
- Sliding window-based approximate triangle counting with bounded memory usageThe VLDB Journal, 2023
- Parallel Overlapping Community Detection Algorithm on GPUIEEE Transactions on Big Data, 2022
- Fast Triangle Counting on GPU2019
- TriCore: Parallel Triangle Counting on GPUs2018
- Mermaid: Integrating Vertex-Centric with Edge-Centric for Real-World Graph Processing2017
- CoreScope: Graph Mining Using k-Core Analysis — Patterns, Anomalies and Algorithms2016
- Scalable SIMD-Efficient Graph Processing on GPUs2015
- Fast Triangle Counting on the GPU2014
- An Efficient GPU General Sparse Matrix-Matrix Multiplication for Irregular Data2014
- Abstract: Parallel Algorithms for Counting Triangles and Computing Clustering Coefficients2012