Research On External Memory Based I/O Deduplication Optimized Multi-Task Graph Processing System

Graph processing systems have been widely used in various fields of data analysis, with the fast growing of graph processing tasks, they have to efficiently deal with multi-task environments. However existing graph processing systems are designed for single task, duplication of graph data and competition of data access bandwidth occur in the execution of concurrent tasks.Due to the exchange data between nodes of in-memory mode graph processing system belongs to each task privately, network bandwidth is the bottleneck of the system when executing multiple tasks. Although existing external-memory mode graph processing system can avoid network communication cost, inconsistence of data access from multiple tasks could easily lead to I/O duplication and impact on performance. Through the analysis of I/O optimization methods of existing external-memory mode graph processing system, a data access model based on I/O deduplication and graph sharing is proposed, and advantages and limitations is discussed comparing the new model with traditional model. Based on this model, we have designed and implemented a multi-task external-memory mode graph processing system named GraphDeSh. GraphDeSh eliminates I/O duplication through uniform data access to external memory, balances the difference between executing speed of multiple tasks, and optimizes data waiting time.We have tested GraphDe Sh using different datasets and different combinations of graph algorithms and verified the validity of I/O deduplication and graph sharing model. Test results show that speedup of GraphDeSh with two tasks have reached 2 compared to traditional parallel model. The optimization effect declines with the rise of graph algorithms' compution ratio, and the average speedup is 1.45. Compare GraphDeSh with parallel GraphChi and X-Stream on different datasets, the speedup increases the maximum 60.7% and 107.1%, at least 32.5% and 84.5%.