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, George Karypis

Research output: Chapter in Book/Report/Conference proceedingConference contribution

16 Scopus citations

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.

Original languageEnglish (US)
Title of host publication2017 IEEE High Performance Extreme Computing Conference, HPEC 2017
PublisherInstitute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)9781538634721
DOIs
StatePublished - Oct 30 2017
Event2017 IEEE High Performance Extreme Computing Conference, HPEC 2017 - Waltham, United States
Duration: Sep 12 2017Sep 14 2017

Publication series

Name2017 IEEE High Performance Extreme Computing Conference, HPEC 2017

Other

Other2017 IEEE High Performance Extreme Computing Conference, HPEC 2017
CountryUnited States
CityWaltham
Period9/12/179/14/17

Fingerprint Dive into the research topics of 'Exploring optimizations on shared-memory platforms for parallel triangle counting algorithms'. Together they form a unique fingerprint.

  • Cite this

    Tom, A. S., Sundaram, N., Ahmed, N. K., Smith, S., Eyerman, S., Kodiyath, M., Hur, I., Petrini, F., & Karypis, G. (2017). Exploring optimizations on shared-memory platforms for parallel triangle counting algorithms. In 2017 IEEE High Performance Extreme Computing Conference, HPEC 2017 [8091054] (2017 IEEE High Performance Extreme Computing Conference, HPEC 2017). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/HPEC.2017.8091054