TY - JOUR
T1 - Complex network partitioning using label propagation
AU - Slota, George M.
AU - Madduri, Kamesh
AU - Rajamanickam, Sivasankaran
N1 - Funding Information:
This research is part of the Blue Waters sustained-petascale computing project, which is supported by the National Science Foundation (awards OCI-0725070, ACI-1238993, and ACI-1444747) and the state of Illinois. Blue Waters is a joint effort of the University of Illinois at Urbana-Champaign and its National Center for Supercomputing Applications. This work is also supported by NSF grants ACI-1253881 and CCF-1439057 and used instrumentation funded by NSF grant OCI-0821527, as well as the National Energy Research Scientific Computing Center, supported by the Office of Science of the U.S. Department of Energy under contract DE-AC02-05CH11231. This work was also suppoerted by the DOE Office of Science through the FASTMath SciDAC Institute. Sandia National Laboratories is a multiprogram laboratory managed and operated by Sandia Corporation, a wholly owned subsidiary of Lockheed Martin Corporation, for the U.S. Department of Energys National Nuclear Security Administration under contract DE-AC04-94AL85000. Portions of this work previously appeared in Proceedings of the IEEE International Conference on Big Data, 2014.
Publisher Copyright:
© 2016 Society for Industrial and Applied Mathematics.
PY - 2016
Y1 - 2016
N2 - We present PuLP (partitioning using label propagation), a parallel and memory-efficient graph partitioning method specifically designed to partition low-diameter networks with skewed degree distributions on shared-memory multicore platforms. Graph partitioning is an important problem in scientific computing because it impacts the execution time and energy efficiency of computations on distributed-memory platforms. Partitioning determines the in-memory layout of a graph, which affects locality, intertask load balance, communication time, and overall memory utilization. A novel feature of our PuLP method is that it optimizes for multiple objective metrics simultaneously, while satisfying multiple partitioning constraints. Using our method, we are able to partition a web crawl with billions of edges on a single compute server in under a minute. For a collection of test graphs, we show that PuLP uses up to 7.8x less memory than state-of-the-art partitioners and is 5.0x faster, on average, than alternate approaches (with 16-way parallelism). We also achieve better partitioning quality results for the multiobjective scenario.
AB - We present PuLP (partitioning using label propagation), a parallel and memory-efficient graph partitioning method specifically designed to partition low-diameter networks with skewed degree distributions on shared-memory multicore platforms. Graph partitioning is an important problem in scientific computing because it impacts the execution time and energy efficiency of computations on distributed-memory platforms. Partitioning determines the in-memory layout of a graph, which affects locality, intertask load balance, communication time, and overall memory utilization. A novel feature of our PuLP method is that it optimizes for multiple objective metrics simultaneously, while satisfying multiple partitioning constraints. Using our method, we are able to partition a web crawl with billions of edges on a single compute server in under a minute. For a collection of test graphs, we show that PuLP uses up to 7.8x less memory than state-of-the-art partitioners and is 5.0x faster, on average, than alternate approaches (with 16-way parallelism). We also achieve better partitioning quality results for the multiobjective scenario.
UR - http://www.scopus.com/inward/record.url?scp=84994166962&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84994166962&partnerID=8YFLogxK
U2 - 10.1137/15M1026183
DO - 10.1137/15M1026183
M3 - Article
AN - SCOPUS:84994166962
SN - 1064-8275
VL - 38
SP - S620-S645
JO - SIAM Journal on Scientific Computing
JF - SIAM Journal on Scientific Computing
IS - 5
ER -