Multi-Task External Memory Graph Processing System Based On I/O Scheduling

Graph processing systems are widely employed in many areas,such as online social network and community discovery,etc.With the increasing of the scale of graph datasets,the execution time of graph algorithms are longer and longer,and multitasking scene is more and more common.Current external-memory graph processing system can effectively execute single graph tasks,However,in a multitasking scenario,each graph algorithm has a different I/O characteristics,which will affect and even destroy the existing I/O optimization method and cause serious external random access overhead.In addition,each graph algorithm initiates the I/O request to the external disks separately and will compete for limited I/O bandwidth and will aggravate the I/O conflict.In order to address the problem of current external-memory graph processing system occurring in the multitasking scene,this paper proposes multi-task graph processing I/O model based on multiple external storage rescheduling and implement GraphScSh,a multitasking external-memory graph processing system.By employing multiple peripherals to storage graph data and taking full advantage of I/O bandwidth for multiple devices,the I/O pressure is evenly distributed to each disk.In addition,the conflict of I/O is effectively mitigated by controlling the access order of graph data stored in multiple devices in the procedure of processing multitasks.What is more,based on the idea of sharing graph data,GraphScSh priority access the graph partition data,that has been loaded into memory,which can reduce repeated loading of the same graph data,and increase the effectiveness of I/O.The extensive experiments of various algorithm combinations running on the graph datasets with different features and sizes demonstrate that the executing time of GraphScSh is less than GridGrph for 92% of all the algorithm combinations,and the percentage of performance improvement increases with the increase of parallelism.Additionally,the comparison test results with the system GraphDeSh show that GraphScSh avoid the synchronization overhead problems of GraphDeSh,The execution time increase percentages of different test data sets were up to 34.12%?19.24% and 12.68%.