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 条

[31] DistTC: High Performance Distributed Triangle Counting
Hoang, Loc
Jatala, Vishwesh
Chen, Xuhao
Agarwal, Udit
Dathathri, Roshan
Gill, Gurbinder
Pingali, Keshav
2019 IEEE HIGH PERFORMANCE EXTREME COMPUTING CONFERENCE (HPEC), 2019,
[32] An FPGA Based Approach For People Counting Using Image Processing Techniques
Ahmad, Ibtihaj
Ul Islam, Zain
Ullah, Fahim
Hussain, Muhammad Abbas
Nabi, Shahid
2019 11TH INTERNATIONAL CONFERENCE ON KNOWLEDGE AND SMART TECHNOLOGY (KST), 2019, : 148 - 152
[33] Differentially Private Triangle Counting in Large Graphs
Ding, Xiaofeng
Sheng, Shujun
Zhou, Huajian
Zhang, Xiaodong
Bao, Zhifeng
Zhou, Pan
Jin, Hai
IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING, 2022, 34 (11) : 5278 - 5292
[34] High Performance Exact Triangle Counting on GPUs
Bisson, Mauro
Fatica, Massimiliano
IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 2017, 28 (12) : 3501 - 3510
[35] STRUD: Truss Decomposition of Simplicial Complexes
Preti, Giulia
Morales, Gianmarco De Francisci
Bonchi, Francesco
PROCEEDINGS OF THE WORLD WIDE WEB CONFERENCE 2021 (WWW 2021), 2021, : 3408 - 3418
[36] Hardware Implementation of LU Decomposition Using Dataflow Architecture on FPGA
Eljammaly, Mahmoud
Hanafy, Yasser
Wahdan, Abdelmoniem
Bayoumi, Amr
2013 5TH INTERNATIONAL CONFERENCE ON COMPUTER SCIENCE AND INFORMATION TECHNOLOGY (CSIT), 2013, : 298 - 302
[37] Implementation of a QR Decomposition Processor using Walke Mapping on FPGA
Camarda, Federico D.
Alpago, Octavio
Alvarez, Nicolas
Zacchigna, Federico
Lutenberg, Ariel
2016 IEEE BIENNIAL CONGRESS OF ARGENTINA (ARGENCON), 2016,
[38] Scalable Triangle Counting on Distributed-Memory Systems
Acer, Seher
Yasar, Abdurrahman
Rajamanickam, Sivasankaran
Wolf, Michael
Catalyurek, Umit V.
2019 IEEE HIGH PERFORMANCE EXTREME COMPUTING CONFERENCE (HPEC), 2019,
[39] Engineering a Distributed-Memory Triangle Counting Algorithm
Sanders, Peter
Uhl, Tim Niklas
2023 IEEE INTERNATIONAL PARALLEL AND DISTRIBUTED PROCESSING SYMPOSIUM, IPDPS, 2023, : 702 - 712
[40] Privacy-Preserving Triangle Counting in Large Graphs
Ding, Xiaofeng
Zhang, Xiaodong
Bao, Zhifeng
Jin, Hai
CIKM'18: PROCEEDINGS OF THE 27TH ACM INTERNATIONAL CONFERENCE ON INFORMATION AND KNOWLEDGE MANAGEMENT, 2018, : 1283 - 1292

← 1 2 3 4 5 →