CGraph: A Correlations-aware Approach for Efficient Concurrent Iterative Graph Processing

Authors: 

Yu Zhang, Xiaofei Liao, Hai Jin, and Lin Gu, Huazhong University of Science and Technology; Ligang He, University of Warwick; Bingsheng He, National University of Singapore; Haikun Liu, Huazhong University of Science and Technology

Abstract: 

With the fast growing of iterative graph analysis applications, the graph processing platform have to efficiently handle massive Concurrent iterative Graph Processing (CGP) jobs. Although it has been extensively studied to optimize the execution of a single job, existing solutions face high ratio of data access cost to computation for the CGP jobs due to significant cache interference and memory wall, which incurs low throughput. In this work, we observed that there are strong spatial and temporal correlations among the data accesses issued by different CGP jobs because these concurrently running jobs usually need to repeatedly traverse the shared graph structure for the iterative processing of each vertex. Based on this observation, this paper proposes a correlations-aware execution model, together with a core-subgraph based scheduling algorithm, to enable these CGP jobs to efficiently share the graph structure data in cache/memory and their accesses by fully exploiting such correlations. It is able to achieve the efficient execution of the CGP jobs by effectively reducing their average ratio of data access cost to computation and therefore delivers a much higher throughput. In order to demonstrate the efficiency of the proposed approaches, a system called CGraph is developed and extensive experiments have been conducted. The experimental results show that CGraph improves the throughput of the CGP jobs by up to 2.31 times in comparison with the existing solutions.

Open Access Media

USENIX is committed to Open Access to the research presented at our events. Papers and proceedings are freely available to everyone once the event begins. Any video, audio, and/or slides that are posted after the event are also free and open to everyone. Support USENIX and our commitment to Open Access.

BibTeX
@inproceedings {216081,
author = {Yu Zhang and Xiaofei Liao and Hai Jin and Lin Gu and Ligang He and Bingsheng He and Haikun Liu},
title = {CGraph: A Correlations-aware Approach for Efficient Concurrent Iterative Graph Processing},
booktitle = {2018 {USENIX} Annual Technical Conference ({USENIX} {ATC} 18)},
year = {2018},
isbn = {978-1-939133-01-4},
address = {Boston, MA},
pages = {441--452},
url = {https://www.usenix.org/conference/atc18/presentation/zhang-yu},
publisher = {{USENIX} Association},
month = jul,
}

Presentation Audio