UM
Residential Collegefalse
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 Name2024 IEEE International Parallel and Distributed Processing Symposium (IPDPS)
Source PublicationProceedings - 2024 IEEE International Parallel and Distributed Processing Symposium, IPDPS 2024
Pages1070-1081
Conference DateMAY 27-31, 2024
Conference PlaceSan Francisco, CA
CountryUSA
PublisherInstitute 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.

KeywordGpu Triangle Counting
DOI10.1109/IPDPS57955.2024.00099
URLView the original
Indexed ByCPCI-S
Language英語English
WOS Research AreaComputer Science
WOS SubjectComputer Science, Software Engineering ; Computer Science, Theory & Methods
WOS IDWOS:001270389600032
Scopus ID2-s2.0-85198901737
Fulltext Access
Citation statistics
Document TypeConference paper
CollectionUniversity of Macau
Corresponding AuthorXu, Zichen
Affiliation1.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.
Related Services
Recommend this item
Bookmark
Usage statistics
Export to Endnote
Google Scholar
Similar articles in Google Scholar
[Li, Jiangbo]'s Articles
[Xu, Zichen]'s Articles
[Pham, Minh]'s Articles
Baidu academic
Similar articles in Baidu academic
[Li, Jiangbo]'s Articles
[Xu, Zichen]'s Articles
[Pham, Minh]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[Li, Jiangbo]'s Articles
[Xu, Zichen]'s Articles
[Pham, Minh]'s Articles
Terms of Use
No data!
Social Bookmark/Share
All comments (0)
No comment.
 

Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.