.png){kind=icon}
返回
Parallel Overlapping Community Detection Algorithm on GPU
.png){kind=icon}
PRE
AI
DOI：10.1109/TBDATA.2022.3180360.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
Community detection is one of the most representative graph mining applications, which is often assembled as a concurrent graph partition application to explore the maximum modularity (or gained modularity) of each community. However, many branch divergence operations create significant obstacles to unleashing GPU's high throughput and memory bandwidth, which are needed in community detection applications to divide the vertices into different communities. In this paper, we present Lugger, a GPU-based overlapping community detection algorithm that reduces GPU's branch divergence via the customer-designed cache-aware parallel searching technique. In Lugger, we first design a cache-aware parallel searching policy using the B-Tree structure. Then, we set the B-Tree node matches with the GPU cache line to meet the coalesced memory access manner and avoid the branch divergence in warps. Moreover, we design a positive node splitting scheme to reduce the lock operation and idle threads when building the B-Tree structure. In addition, we implement a warp-centric thread assignment strategy to make sure the workloads across threads are balanced. We implement the proposed algorithm on NVIDIA GPU and evaluate the performance on eight large graphs (up to 3 M vertices and 117 M edges) with ground-truth communities. The experimental results show that Lugger can outperform the state-of-the-art works on scalability and detection quality.
Keyword:
Graphics processing units
Message systems
Detection algorithms
Image edge detection
Big Data
Parallel processing
Instruction sets
Overlapping community detection
B-Tree
warp-centric thread assignment strategy
GPGPU
parallelism
期刊
I
IF:
5.7
论文数:
860
被引数:
3.0K
机构
暂无机构信息
引用论文
.png){kind=icon}
分享收藏
查看更多内容