Skip to content
Differentiated Computation and Partitioning on Skewed (Natural or Bipartite) Graphs
C++ Python CMake C Shell JavaScript Other
Branch: master
Clone or download
Pull request Compare This branch is 54 commits ahead, 15 commits behind jegonzal:master.
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
apps
cmake configured cmake to generate Eclipse project files Mar 30, 2012
cxxtest
demoapps
dist
doc
images
license
matlab
patches submited opencv patch by ponyma Sep 16, 2014
scripts
src
tests
toolkits
.gitignore
BINARY_README
CMakeLists.txt
Doxyfile
Doxyfile_internal
README.md
README_graphlab.md
TUTORIALS.md
configure

README.md

PowerLyra v1.0

License

PowerLyra is released under the Apache 2 license.

If you use PowerLyra in your research, please cite our paper:

    @inproceedings{Chen:eurosys2015powerlyra,
     title = {PowerLyra: Differentiated Graph Computation and Partitioning on Skewed Graphs},
     author = {Chen, Rong and Shi, Jiaxin and Chen, Yanzhe and Chen, Haibo},
     booktitle = {Proceedings of the Tenth European Conference on Computer Systems},
     series = {EuroSys '15},
     year = {2015},
     location = {Bordeaux, France},
    }

Introduction

PowerLyra is based on the latest codebase of GraphLab PowerGraph (a distributed graph computation framework written in C++) and can seamlessly support all GraphLab toolkits. PowerLyra provides several new hybrid execution engines and partitioning algorithms to achieve optimal performance by leveraging input graph properties (e.g., power-law and bipartite).

PowerLyra New Features:

  • Hybrid computation engine: Exploit the locality of low-degree vertices and the parallelism of high-degree vertices

  • Hybrid partitioning algorithm: Differentiate the partitioning algorithms for different types of vertices

  • Diverse scheduling strategy: Provide both synchronous and asynchronous computation engines

  • Compatible API: Seamlessly support all GraphLab toolkits

For more details on the PowerLyra see http://ipads.se.sjtu.edu.cn/projects/powerlyra.html, including new features, instructions, etc.

Hybrid Computation Engine

We argue that skewed distribution in natural graphs also calls for differentiated processing of high-degree and low-degree vertices. PowerLyra uses Pregel/GraphLab-like computation models for process low-degree vertices to minimize computation, communication and synchronization overhead, and uses PowerGraph-like computation model for process high-degree vertices to reduce load imbalance, contention and memory pressure. PowerLyra follows the interface of GAS (Gather, Apply and Scatter) model and can seamlessly support various graph algorithms (e.g., all GraphLab toolkits).

Hybrid Computation Engine

Hybrid Graph Partitioning

PowerLyra additionally proposes a new hybrid graph cut algorithm that embraces the best of both worlds in edge-cut and vertex-cut, which evenly distributes low-degree vertices along with their edges like edge-cut, and evenly distributes edges of high-degree vertices like vertex-cut. Both theoretical analysis and empirical validation show that the expected replication factor of random hybrid-cut is alway better than both random (Hash-based), contrained (e.g., Grid), and heuristic (e.g., Oblivious or Coordinated) vertex-cut for skewed power-law graphs.

Hybrid Partitioning Algorithms

Academic and Conference Papers

Rong Chen, Jiaxin Shi, Yanzhe Chen and Haibo Chen. "PowerLyra: Differentiated Graph Computation and Partitioning on Skewed Graphs." Proceeding of the 10th ACM SIGOPS European Conference on Computer Systems (EuroSys). Bordeaux, France. April, 2015.

Rong Chen, Jiaxin Shi, Binyu Zang and Haibing Guan. "BiGraph: Bipartite-oriented Distributed Graph Partitioning for Big Learning." Proceeding of the 5th Asia-Pacific Workshop on Systems (APSys). Beijing, China. June, 2014.

Rong Chen, Jiaxin Shi, Haibo Chen and Binyu Zang. "Bipartite-oriented Distributed Graph Partitioning for Big Learning." Journal of Computer Science and Technology (JCST), 30(1), pp. 20-29. January, 2015.

Building

The building, installation and tutorial of PowerLyra fully follow that of GraphLab PowerGraph. See README_GraphLab.txt for details.

You can’t perform that action at this time.