Exploring Optimizations on Shared-memory Platforms for Parallel Triangle Counting Algorithms
| Ancy Sarah Tom, Narayanan Sundaram, Nesreen K. Ahmed, Shaden Smith, Stijn Eyerman, Midhunchandra Kodiyath, Ibrahim Hur, Fabrizio Petrini, and George Karypis |
| IEEE High Performance Extreme Computing Conference (HPEC), 2017 |
Download Paper  |
| Abstract The widespread use of graphs to model large scale real-world data brings with it the need for fast graph analytics. In this paper, we explore the problem of triangle counting, a fundamental graph-analytic operation, on shared-memory platforms. Existing triangle counting implementations do not effectively utilize the key characteristics of large sparse graphs for tuning their algorithms for performance. We explore such optimizations and develop faster serial and parallel variants of existing algorithms, which outperform the state-of-the-art on Intel manycore and multicore processors. Our algorithms achieve good strong scaling on many graphs with varying scale and degree distributions. Furthermore, we extend our optimizations to a well-known graph processing framework, GraphMat, and demonstrate their generality. |
| Comments GraphChallenge 2017 Finalist The code is available on GitHub at https://github.com/KarypisLab/TriangleCounting. |
| Research topics: Data mining | Graph mining | Parallel processing |