Triangle Counting with A Multi-Core Computer
- Resource Type
- Conference
- Authors
- Donato, Evan; Ouyang, Ming; Peguero-Isalguez, Cristian
- Source
- 2018 IEEE High Performance extreme Computing Conference (HPEC) High Performance extreme Computing Conference (HPEC), 2018 IEEE. :1-7 Sep, 2018
- Subject
- Communication, Networking and Broadcast Technologies
Computing and Processing
Sorting
Sparse matrices
Arrays
Runtime
Graphics processing units
Matrix decomposition
graph
parallel computation
2-core
triangle
- Language
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.