In order to analyze and process the large graphs with high cost efficiency,researchers have developed a number of out-of-core graph processing systems in recent years based on just one commodity computer.On the other ...In order to analyze and process the large graphs with high cost efficiency,researchers have developed a number of out-of-core graph processing systems in recent years based on just one commodity computer.On the other hand,with the rapidly growing need of analyzing graphs in the real-world,graph processing systems have to efficiently handle massive concurrent graph processing(CGP)jobs.Unfortunately,due to the inherent design for single graph processing job,existing out-of-core graph processing systems usually incur unnecessary data accesses and severe competition of I/O bandwidth when handling the CGP jobs.In this paper,we propose GraphCP,a disk I/O optimized out-of-core graph processing system that efficiently supports the processing of CGP jobs.GraphCP proposes a benefit-aware sharing execution model to share the I/O access and processing of graph data among the CGP jobs and adaptively schedule the graph data loading based on the states of vertices,which efficiently overcomes above challenges faced by existing out-of-core graph processing systems.Moreover,GraphCP adopts a dependency-based future-vertex updating model so as to reduce disk I/Os in the future iterations.In addition,GraphCP organizes the graph data with a Source-Sorted Sub-Block graph representation for better processing capacity and I/O access locality.Extensive evaluation results show that GraphCP is 20.5×and 8.9×faster than two out-of-core graph processing systems GridGraph and GraphZ,and 3.5×and 1.7×faster than two state-of-art concurrent graph processing systems Seraph and GraphSO.展开更多
基金supported by the National Natural Science Foundation of China(Grant Nos.61832020,61821003 and U1705261)National Defense Preliminary Research Project(No.31511010202)+3 种基金the Fundamental Research Funds for the Central Universities,the Open Project Program of Wuhan National Laboratory for Optoelectronics(No.2022WNLOKF017)the Natural Science Foundation of Fujian Province(No.2020J01493)Zhejiang provincial“Ten Thousand Talents Program”(No.2021R52007)Center-initiated Research Project of Zhejiang Lab(No.2021DA0AM01).
文摘In order to analyze and process the large graphs with high cost efficiency,researchers have developed a number of out-of-core graph processing systems in recent years based on just one commodity computer.On the other hand,with the rapidly growing need of analyzing graphs in the real-world,graph processing systems have to efficiently handle massive concurrent graph processing(CGP)jobs.Unfortunately,due to the inherent design for single graph processing job,existing out-of-core graph processing systems usually incur unnecessary data accesses and severe competition of I/O bandwidth when handling the CGP jobs.In this paper,we propose GraphCP,a disk I/O optimized out-of-core graph processing system that efficiently supports the processing of CGP jobs.GraphCP proposes a benefit-aware sharing execution model to share the I/O access and processing of graph data among the CGP jobs and adaptively schedule the graph data loading based on the states of vertices,which efficiently overcomes above challenges faced by existing out-of-core graph processing systems.Moreover,GraphCP adopts a dependency-based future-vertex updating model so as to reduce disk I/Os in the future iterations.In addition,GraphCP organizes the graph data with a Source-Sorted Sub-Block graph representation for better processing capacity and I/O access locality.Extensive evaluation results show that GraphCP is 20.5×and 8.9×faster than two out-of-core graph processing systems GridGraph and GraphZ,and 3.5×and 1.7×faster than two state-of-art concurrent graph processing systems Seraph and GraphSO.
