Collaborative (CPU + GPU) Algorithms for Triangle Counting and Truss Decomposition

Vikram S. Mailthody, Ketan Date, Zaid Qureshi, Carl Pearson, Rakesh Nagi, Jinjun Xiong, Wen-Mei W Hwu

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

Abstract

In this paper, we present an update to our previous submission from Graph Challenge 2017. This work describes and evaluates new software algorithm optimizations undertaken for our 2018 year submission on Collaborative CPU+GPU Algorithms for Triangle Counting and Truss Decomposition. First, we describe four major optimizations for the triangle counting which improved performance by up to 117x over our prior submission. Additionally, we show that our triangle-counting algorithm is on average 151.7x faster than NVIDIA's NVGraph library (max 476x) for SNAP datasets. Second, we propose a novel parallel k-truss decomposition algorithm that is time-efficient and is up to 13.9x faster than our previous submission. Third, we evaluate the effect of generational hardware improvements between the IBM 'Minsky' (POWER8, P100, NVLink 1.0) and 'Newell' (POWER9, V100, NVLink 2.0) platforms. Lastly, the software optimizations presented in this work and the hardware improvements in the Newell platform enable analytics and discovery on large graphs with millions of nodes and billions of edges in less than a minute. In sum, the new algorithmic implementations are significantly faster and can handle much larger 'big' graphs.

Original languageEnglish (US)
Title of host publication2018 IEEE High Performance Extreme Computing Conference, HPEC 2018
PublisherInstitute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)9781538659892
DOIs
StatePublished - Nov 26 2018
Event2018 IEEE High Performance Extreme Computing Conference, HPEC 2018 - Waltham, United States
Duration: Sep 25 2018Sep 27 2018

Publication series

Name2018 IEEE High Performance Extreme Computing Conference, HPEC 2018

Other

Other2018 IEEE High Performance Extreme Computing Conference, HPEC 2018
CountryUnited States
CityWaltham
Period9/25/189/27/18

Fingerprint

Program processors
Decomposition
Hardware
Graphics processing unit

Keywords

  • CUDA
  • Collaborative graph algorithms
  • GPU
  • Triangle counting
  • Truss decomposition

ASJC Scopus subject areas

  • Computer Science (miscellaneous)
  • Hardware and Architecture

Cite this

Mailthody, V. S., Date, K., Qureshi, Z., Pearson, C., Nagi, R., Xiong, J., & Hwu, W-M. W. (2018). Collaborative (CPU + GPU) Algorithms for Triangle Counting and Truss Decomposition. In 2018 IEEE High Performance Extreme Computing Conference, HPEC 2018 [8547517] (2018 IEEE High Performance Extreme Computing Conference, HPEC 2018). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/HPEC.2018.8547517

Collaborative (CPU + GPU) Algorithms for Triangle Counting and Truss Decomposition. / Mailthody, Vikram S.; Date, Ketan; Qureshi, Zaid; Pearson, Carl; Nagi, Rakesh; Xiong, Jinjun; Hwu, Wen-Mei W.

2018 IEEE High Performance Extreme Computing Conference, HPEC 2018. Institute of Electrical and Electronics Engineers Inc., 2018. 8547517 (2018 IEEE High Performance Extreme Computing Conference, HPEC 2018).

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

