Parallel k-truss decomposition on multicore systems

Humayun Kabir; Kamesh Madduri

doi:10.1109/HPEC.2017.8091052

Parallel k-truss decomposition on multicore systems

Humayun Kabir, Kamesh Madduri

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

26 Scopus citations

Abstract

We discuss our submission to the HPEC 2017 Static Graph Challenge on k-truss decomposition and triangle counting. Our results use an algorithm called PKT (Parallel k-truss) designed for multicore systems. We are able to process almost all Graph Challenge datasets in under a minute on a 24-core server with 128 GB memory. For a synthetic Graph500 graph with 17 million vertices and 523 million edges, triangle counting takes 16 seconds and truss decomposition takes 29 minutes on the 24-core server.

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

All Science Journal Classification (ASJC) codes

Computational Theory and Mathematics
Hardware and Architecture
Computer Networks and Communications

Access to Document

10.1109/HPEC.2017.8091052

Cite this

@inproceedings{f043b4aae9f34517869ed757d11b151d,

title = "Parallel k-truss decomposition on multicore systems",

abstract = "We discuss our submission to the HPEC 2017 Static Graph Challenge on k-truss decomposition and triangle counting. Our results use an algorithm called PKT (Parallel k-truss) designed for multicore systems. We are able to process almost all Graph Challenge datasets in under a minute on a 24-core server with 128 GB memory. For a synthetic Graph500 graph with 17 million vertices and 523 million edges, triangle counting takes 16 seconds and truss decomposition takes 29 minutes on the 24-core server.",

author = "Humayun Kabir and Kamesh Madduri",

note = "Funding Information: This research is supported by the US National Science Foundation grants ACI-1253881 and CCF-1439057. This research was conducted with Advanced CyberInfrastructure computational resources provided by The Institute for CyberScience at The Pennsylvania State University (http://ics.psu.edu). Publisher Copyright: {\textcopyright} 2017 IEEE.; 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.8091052",

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

address = "United States",

}

Kabir, H & Madduri, K 2017, Parallel k-truss decomposition on multicore systems. in 2017 IEEE High Performance Extreme Computing Conference, HPEC 2017., 8091052, 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.8091052

Parallel k-truss decomposition on multicore systems. / Kabir, Humayun; Madduri, Kamesh.
2017 IEEE High Performance Extreme Computing Conference, HPEC 2017. Institute of Electrical and Electronics Engineers Inc., 2017. 8091052 (2017 IEEE High Performance Extreme Computing Conference, HPEC 2017).

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

TY - GEN

T1 - Parallel k-truss decomposition on multicore systems

AU - Kabir, Humayun

AU - Madduri, Kamesh

N1 - Funding Information: This research is supported by the US National Science Foundation grants ACI-1253881 and CCF-1439057. This research was conducted with Advanced CyberInfrastructure computational resources provided by The Institute for CyberScience at The Pennsylvania State University (http://ics.psu.edu). Publisher Copyright: © 2017 IEEE.

PY - 2017/10/30

Y1 - 2017/10/30

N2 - We discuss our submission to the HPEC 2017 Static Graph Challenge on k-truss decomposition and triangle counting. Our results use an algorithm called PKT (Parallel k-truss) designed for multicore systems. We are able to process almost all Graph Challenge datasets in under a minute on a 24-core server with 128 GB memory. For a synthetic Graph500 graph with 17 million vertices and 523 million edges, triangle counting takes 16 seconds and truss decomposition takes 29 minutes on the 24-core server.

AB - We discuss our submission to the HPEC 2017 Static Graph Challenge on k-truss decomposition and triangle counting. Our results use an algorithm called PKT (Parallel k-truss) designed for multicore systems. We are able to process almost all Graph Challenge datasets in under a minute on a 24-core server with 128 GB memory. For a synthetic Graph500 graph with 17 million vertices and 523 million edges, triangle counting takes 16 seconds and truss decomposition takes 29 minutes on the 24-core server.

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

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

U2 - 10.1109/HPEC.2017.8091052

DO - 10.1109/HPEC.2017.8091052

M3 - Conference contribution

AN - SCOPUS:85041212454

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 -

Parallel k-truss decomposition on multicore systems

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this