Triangle Counting and Truss Decomposition using FPGA

Sitao Huang, Mohamed El-Hadedy, Cong Hao, Qin Li, Vikram S. Mailthody, Ketan Date, Jinjun Xiong, Deming Chen, Rakesh Nagi, Wen-Mei W Hwu

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

Abstract

Triangle counting and truss decomposition are two essential procedures in graph analysis. As the scale of graphs grows larger, designing highly efficient graph analysis systems with less power demand becomes more and more urgent. In this paper, we present triangle counting and truss decomposition using a Field-Programmable Gate Array (FPGA). We leverage the flexibility of FPGAs and achieve low-latency high-efficiency implementations. Evaluation on SNAP dataset shows that our triangle counting and truss decomposition implementations achieve 43.5× on average (up to 757.7×) and 6.4× on average (up to 68.0×) higher performance per Watt respectively over GPU solutions.

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

Field programmable gate arrays (FPGA)
Decomposition
Graphics processing unit

Keywords

  • FPGA
  • Graph algorithms
  • Triangle counting
  • Truss decomposition

ASJC Scopus subject areas

  • Computer Science (miscellaneous)
  • Hardware and Architecture

Cite this

Huang, S., El-Hadedy, M., Hao, C., Li, Q., Mailthody, V. S., Date, K., ... Hwu, W-M. W. (2018). Triangle Counting and Truss Decomposition using FPGA. In 2018 IEEE High Performance Extreme Computing Conference, HPEC 2018 [8547536] (2018 IEEE High Performance Extreme Computing Conference, HPEC 2018). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/HPEC.2018.8547536

Triangle Counting and Truss Decomposition using FPGA. / Huang, Sitao; El-Hadedy, Mohamed; Hao, Cong; Li, Qin; Mailthody, Vikram S.; Date, Ketan; Xiong, Jinjun; Chen, Deming; Nagi, Rakesh; Hwu, Wen-Mei W.

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

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

Huang, S, El-Hadedy, M, Hao, C, Li, Q, Mailthody, VS, Date, K, Xiong, J, Chen, D, Nagi, R & Hwu, W-MW 2018, Triangle Counting and Truss Decomposition using FPGA. in 2018 IEEE High Performance Extreme Computing Conference, HPEC 2018., 8547536, 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.8547536
Huang S, El-Hadedy M, Hao C, Li Q, Mailthody VS, Date K et al. Triangle Counting and Truss Decomposition using FPGA. In 2018 IEEE High Performance Extreme Computing Conference, HPEC 2018. Institute of Electrical and Electronics Engineers Inc. 2018. 8547536. (2018 IEEE High Performance Extreme Computing Conference, HPEC 2018). https://doi.org/10.1109/HPEC.2018.8547536
Huang, Sitao ; El-Hadedy, Mohamed ; Hao, Cong ; Li, Qin ; Mailthody, Vikram S. ; Date, Ketan ; Xiong, Jinjun ; Chen, Deming ; Nagi, Rakesh ; Hwu, Wen-Mei W. / Triangle Counting and Truss Decomposition using FPGA. 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{136b68e6204b4e0c89d7d4ef10c3de6f,
title = "Triangle Counting and Truss Decomposition using FPGA",
abstract = "Triangle counting and truss decomposition are two essential procedures in graph analysis. As the scale of graphs grows larger, designing highly efficient graph analysis systems with less power demand becomes more and more urgent. In this paper, we present triangle counting and truss decomposition using a Field-Programmable Gate Array (FPGA). We leverage the flexibility of FPGAs and achieve low-latency high-efficiency implementations. Evaluation on SNAP dataset shows that our triangle counting and truss decomposition implementations achieve 43.5× on average (up to 757.7×) and 6.4× on average (up to 68.0×) higher performance per Watt respectively over GPU solutions.",
keywords = "FPGA, Graph algorithms, Triangle counting, Truss decomposition",
author = "Sitao Huang and Mohamed El-Hadedy and Cong Hao and Qin Li and Mailthody, {Vikram S.} and Ketan Date and Jinjun Xiong and Deming Chen and Rakesh Nagi and Hwu, {Wen-Mei W}",
year = "2018",
month = "11",
day = "26",
doi = "10.1109/HPEC.2018.8547536",
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 - Triangle Counting and Truss Decomposition using FPGA

AU - Huang, Sitao

AU - El-Hadedy, Mohamed

AU - Hao, Cong

AU - Li, Qin

AU - Mailthody, Vikram S.

AU - Date, Ketan

AU - Xiong, Jinjun

AU - Chen, Deming

AU - Nagi, Rakesh

AU - Hwu, Wen-Mei W

PY - 2018/11/26

Y1 - 2018/11/26

N2 - Triangle counting and truss decomposition are two essential procedures in graph analysis. As the scale of graphs grows larger, designing highly efficient graph analysis systems with less power demand becomes more and more urgent. In this paper, we present triangle counting and truss decomposition using a Field-Programmable Gate Array (FPGA). We leverage the flexibility of FPGAs and achieve low-latency high-efficiency implementations. Evaluation on SNAP dataset shows that our triangle counting and truss decomposition implementations achieve 43.5× on average (up to 757.7×) and 6.4× on average (up to 68.0×) higher performance per Watt respectively over GPU solutions.

AB - Triangle counting and truss decomposition are two essential procedures in graph analysis. As the scale of graphs grows larger, designing highly efficient graph analysis systems with less power demand becomes more and more urgent. In this paper, we present triangle counting and truss decomposition using a Field-Programmable Gate Array (FPGA). We leverage the flexibility of FPGAs and achieve low-latency high-efficiency implementations. Evaluation on SNAP dataset shows that our triangle counting and truss decomposition implementations achieve 43.5× on average (up to 757.7×) and 6.4× on average (up to 68.0×) higher performance per Watt respectively over GPU solutions.

KW - FPGA

KW - Graph algorithms

KW - Triangle counting

KW - Truss decomposition

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

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

U2 - 10.1109/HPEC.2018.8547536

DO - 10.1109/HPEC.2018.8547536

M3 - Conference contribution

AN - SCOPUS:85060092130

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 -