Date of Award

9-8-2015

Document Type

Dissertation

Degree Name

Doctor of Philosophy (PhD)

Department

Computer Science

First Advisor

Kenji Yoshigoe

Abstract

A number of distributed graph-parallel computing systems have been proposed to address the needs of solving complex and large-scale graph algorithms. Distributed Graphlab and PowerGraph are two such frameworks, which demonstrate excellent performance with high scalability and fault tolerance. However, unnecessary and excessive communications among computing nodes in these frameworks not only reduce the network efficiency but may also cause a decrease in runtime performance. In this work, we first conduct an evaluation work for representative distributed graph-parallel processing. Secondly, we propose a mechanism to identify and eliminate excessive communications for PageRank-like algorithms during synchronization phase of the distributed graph-parallel computing abstractions. We integrate it on PowerGraph and name it LightGraph. Thirdly, we propose a L-PowerGraph mechanism to further reduce the communication overhead of PageRank-like algorithms for PowerGraph. In particular, L-PowerGraph eliminates both the synchronizing communication for the mirrors without outgoing edges and the Gather communication for the mirrors without incoming edges. Lastly, we propose an edge direction-aware graph partitioning strategy to maximize the effectiveness of both LightGraph and L-PowerGraph. This strategy optimally isolates the outgoing edges from the incoming edges for each vertex. We conduct extensive experiments to verify the effectiveness of our methods with multiple datasets.

Download

Share

COinS