Abstract | ||
---|---|---|
We present and evaluate a new GPU algorithm based on the Louvain method for community detection. Our algorithm is the first for this problem that parallelizes the access to individual edges. In this way we can fine tune the load balance when processing networks with nodes of highly varying degrees. This is achieved by scaling the number of threads assigned to each node according to its degree. Extensive experiments show that we obtain speedups up to a factor of 270 compared to the sequential algorithm. The algorithm consistently outperforms other recent shared memory implementations and is only one order of magnitude slower than the current fastest parallel Louvain method running on a Blue Gene/Q supercomputer using more than 500K threads. |
Year | DOI | Venue |
---|---|---|
2017 | 10.1109/IPDPS.2017.16 | 2017 IEEE International Parallel and Distributed Processing Symposium (IPDPS) |
Keywords | Field | DocType |
community detection,GPU algorithm,Louvain method,individual edges,load balance,processing networks,sequential algorithm,shared memory implementations,magnitude slower,parallel Louvain method,Blue Gene/Q supercomputer | Shared memory,Supercomputer,Instruction set,Parallel algorithm,Load balancing (computing),Computer science,Parallel computing,Thread (computing),Sequential algorithm,Cluster analysis,Distributed computing | Conference |
ISSN | ISBN | Citations |
1530-2075 | 978-1-5386-3915-3 | 2 |
PageRank | References | Authors |
0.38 | 14 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Md. Naim | 1 | 2 | 0.38 |
Fredrik Manne | 2 | 549 | 49.60 |
Mahantesh Halappanavar | 3 | 218 | 33.64 |
Antonino Tumeo | 4 | 356 | 44.70 |