A Fast Parallel Graph Processing System For NVMe SSD Based On Lock-free Multiqueues

With the rapid growth of the complexity and scale of graph data,low-cost and easily expandable external memory graph processing systems have become a popular alternative to in-memory graph processing systems.The cost of emerging storage devices,including NVMe SSDs,continues to drop,while providing good performance,bringing new challenges and opportunities to external memory graph processing systems.When the existing graph processing system uses NVMe SSD as external memory,there are problems such as lock contention overhead,limited parallel I/O capability,and insufficient bandwidth utilization,and cannot fully utilize the I/O performance of NVMe SSD devices.To solve the above problems,we adopt the strategy of parallelizing I/O and computing.We proposes SMRP computing model that supports parallel computing and parallel I/O,realizes asynchronous data loading-computing-update.We manage computation and I/O using lock-free multi-queue.In order to overlap I/O and computing,we have designed streaming cache management method based on sliding window.In order to reduce the software overhead in the read and write accesses of NVMe SSD,we use IO＿Uring to implement a lock-free zero-copy graph processing I/O method.Then we have designed and developed Graph NS,a fast parallel graph processing system for NVMe SSD based on lockfree multiqueues.We use Graph NS,Gra FSoft and Flash Graph to test the execution time of three graph algorithms including Page Rank,WCC and BFS,and the corresponding NVMe SSD I/O bandwidth on different graphs.Experimental test results show that in terms of the performance of the execution test algorithm,Graph NS is improved by 37%～90.4% relative to Gra FSoft,and by 14.2%～57.8% relative to Flash Graph.For the same test algorithm,the average I/O throughput of Graph NS is 5.89～75 times that of Gra FSoft and 1.50～3.79 times that of Flash Graph.The above results show that Graph NS,compared with the existing stand-alone NVMe SSD graph processing system,can take advantage of the high bandwidth of the NVMe SSD,and performance has been effectively improved.