Scalable stochastic block partition
Scalable stochastic block partition
复制标题
可扩展的随机块分区
DOI：
10.1109/hpec.2017.8091050
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
The George Washington
中科院分区：
文献类型：
--
作者：
Ahsen J. Uppal;Guy Swope;H. H. Huang;The George Washington
虽然大规模的图形数据处理对于现实世界的应用程序来说是重要和有用的，但仍然是具有挑战性的，特别是对于诸如图划分之类的问题。图的最优划分是NP难问题，但有几种方法能在合理的时间内给出近似解。然而，扩展这些近似算法也是具有挑战性的。在这篇文章中，我们描述了我们为提高这种技术的可扩展性所做的努力，随机块划分是IEEE HPEC图挑战的基线算法[1]。本文的主要贡献包括：改进了基线自底向上算法的并行化，特别是针对贝叶斯推理的马尔可夫链蒙特卡罗(MCMC)节点更新算法；提出了一种新的自顶向下的分治算法，该算法能够降低静态划分的算法复杂度，也适用于流划分；并行的单节点多CPU实现和并行多节点MPI实现。虽然我们的重点是算法可伸缩性，但在多CPU单节点机器上，在100k顶点划分为8个子图的情况下，我们的Python实现比最快的基线并行C++运行时获得了1.65倍的加速比。在具有256个CPU的4机集群上，将20k结点图划分为4个子图，加速比提高61倍；在多CPU单结点机上，将50k结点图划分为8个子图，加速比为441倍。
The processing of graph data at large scale, though important and useful for real-world applications, continues to be challenging, particularly for problems such as graph partitioning. Optimal graph partitioning is NP-hard, but several methods provide approximate solutions in reasonable time. Yet scaling these approximate algorithms is also challenging. In this paper, we describe our efforts towards improving the scalability of one such technique, stochastic block partition, which is the baseline algorithm for the IEEE HPEC Graph Challenge [1]. Our key contributions are: improvements to the parallelization of the baseline bottom-up algorithm, especially the Markov Chain Monte Carlo (MCMC) nodal updates for Bayesian inference; a new top-down divide and conquer algorithm capable of reducing the algorithmic complexity of static partitioning and also suitable for streaming partitioning; a parallel single-node multi-CPU implementation and a parallel multi-node MPI implementation. Although our focus is on algorithmic scalability, our Python implementation obtains a speedup of 1.65× over the fastest baseline parallel C++ run at a graph size of 100k vertices divided into 8 subgraphs on a multi-CPU single node machine. It achieves a speedup of 61× over itself on a cluster of 4 machines with 256 CPUs for a 20k node graph divided into 4 subgraphs, and 441× speedup over itself on a 50k node graph divided into 8 subgraphs on a multi-CPU single node machine.