Trust: Triangle Counting Reloaded on GPUs

Triangle counting is a building block for a wide range of graph applications. Traditional wisdom suggests that i) hashing is not suitable for triangle counting, ii) edge-centric triangle counting beats vertex-centric design, and iii) communication-free and workload balanced graph partitioning is a g...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on parallel and distributed systems 2021-11, Vol.32 (11), p.2646-2660
Main Authors: Pandey, Santosh, Wang, Zhibin, Zhong, Sheng, Tian, Chen, Zheng, Bolong, Li, Xiaoye, Li, Lingda, Hoisie, Adolfy, Ding, Caiwen, Li, Dong, Liu, Hang
Format: Article
Language:English
Subjects:
Arrays
Construction costs
GPGPU
Graph algorithms
Graphics processing units
Instruction sets
MATHEMATICS AND COMPUTING
Message systems
Parallel processing
Partitioning
Partitioning algorithms
Time complexity
Triangle counting
Two dimensional displays
Workload
Workloads
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Triangle counting is a building block for a wide range of graph applications. Traditional wisdom suggests that i) hashing is not suitable for triangle counting, ii) edge-centric triangle counting beats vertex-centric design, and iii) communication-free and workload balanced graph partitioning is a grand challenge for triangle counting. On the contrary, we advocate that i) hashing can help the key operations for scalable triangle counting on Graphics Processing Units (GPUs), i.e., list intersection and graph partitioning, ii) vertex-centric design reduces both hash table construction cost and memory consumption, which is limited on GPUs. In addition, iii) we exploit graph and workload collaborative, and hashing-based 2D partitioning to scale vertex-centric triangle counting over 1000 GPUs with sustained scalability. In this article, we present Trust which performs tr iangle co u nting with the ha s h operation and ver t ex-centric mechanism at the core. To the best of our knowledge, Trust is the first work that achieves over one trillion Traversed Edges Per Second (TEPS) rate for triangle counting.
ISSN:1045-9219
1558-2183
DOI:10.1109/TPDS.2021.3064892