NUMA-aware Graph-structured Analytics
Kaiyuan Zhang, Rong Chen and Haibo Chen
ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP'15)
Bay Area, California, USA, February, 2015.
Graph-structured analytics has been widely adopted in a number of big data applications such as social computation, web-search and recommendation systems. Though much prior research focuses on scaling graph-analytics on distributed environments, the strong desire on performance per core, dollar and joule has generated considerable interests of processing large-scale graphs on a single server-class machine, which may have several terabytes of RAM and 80 or more cores. However, prior graph-analytics systems are largely neutral to NUMA characteristics and thus have suboptimal performance.
A detailed study of NUMA characteristics and their impact on the efficiency of graph-analytics uncovers two insights:
1) either random or interleaved allocation of graph data will significantly hamper data locality and parallelism;
2) sequential inter-node (i.e., remote) memory accesses have much higher bandwidth than both intra- and inter-node random ones.
Based on them, we design and implement Polymer, a NUMA-aware graph-analytics framework on multicore with two key design decisions. First, Polymer differentially allocates and places topology data, application-defined data and mutable runtime states of a graph system according to their access patterns to minimize remote accesses. Second, for some remaining random accesses, Polymer carefully converts random remote accesses into sequential remote accesses, by using lightweight replication of vertices across NUMA nodes. To improve load balance and vertex convergence, Polymer is further built with a hierarchical barrier to boost parallelism and locality, an edge-oriented balanced partitioning for skewed graphs, and adaptive data structures according to the proportion of active vertices. A detailed evaluation on an 80-core machine shows that Polymer often outperforms the state-of-the-art single-machine graphanalytics systems, including Ligra, X-Stream and Galois, for a set of popular real-world and synthetic graphs.
NUMA-aware Graph-structured Analytics |
|
If you use Polymer in your work or research, please let us know about it. We also encourage you to reference our paper.
EuroSys 2015 TPC Meeting WorkShop, University Cambridge, Jan. 2015 (slides)
PPoPP 2015, Bay Area, California, USA, Feb. 2015 (slides)
The Polymer source code is distributed with a Apache license 2.0. The copyright is held by Shanghai Jiao Tong University. Polymer is provided "as is" without any warranties and conditions of any kind.
You can check out the latest code of Polymer from the github mirror or from IPADS's gitlab server: git clone http://ipads.se.sjtu.edu.cn:1312/opensource/polymer.git. Currently, Polymer mostly follows the interface from Ligra and thus most applications in Ligra can run with small modifications on Polymer.
If you are interested in estimating or working with the version of Polymer in PPoPP's paper, you can obtain the snapshot (~61KB). (last updated: Dec. 12, 2014)
Please contact Kaiyuan Zhang or Rong Chen for further information. Welcome to let us know about bug reports and suggested improvements, while we may not be able to provide technical support timely. If you make some correction or improvement to Polymer, we would appreciate receiving a patch that we can include in the next release.
PowerLyra: Differentiated Graph Computation and Partitioning on Skewed Graphs.
PowerSwitch: Adaptive prediction and mode switch (synchronous and asynchronous) on graph-parallel computation.
Imitator: Replication-based Fault-tolerance for Large-scale Graph Processing.
Cyclops: Computation and Communication Efficient Graph Processing with Distributed Immutable View.