High-Performance Triangle Counting on GPUs
High-Performance Triangle Counting on GPUs
复制标题
GPU 上的高性能三角形计数
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
H. H. Huang
中科院分区：
文献类型：
--
作者：
Yang Hu;Hang Liu;H. H. Huang
计算社交网络中的三角形是理解社交网络的主要步骤。例如，一个包含大量三角形的图被认为是一个具有高度信任度的“紧密联系的社区”，因为在这种情况下，一个顶点的所有朋友(邻居)也是彼此的朋友(连接)。这项工作的重点是使用图形处理单元(GPU)来加速三角形计算。为了容纳大型图形，最先进的基于GPU的三角形计数项目-TriCore-只需将整个图形存储在二级存储中，即可实现免通信的多GPU三角形计数。我们的主要观察是，每个现代的GPU服务器(表I)经常安装多个GPU，这很容易使磁盘带宽超负荷。因此，本文提出了一种新的负载均衡设计，对图和负载进行分区，以便在CPU内存中缓冲每个分区的数据，以加快数据供应。总而言之，据我们所知，这项工作是第一个将三角形计数速度提高到每秒109条遍历边(TEPs)的项目，也是第一个为具有超过100亿条边的图实现108TEPS的项目。
Counting triangles in a network is a primary step toward making sense of social networks. For instance, a graph with a large number of triangles is regarded as a “tightly knit community” with high degree of trust, because in this case all the friends (neighbors) of one vertex are also friends (connected) to each other. This work focuses on using Graphics Processing Units (GPUs) to accelerate triangle counting. To accommodate large graphs, the stat-of-the-art GPU-based triangle counting project-TriCore-simply stores the entire graph in the secondary storage to achieve communication free multi-GPU triangle counting. Our key observation is that each modern GPU server (Table I) often installs multiple GPUs which can easily overwhelm the disk bandwidth. Therefore, this paper introduces a new design for workload balancing to partition the graph and the workload in order to buffer each partitioned data in the CPU memory for faster data provisioning. Taken together, this work is the first, to the best of our knowledge, to advance the rate of triangle counting beyond 109 traversed edges per second (TEPS), as well as the first project that achieves > 108TEPS for graphs with more than ten billion edges.