A disk I/O optimized system for concurrent graph processing jobs  

作　　者：Xianghao XU Fang WANG Hong JIANG Yongli CHENG Dan FENG Peng FANG 

机构地区：[1]School of Computer Science and Engineering,Nanjing University of Science and Technology,Nanjing 210094,China [2]Wuhan National Laboratory for Optoelectronics,Huazhong University of Science and Technology,Wuhan 430074,China [3]Department of Computer Science&Engineering,University of Texas at Arlington,Arlington,TX 76019,USA [4]College of Computer and Data Science,Fuzhou University,Fuzhou 350108,China [5]Zhejiang Lab,Hangzhou 311121,China

出　　处：《Frontiers of Computer Science》2024年第3期13-29,共17页中国计算机科学前沿（英文版）

基　　金：supported by the National Natural Science Foundation of China(Grant Nos.61832020,61821003 and U1705261);National Defense Preliminary Research Project(No.31511010202);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.

关 键 词：graph processing disk I/O concurrent jobs 

分 类 号：TP333[自动化与计算机技术—计算机系统结构] TP338.6[自动化与计算机技术—计算机科学与技术]