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.
|Original language||English (US)|
|Title of host publication||2017 IEEE High Performance Extreme Computing Conference, HPEC 2017|
|Publisher||Institute of Electrical and Electronics Engineers Inc.|
|State||Published - Oct 30 2017|
|Event||2017 IEEE High Performance Extreme Computing Conference, HPEC 2017 - Waltham, United States|
Duration: Sep 12 2017 → Sep 14 2017
|Name||2017 IEEE High Performance Extreme Computing Conference, HPEC 2017|
|Other||2017 IEEE High Performance Extreme Computing Conference, HPEC 2017|
|Period||9/12/17 → 9/14/17|
Bibliographical noteFunding Information:
This work was supported in part by NSF (IIS-0905220, OCI-1048018, CNS-1162405, IIS-1247632, IIP-1414153, IIS-1447788), Army Research Office (W911NF-14-1-0316), Intel Software and Services Group, and the Digital Technology Center at the University of Minnesota. Access to research and computing facilities was provided by the Digital Technology Center and the Minnesota Supercomputing Institute.