Abstract | ||
---|---|---|
In order to process complex and large-scale graph data, numerous distributed graph-parallel computing platforms have been proposed. PowerGraph is an excellent representative of them. It has exhibited better performance, such as faster graph-processing rate and higher scalability, than others. However, like in other distributed graph computing systems, unnecessary and excessive communications among computing nodes in PowerGraph not only aggravate the network I/O workload of the underlying computing hardware systems but may also cause a decrease in runtime performance. In this paper, we propose and implement a mechanism called L-PowerGraph, which reduces the communication overhead in PowerGraph. First, L-PowerGraph identifies and eliminates the avoidable communications in PowerGraph. Second, in order to further reduce the required communications L-PowerGraph proposes an edge direction-aware master appointment strategy, in which L-PowerGraph appoints the replica with both incoming and outgoing edges as master. Third, L-PowerGraph proposes an edge direction-aware graph partition strategy, which optimally isolates the outgoing edges from the incoming edges of a vertex during the graph partition process. We have conducted extensive experiments using real-world datasets, and our results verified the effectiveness of the proposed mechanism. For example, compared with PowerGraph under Random partition scenario L-PowerGraph can not only reduce up to 30.5% of the communication overhead but also cut up to 20.3% of the runtime for PageRank algorithm while processing Live-journal dataset. The performance improvement achieved by L-PowerGraph over our precursor work, LightGraph, which only reduces the synchronizing communication overhead, is also verified by our experimental results. |
Year | DOI | Venue |
---|---|---|
2020 | 10.1007/s11227-018-2359-9 | The Journal of Supercomputing |
Keywords | Field | DocType |
Distributed graph-parallel computing, Big data, Communication overhead | Replica,Vertex (geometry),Computer science,Parallel communication,Synchronizing,Parallel computing,Graph partition,Big data,Performance improvement,Scalability,Distributed computing | Journal |
Volume | Issue | ISSN |
76 | 3 | 1573-0484 |
Citations | PageRank | References |
0 | 0.34 | 32 |
Authors | ||
5 |
Name | Order | Citations | PageRank |
---|---|---|---|
Yue Zhao | 1 | 8 | 2.23 |
Kenji Yoshigoe | 2 | 84 | 13.88 |
Mengjun Xie | 3 | 212 | 23.46 |
Jiang Bian | 4 | 150 | 43.09 |
Ke Xiong | 5 | 579 | 49.96 |