@inproceedings{969ab715f834490da069905138f1bef9,
title = "Update on k-truss Decomposition on GPU",
abstract = "In this paper, we present an update to our previous submission on k-truss decomposition from Graph Challenge 2018. For single k k-truss implementation, we propose multiple algorithmic optimizations that significantly improve performance by up to 35.2x (6.9x on average) compared to our previous GPU implementation. In addition, we present a scalable multi-GPU implementation in which each GPU handles a different 'k' value. Compared to our prior multi-GPU implementation, the proposed approach is faster by up to 151.3x (78.8x on average). In case when the edges with only maximal k-truss are sought, incrementing the 'k' value in each iteration is inefficient particularly for graphs with large maximum k-truss. Thus, we propose binary search for the 'k' value to find the maximal k-truss. The binary search approach on a single GPU is up to 101.5 (24.3x on average) faster than our 2018 k-truss submission. Lastly, we show that the proposed binary search finds the maximum k-truss for 'Twitter' graph dataset having 2.8 billion bidirectional edges in just 16 minutes on a single V100 GPU.",
keywords = "Binary search, CUDA, GPU, K-truss decomposition, Multi-GPU, Multi-node",
author = "Mohammad Almasri and Omer Anjum and Carl Pearson and Zaid Qureshi and Mailthody, \{Vikram S.\} and Rakesh Nagi and Jinjun Xiong and Hwu, \{Wen Mei\}",
note = "Publisher Copyright: {\textcopyright} 2019 IEEE.; 2019 IEEE High Performance Extreme Computing Conference, HPEC 2019 ; Conference date: 24-09-2019 Through 26-09-2019",
year = "2019",
month = sep,
doi = "10.1109/HPEC.2019.8916285",
language = "English",
series = "2019 IEEE High Performance Extreme Computing Conference, HPEC 2019",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
booktitle = "2019 IEEE High Performance Extreme Computing Conference, HPEC 2019",
address = "United States",
}