Triangle Counting with A Multi-Core Computer
Triangle Counting with A Multi-Core Computer
复制标题
使用多核计算机进行三角形计数
DOI：
10.1109/hpec.2018.8547540
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Cristian Peguero
中科院分区：
文献类型：
--
作者：
Evan Donato;Ming Ouyang;Cristian Peguero
用于计算稀疏图中三角形数量的前向算法在实践中速度很快。本文研究如何准备数据和数据结构以在双路计算机上实现该算法。具体而言，设计了数据结构以提高前向算法的缓存效率，并设计了顶点排序期间的平局方案以增加对数据结构的顺序访问。图形挑战赛为研究人员提供了一组数据集，以比较其实现的性能。性能指标包括边率（图中的边数除以运行时间）和三角形率（三角形数量除以运行时间）。其中最高边缘速率为每秒 14.06 亿个边缘，最高三角形速率为每秒 34.95 亿个三角形。
The forward algorithm for counting the number of triangles in a sparse graph is fast in practice. This article studies how to prepare data and data structures for implementing the algorithm on a two-socket computer. Specifically, a data structure is designed to increase cache efficiency for the forward algorithm, and a scheme for tiebreaking during the sorting of vertices is designed to increase sequential access to the data structure. The Graph Challenge provides a collection of data sets for researchers to compare the performance of their implementations. The performance metrics include the edge rate (the number of edges in the graph divided by runtime) and the triangle rate (the number of triangles divided by runtime). Herein the highest edge rate achieved is 1.406 billion edges per second, and the highest triangle rate is 3.495 billion triangles per second.