Paper Info
Title
Towards Community Detection on Heterogeneous Platforms.
Abstract
Over the last decade, community detection has become an increasingly important topic of research due to its many applications in different fields of research, such as biology and sociology. One example of a modern community detection algorithm is Scalable Community Detection (SCD), which has been shown to produce high-quality results, but its performance remains an issue on large graphs. In this work, we demonstrate how SCD can benefit from the heterogeneity offered by hybrid CPU-GPU platforms by presenting Het-SCD: a heterogeneous version of SCD which combines the larger memory capacity of the CPU with the larger computational power of the GPU. To enable this, we have designed an entirely new version of SCD which efficiently uses the fine-grained parallelism of GPUs. We report performance results on six real-world graphs (up to 1.8B edges) and six platforms. We observe excellent performance for only the GPU (e.g., 70x speedup over sequential CPU version on graph of 117M edges) and for combining the CPU and GPU (e.g., 40x speedup for same graph on low-end GPU with insufficient memory to store entire dataset). These results demonstrate that Het-SCD is an excellent solution for large-scale community detection, since it provides high performance while preserving the high quality of the original algorithm.
Year
DOI
Venue
2015
10.1007/978-3-319-27308-2_18
Lecture Notes in Computer Science
Keywords
Field
DocType
Community detection,Heterogeneous computing,GPU computing,SCD algorithm,WCC metric
Graph,Central processing unit,Computer science,Parallel computing,Symmetric multiprocessor system,General-purpose computing on graphics processing units,Speedup,Scalability
Conference
Volume
ISSN
Citations 
9523
0302-9743
0
PageRank 
References 
Authors
0.34
4
4
Name
Order
Citations
PageRank
Stijn Heldens100.34
Ana Lucia Varbanescu252044.83
Arnau Prat-Pérez322713.44
Josep-Lluis Larriba-Pey424521.70