The Library
CGraph : a correlations-aware approach for efficient concurrent iterative graph processing
Tools
Zhang, Yu, Liao, Xiaofei, Jin, Hai, Gu, Lin, Liu, Haikun, He, Bingsheng and He, Ligang (2018) CGraph : a correlations-aware approach for efficient concurrent iterative graph processing. In: 2018 USENIX Annual Technical Conference (USENIX ATC 18), Boston, MA, 11–13 Jul 2018. Published in: USENIX ATC '18: Proceedings of the 2018 USENIX Conference on Usenix Annual Technical Conference pp. 441-452. ISBN 9781931971447.
|
PDF
WRAP-CGraph-correlations-aware-approach-efficient-concurrent-iterative-graph-processing-He-2018.pdf - Accepted Version - Requires a PDF viewer. Download (1566Kb) | Preview |
Official URL: https://www.usenix.org/conference/atc18/presentati...
Abstract
With the fast growing of iterative graph analysis applications, the graph processing platform has 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.
Item Type: | Conference Item (Paper) | ||||||
---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||
Library of Congress Subject Headings (LCSH): | Computer science | ||||||
Journal or Publication Title: | USENIX ATC '18: Proceedings of the 2018 USENIX Conference on Usenix Annual Technical Conference | ||||||
Publisher: | USENIX Association | ||||||
Place of Publication: | Boston, MA | ||||||
ISBN: | 9781931971447 | ||||||
Official Date: | July 2018 | ||||||
Dates: |
|
||||||
Page Range: | pp. 441-452 | ||||||
Status: | Peer Reviewed | ||||||
Publication Status: | Published | ||||||
Access rights to Published version: | Restricted or Subscription Access | ||||||
Date of first compliant deposit: | 24 May 2018 | ||||||
Date of first compliant Open Access: | 24 May 2018 | ||||||
Conference Paper Type: | Paper | ||||||
Title of Event: | 2018 USENIX Annual Technical Conference (USENIX ATC 18) | ||||||
Type of Event: | Conference | ||||||
Location of Event: | Boston, MA | ||||||
Date(s) of Event: | 11–13 Jul 2018 | ||||||
Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year