Trust: Triangle Counting Reloaded on GPUs
Trust: Triangle Counting Reloaded on GPUs
复制标题
信任：在 GPU 上重新加载三角形计数
DOI：
10.1109/tpds.2021.3064892
复制
发表时间：
2021-11-01
影响因子：
5.3
通讯作者：
Liu, Hang
中科院分区：
文献类型：
--
作者：
Pandey, Santosh;Wang, Zhibin;Liu, Hang
三角形计数是各种图形应用的构建块。传统观点认为，i) 散列不适合三角形计数，ii) 以边为中心的三角形计数胜过以顶点为中心的设计，以及 iii) 无通信和工作负载平衡的图分区是三角形计数的巨大挑战。相反，我们主张i）散列可以帮助图形处理单元（GPU）上可扩展三角形计数的关键操作，即列表交集和图分区，ii）以顶点为中心的设计减少散列表构建成本和内存消耗，这在GPU上是有限的。此外，iii) 我们利用图形和工作负载协作以及基于散列的 2D 分区来扩展以顶点为中心的三角形计数超过 1000 个 GPU，并具有持续的可扩展性。在本文中，我们介绍了 Trust，它以哈希运算和以顶点为中心的机制为核心执行三角形计数。据我们所知，Trust 是第一个在三角形计数方面实现每秒超过一万亿次遍历边数 (TEPS) 的工作。
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 triangle counting with the hash operation and vertex-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.