Mailthody, VS, Date, K, Qureshi, Z, Pearson, C, Nagi, R, Xiong, J & Hwu, W-MW 2018, Collaborative (CPU + GPU) Algorithms for Triangle Counting and Truss Decomposition. in 2018 IEEE High Performance Extreme Computing Conference, HPEC 2018., 8547517, 2018 IEEE High Performance Extreme Computing Conference, HPEC 2018, Institute of Electrical and Electronics Engineers Inc., 2018 IEEE High Performance Extreme Computing Conference, HPEC 2018, Waltham, United States, 9/25/18. https://doi.org/10.1109/HPEC.2018.8547517
Mailthody VS, Date K, Qureshi Z, Pearson C, Nagi R, Xiong J et al. Collaborative (CPU + GPU) Algorithms for Triangle Counting and Truss Decomposition. In 2018 IEEE High Performance Extreme Computing Conference, HPEC 2018. Institute of Electrical and Electronics Engineers Inc. 2018. 8547517. (2018 IEEE High Performance Extreme Computing Conference, HPEC 2018). https://doi.org/10.1109/HPEC.2018.8547517
Mailthody, Vikram S. ; Date, Ketan ; Qureshi, Zaid ; Pearson, Carl ; Nagi, Rakesh ; Xiong, Jinjun ; Hwu, Wen-Mei W. / Collaborative (CPU + GPU) Algorithms for Triangle Counting and Truss Decomposition. 2018 IEEE High Performance Extreme Computing Conference, HPEC 2018. Institute of Electrical and Electronics Engineers Inc., 2018. (2018 IEEE High Performance Extreme Computing Conference, HPEC 2018).
@inproceedings{39da4e9c77e54637ac5d0b42863614ee,
title = "Collaborative (CPU + GPU) Algorithms for Triangle Counting and Truss Decomposition",
abstract = "In this paper, we present an update to our previous submission from Graph Challenge 2017. This work describes and evaluates new software algorithm optimizations undertaken for our 2018 year submission on Collaborative CPU+GPU Algorithms for Triangle Counting and Truss Decomposition. First, we describe four major optimizations for the triangle counting which improved performance by up to 117x over our prior submission. Additionally, we show that our triangle-counting algorithm is on average 151.7x faster than NVIDIA's NVGraph library (max 476x) for SNAP datasets. Second, we propose a novel parallel k-truss decomposition algorithm that is time-efficient and is up to 13.9x faster than our previous submission. Third, we evaluate the effect of generational hardware improvements between the IBM 'Minsky' (POWER8, P100, NVLink 1.0) and 'Newell' (POWER9, V100, NVLink 2.0) platforms. Lastly, the software optimizations presented in this work and the hardware improvements in the Newell platform enable analytics and discovery on large graphs with millions of nodes and billions of edges in less than a minute. In sum, the new algorithmic implementations are significantly faster and can handle much larger 'big' graphs.",
keywords = "CUDA, Collaborative graph algorithms, GPU, Triangle counting, Truss decomposition",
author = "Mailthody, {Vikram S.} and Ketan Date and Zaid Qureshi and Carl Pearson and Rakesh Nagi and Jinjun Xiong and Hwu, {Wen-Mei W}",
year = "2018",
month = "11",
day = "26",
doi = "10.1109/HPEC.2018.8547517",
language = "English (US)",
series = "2018 IEEE High Performance Extreme Computing Conference, HPEC 2018",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
booktitle = "2018 IEEE High Performance Extreme Computing Conference, HPEC 2018",
address = "United States",

}

TY - GEN

T1 - Collaborative (CPU + GPU) Algorithms for Triangle Counting and Truss Decomposition

AU - Mailthody, Vikram S.

AU - Date, Ketan

AU - Qureshi, Zaid

AU - Pearson, Carl

AU - Nagi, Rakesh

AU - Xiong, Jinjun

AU - Hwu, Wen-Mei W

PY - 2018/11/26

Y1 - 2018/11/26

N2 - In this paper, we present an update to our previous submission from Graph Challenge 2017. This work describes and evaluates new software algorithm optimizations undertaken for our 2018 year submission on Collaborative CPU+GPU Algorithms for Triangle Counting and Truss Decomposition. First, we describe four major optimizations for the triangle counting which improved performance by up to 117x over our prior submission. Additionally, we show that our triangle-counting algorithm is on average 151.7x faster than NVIDIA's NVGraph library (max 476x) for SNAP datasets. Second, we propose a novel parallel k-truss decomposition algorithm that is time-efficient and is up to 13.9x faster than our previous submission. Third, we evaluate the effect of generational hardware improvements between the IBM 'Minsky' (POWER8, P100, NVLink 1.0) and 'Newell' (POWER9, V100, NVLink 2.0) platforms. Lastly, the software optimizations presented in this work and the hardware improvements in the Newell platform enable analytics and discovery on large graphs with millions of nodes and billions of edges in less than a minute. In sum, the new algorithmic implementations are significantly faster and can handle much larger 'big' graphs.

AB - In this paper, we present an update to our previous submission from Graph Challenge 2017. This work describes and evaluates new software algorithm optimizations undertaken for our 2018 year submission on Collaborative CPU+GPU Algorithms for Triangle Counting and Truss Decomposition. First, we describe four major optimizations for the triangle counting which improved performance by up to 117x over our prior submission. Additionally, we show that our triangle-counting algorithm is on average 151.7x faster than NVIDIA's NVGraph library (max 476x) for SNAP datasets. Second, we propose a novel parallel k-truss decomposition algorithm that is time-efficient and is up to 13.9x faster than our previous submission. Third, we evaluate the effect of generational hardware improvements between the IBM 'Minsky' (POWER8, P100, NVLink 1.0) and 'Newell' (POWER9, V100, NVLink 2.0) platforms. Lastly, the software optimizations presented in this work and the hardware improvements in the Newell platform enable analytics and discovery on large graphs with millions of nodes and billions of edges in less than a minute. In sum, the new algorithmic implementations are significantly faster and can handle much larger 'big' graphs.

KW - CUDA

KW - Collaborative graph algorithms

KW - GPU

KW - Triangle counting

KW - Truss decomposition

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

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

U2 - 10.1109/HPEC.2018.8547517

DO - 10.1109/HPEC.2018.8547517

M3 - Conference contribution

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

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

PB - Institute of Electrical and Electronics Engineers Inc.

ER -