Triangle Counting and Truss Decomposition using FPGA

被引：0

作者：

Huang, Sitao ^{[1
]}

El-Hadedy, Mohamed ^{[1
]}

Hao, Cong ^{[1
]}

Li, Qin ^{[1
]}

Mailthody, Vikram S. ^{[1
]}

Date, Ketan ^{[2
]}

Xiong, Jinjun ^{[3
]}

Chen, Deming ^{[1
]}

Nagi, Rakesh ^{[2
]}

Hwu, Wen-mei ^{[1
]}

机构：

[1] Univ Illinois, ECE, Urbana, IL 61801 USA

[2] Univ Illinois, ISE, Urbana, IL 61801 USA

[3] IBM Corp, Thomas J Watson Res Ctr, Cognit Comp Syst Res, Yorktown Hts, NY 10598 USA

来源：

2018 IEEE HIGH PERFORMANCE EXTREME COMPUTING CONFERENCE (HPEC) | 2018年

关键词：

FPGA; graph algorithms; triangle counting; truss decomposition;

D O I：

暂无

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

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.5x on average (up to 757.7x) and 6.4x on average (up to 68.0x) higher performance per Watt respectively over GPU solutions.

引用

页数：7

共 50 条

[41] Distributed, Shared-Memory Parallel Triangle Counting
Kanewala, Thejaka Amila
Zalewski, Marcin
Lumsdaine, Andrew
PROCEEDINGS OF THE PLATFORM FOR ADVANCED SCIENTIFIC COMPUTING CONFERENCE (PASC '18), 2017,
[42] How the Degeneracy Helps for Triangle Counting in Graph Streams
Bera, Suman K.
Seshadhri, C.
PODS'20: PROCEEDINGS OF THE 39TH ACM SIGMOD-SIGACT-SIGAI SYMPOSIUM ON PRINCIPLES OF DATABASE SYSTEMS, 2020, : 457 - 467
[43] HyKernel: A Hybrid Selection of One/Two-Phase Kernels for Triangle Counting on GPUs
Almasri, Mohammad
Vasudeva, Neo
Nagi, Rakesh
Xiong, Jinjun
Hwu, Wen-Mei
2021 IEEE HIGH PERFORMANCE EXTREME COMPUTING CONFERENCE (HPEC), 2021,
[44] Higher-Order Truss Decomposition in Graphs
Chen, Zi
Yuan, Long
Han, Li
Qian, Zhengping
IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING, 2023, 35 (04) : 3966 - 3978
[45] Scalable probabilistic truss decomposition using central limit theorem and H-index
Fatemeh Esfahani
Mahsa Daneshmand
Venkatesh Srinivasan
Alex Thomo
Kui Wu
Distributed and Parallel Databases, 2022, 40 : 299 - 333
[46] Scalable probabilistic truss decomposition using central limit theorem and H-index
Esfahani, Fatemeh
Daneshmand, Mahsa
Srinivasan, Venkatesh
Thomo, Alex
Wu, Kui
DISTRIBUTED AND PARALLEL DATABASES, 2022, 40 (2-3) : 299 - 333
[47] A NUMA-Aware Parallel Truss Decomposition Algorithm for Large Scale Graphs
Mou, Zhebin
Xiao, Nong
Chen, Zhiguang
ALGORITHMS AND ARCHITECTURES FOR PARALLEL PROCESSING, ICA3PP 2021, PT II, 2022, 13156 : 193 - 212
[48] K-mer Counting Using Bloom Filters with an FPGA-Attached HMC
Mcvicar, Nathaniel
Lin, Chih-Ching
Hauck, Scott
2017 IEEE 25TH ANNUAL INTERNATIONAL SYMPOSIUM ON FIELD-PROGRAMMABLE CUSTOM COMPUTING MACHINES (FCCM 2017), 2017, : 203 - 210
[49] FPGA Realization of the Reconfigurable Mesh Counting Algorithm
Ben-Asher, Yosi
Stein, Esti
Tartakovsky, Vladislav
JOURNAL OF CIRCUITS SYSTEMS AND COMPUTERS, 2021, 30 (09)
[50] A Block-Based Triangle Counting Algorithm on Heterogeneous Environments
Yasar, Abdurrahman
Rajamanickam, Sivasankaran
Berry, Jonathan W.
Catalyurek, Umit V.
IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 2022, 33 (02) : 444 - 458

← 1 2 3 4 5 →