TRUST: Triangle Counting Reloaded on GPUs
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , , , , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2021
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866912981749596160 |
|---|---|
| author | Pandey, Santosh Wang, Zhibin Zhong, Sheng Tian, Chen Zheng, Bolong Li, Xiaoye Li, Lingda Hoisie, Adolfy Ding, Caiwen Li, Dong Liu, Hang |
| author_facet | Pandey, Santosh Wang, Zhibin Zhong, Sheng Tian, Chen Zheng, Bolong Li, Xiaoye Li, Lingda Hoisie, Adolfy Ding, Caiwen Li, Dong Liu, Hang |
| contents | 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 1,000 GPUswith sustained scalability. In this work, we present TRUST which performs triangle counting with the hash operation and vertex-centric mechanism at the core. To the best of our knowledge, TRUSTis the first work that achieves over one trillion Traversed Edges Per Second (TEPS) rate for triangle counting. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2103_08053 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | TRUST: Triangle Counting Reloaded on GPUs Pandey, Santosh Wang, Zhibin Zhong, Sheng Tian, Chen Zheng, Bolong Li, Xiaoye Li, Lingda Hoisie, Adolfy Ding, Caiwen Li, Dong Liu, Hang Distributed, Parallel, and Cluster Computing Social and Information Networks 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 1,000 GPUswith sustained scalability. In this work, we present TRUST which performs triangle counting with the hash operation and vertex-centric mechanism at the core. To the best of our knowledge, TRUSTis the first work that achieves over one trillion Traversed Edges Per Second (TEPS) rate for triangle counting. |
| title | TRUST: Triangle Counting Reloaded on GPUs |
| topic | Distributed, Parallel, and Cluster Computing Social and Information Networks |
| url | https://arxiv.org/abs/2103.08053 |