NDLI: PowerLyra: differentiated graph computation and partitioning on skewed graphs

Please wait, while we are loading the content...

PowerLyra: differentiated graph computation and partitioning on skewed graphs

An in-memory object caching framework with adaptive load balancing

Visigoth fault tolerance

Deriving and comparing deduplication techniques using a model-based classification

Process-level power estimation in VM-based systems

Large-scale cluster management at Google with Borg

NBA (network balancing act): a high-performance packet processing framework for heterogeneous processors

Maxoid: transparently confining mobile applications with custom views of state

Popcorn: bridging the programmability gap in heterogeneous-ISA platforms

Musketeer: all for one, one for all in data processing systems

GD-Wheel: a cost-aware replacement policy for key-value stores

Taming uncertainty in distributed systems with help from the network

An efficient page-level FTL to optimize address translation in flash memory

Application-assisted live migration of virtual machines with Java applications

ConfValley: a systematic configuration validation framework for cloud services

In-Net: in-network processing for the masses

TinMan: eliminating confidential mobile data exposure with security oriented offloading

Hare: a file system for non-cache-coherent multicores

MALT: distributed data-parallelism for existing ML applications

Putting consistency back into eventual consistency

Extensible distributed coordination

Guardat: enforcing data policies at the storage layer

SpotCheck: designing a derivative IaaS cloud on the spot market

Guaranteeing deadlines for inter-datacenter transfers

Flux: multi-surface computing in Android

Verifiable differential privacy

High-performance determinism with total store order consistency

Simba: tunable end-to-end data consistency for mobile apps

CYRUS: towards client-defined cloud storage

Synapse: a microservices architecture for heterogeneous-database web applications

μPnP: plug and play peripherals for the internet of things

Scaling concurrent log-structured data stores

PowerLyra: differentiated graph computation and partitioning on skewed graphs

Content Provider	ACM Digital Library
Author	Chen, Rong Chen, Haibo Shi, Jiaxin Chen, Yanzhe
Abstract	Natural graphs with skewed distribution raise unique challenges to graph computation and partitioning. Existing graph-parallel systems usually use a "one size fits all" design that uniformly processes all vertices, which either suffer from notable load imbalance and high contention for high-degree vertices (e.g., Pregel and GraphLab), or incur high communication cost and memory consumption even for low-degree vertices (e.g., PowerGraph and GraphX). In this paper, we argue that skewed distribution in natural graphs also calls for differentiated processing on high-degree and low-degree vertices. We then introduce PowerLyra, a new graph computation engine that embraces the best of both worlds of existing graph-parallel systems, by dynamically applying different computation and partitioning strategies for different vertices. PowerLyra further provides an efficient hybrid graph partitioning algorithm (hybrid-cut) that combines edge-cut and vertex-cut with heuristics. Based on PowerLyra, we design locality-conscious data layout optimization to improve cache locality of graph accesses during communication. PowerLyra is implemented as a separate computation engine of PowerGraph, and can seamlessly support various graph algorithms. A detailed evaluation on two clusters using graph-analytics and MLDM (machine learning and data mining) applications show that PowerLyra outperforms PowerGraph by up to 5.53X (from 1.24X) and 3.26X (from 1.49X) for real-world and synthetic graphs accordingly, and is much faster than other systems like GraphX and Giraph, yet with much less memory consumption. A porting of hybrid-cut to GraphX further confirms the efficiency and generality of PowerLyra.
Starting Page	1
Ending Page	15
Page Count	15
File Format	PDF MP4
ISBN	9781450332385
DOI	10.1145/2741948.2741970
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2015-04-17
Publisher Place	New York
Access Restriction	Subscribed
Content Type	Audio Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Study on Partitioning Real-World Directed Graphs of Skewed Degree Distribution

Streaming graph partitioning for large distributed graphs

A multilevel algorithm for partitioning graphs

An Improved Spectral Graph Partitioning Algorithm for Mapping Parallel Computations

Partitioning Hypergraphs in Scientific Computing Applications through Vertex Separators on Graphs

Partitioning Planar Graphs

Efficient breadth-first search on large graphs with skewed degree distributions

Graph partitioning into isolated, high conductance clusters: theory, computation and applications to preconditioning

Scalable matrix computations on large scale-free graphs using 2D graph partitioning

PowerLyra: differentiated graph computation and partitioning on skewed graphs

Similar Documents

Study on Partitioning Real-World Directed Graphs of Skewed Degree Distribution

Streaming graph partitioning for large distributed graphs

A multilevel algorithm for partitioning graphs

An Improved Spectral Graph Partitioning Algorithm for Mapping Parallel Computations

Partitioning Hypergraphs in Scientific Computing Applications through Vertex Separators on Graphs

Partitioning Planar Graphs

Efficient breadth-first search on large graphs with skewed degree distributions

Graph partitioning into isolated, high conductance clusters: theory, computation and applications to preconditioning

Scalable matrix computations on large scale-free graphs using 2D graph partitioning

PowerLyra: differentiated graph computation and partitioning on skewed graphs