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

doi:10.1109/HPEC.2017.8091054

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

Computer Science and Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

26 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 language	English (US)
Title of host publication	2017 IEEE High Performance Extreme Computing Conference, HPEC 2017
Publisher	Institute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)	9781538634721
DOIs	https://doi.org/10.1109/HPEC.2017.8091054
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

Publication series

Name	2017 IEEE High Performance Extreme Computing Conference, HPEC 2017

Other

Other	2017 IEEE High Performance Extreme Computing Conference, HPEC 2017
Country/Territory	United States
City	Waltham
Period	9/12/17 → 9/14/17

Bibliographical note

Funding 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.

Publisher link

10.1109/HPEC.2017.8091054

Find It

Find It at U of M Libraries

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 Article 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

Exploring optimizations on shared-memory platforms for parallel triangle counting algorithms. / Tom, Ancy Sarah; Sundaram, Narayanan; Ahmed, Nesreen K. et al.
2017 IEEE High Performance Extreme Computing Conference, HPEC 2017. Institute of Electrical and Electronics Engineers Inc., 2017. 8091054 (2017 IEEE High Performance Extreme Computing Conference, HPEC 2017).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Tom, AS, Sundaram, N, Ahmed, NK, 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., 2017 IEEE High Performance Extreme Computing Conference, HPEC 2017, Waltham, United States, 9/12/17. https://doi.org/10.1109/HPEC.2017.8091054

Tom AS, Sundaram N, Ahmed NK, Smith S, Eyerman S, Kodiyath M et al. Exploring optimizations on shared-memory platforms for parallel triangle counting algorithms. In 2017 IEEE High Performance Extreme Computing Conference, HPEC 2017. Institute of Electrical and Electronics Engineers Inc. 2017. 8091054. (2017 IEEE High Performance Extreme Computing Conference, HPEC 2017). doi: 10.1109/HPEC.2017.8091054

@inproceedings{f31e98fd82b64d5a9877400df549672b,

title = "Exploring optimizations on shared-memory platforms for parallel triangle counting algorithms",

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.",

author = "Tom, {Ancy Sarah} and Narayanan Sundaram and Ahmed, {Nesreen K.} and Shaden Smith and Stijn Eyerman and Midhunchandra Kodiyath and Ibrahim Hur and Fabrizio Petrini and George Karypis",

note = "Funding 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.; 2017 IEEE High Performance Extreme Computing Conference, HPEC 2017 ; Conference date: 12-09-2017 Through 14-09-2017",

year = "2017",

month = oct,

day = "30",

doi = "10.1109/HPEC.2017.8091054",

language = "English (US)",

series = "2017 IEEE High Performance Extreme Computing Conference, HPEC 2017",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

booktitle = "2017 IEEE High Performance Extreme Computing Conference, HPEC 2017",

}

TY - GEN

T1 - Exploring optimizations on shared-memory platforms for parallel triangle counting algorithms

AU - Tom, Ancy Sarah

AU - Sundaram, Narayanan

AU - Ahmed, Nesreen K.

AU - Smith, Shaden

AU - Eyerman, Stijn

AU - Kodiyath, Midhunchandra

AU - Hur, Ibrahim

AU - Petrini, Fabrizio

AU - Karypis, George

N1 - Funding 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.

PY - 2017/10/30

Y1 - 2017/10/30

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85041173522&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85041173522&partnerID=8YFLogxK

U2 - 10.1109/HPEC.2017.8091054

DO - 10.1109/HPEC.2017.8091054

M3 - Conference contribution

AN - SCOPUS:85041173522

T3 - 2017 IEEE High Performance Extreme Computing Conference, HPEC 2017

BT - 2017 IEEE High Performance Extreme Computing Conference, HPEC 2017

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2017 IEEE High Performance Extreme Computing Conference, HPEC 2017

Y2 - 12 September 2017 through 14 September 2017

ER -

Exploring optimizations on shared-memory platforms for parallel triangle counting algorithms

Abstract

Publication series

Other

Bibliographical note

Publisher link

Find It

Other files and links

Fingerprint

Cite this