Residential College | false |
Status | 已發表Published |
A Comparative Study of Intersection-Based Triangle Counting Algorithms on GPUs | |
Li, Jiangbo1,2; Xu, Zichen1,2; Pham, Minh3; Tu, Yicheng2,3; Zhou, Qihe4 | |
2024-07 | |
Conference Name | 2024 IEEE International Parallel and Distributed Processing Symposium (IPDPS) |
Source Publication | Proceedings - 2024 IEEE International Parallel and Distributed Processing Symposium, IPDPS 2024 |
Pages | 1070-1081 |
Conference Date | MAY 27-31, 2024 |
Conference Place | San Francisco, CA |
Country | USA |
Publisher | Institute of Electrical and Electronics Engineers Inc. |
Abstract | Counting triangles in large graphs, being a crucial problem in graph computing, has attracted significant attention from research communities. There is a large body of work dedicated to algorithmic design and efficient implementation on parallel platforms such as GPUs. Among them, the intersection-based triangle counting algorithm is found to be the most efficient approach and a few GPU implementations have been proposed following this algorithm. However, there remains a gap in understanding how these algorithms perform when confronted with diverse real-world graph datasets. It is a well-established fact that the performance of GPU code is heavily influenced by data characteristics, including graph size and node degree, often leading to issues such as workload imbalances and inefficient memory access. The goal of this study is to systematically evaluate the performance and analyze the behavior of eight recently published intersection-based triangle counting implementations. For that, we developed a unified testing framework that facilitates fast performance assessment of any triangle counting algorithm. Our experiments show that the TRUST algorithm outperforms competitors in most cases. To our surprise, the Polak algorithm, with a simple design, has displayed commendable performance across the board. Notably, it even surpasses the TRUST algorithm when processing small datasets. We conducted an in-depth analysis on the resource consumption patterns of these implementations in relation to their performance and identified key factors that contributed to their behaviors. Based on insights gained from such analysis, we proposed a novel algorithm named GroupTC that delivers outstanding performance under all types of datasets. |
Keyword | Gpu Triangle Counting |
DOI | 10.1109/IPDPS57955.2024.00099 |
URL | View the original |
Indexed By | CPCI-S |
Language | 英語English |
WOS Research Area | Computer Science |
WOS Subject | Computer Science, Software Engineering ; Computer Science, Theory & Methods |
WOS ID | WOS:001270389600032 |
Scopus ID | 2-s2.0-85198901737 |
Fulltext Access | |
Citation statistics | |
Document Type | Conference paper |
Collection | University of Macau |
Corresponding Author | Xu, Zichen |
Affiliation | 1.Nanchang University, School of Mcs, Nanchang, China 2.Jiaxing Neofelis Technologies Co. Ltd., Jiaxing, China 3.University of South Florida, Depart. of Cse, Tampa, United States 4.University of Macau, Faculty of Data Science City, Macao |
Recommended Citation GB/T 7714 | Li, Jiangbo,Xu, Zichen,Pham, Minh,et al. A Comparative Study of Intersection-Based Triangle Counting Algorithms on GPUs[C]:Institute of Electrical and Electronics Engineers Inc., 2024, 1070-1081. |
APA | Li, Jiangbo., Xu, Zichen., Pham, Minh., Tu, Yicheng., & Zhou, Qihe (2024). A Comparative Study of Intersection-Based Triangle Counting Algorithms on GPUs. Proceedings - 2024 IEEE International Parallel and Distributed Processing Symposium, IPDPS 2024, 1070-1081. |
Files in This Item: | There are no files associated with this item. |
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.
Edit Comment