Research And Implementation Of A Double Partition Structure Graph Processing System On A Single Machine

Nowadays,graph processing is widely used in various fields,such as social networks,Internet of things,and neural networks.Common graph processing systems are divided into graph processing system on a single machine and distributed graph processing system.Distributed graph processing systems have the disadvantages of unbalanced load,expensive communication overhead,and weak robustness.At the same time,in terms of processing large-scale graphs,recent research results show that graph processing system on a single machine can be competitive to the distributed graph processing system.Therefore,graph processing system on a single machine has become the focus of graph processing research.GraphDse is a graph processing system on a single machine,The procedure of GraphDse processing is divided into two phases: a preprocessing phase and an update phase.In the preprocessing phase,GraphDse proposes a structure based on Destination-Average Shard(DAS)and Source-Average Shard(SAS)to store the graph data,this structure ensures the graph data locality and improves CPU efficiency.In the update phase,GraphDse proposes a Double Sliding Edges(DSE)calculation model,which avoids the overhead of synchronization locks or atomic operations and achieves a high degree of parallelism.In the iterative procedure,the vertices are stored in the memory,which reduces the read and write operations on the vertices of the graph on the external memory as well as the amount of I/O transfer.For different types of graph applications,a flexible selective scheduling strategy is proposed,which can skip the execution of one edge even the loading and execution of a shard,leading to significantly reducing the amount of I/O transfer and improving the convergence rate of graph algorithm.We run graph applications(PageRank,BFS,and WCC)on real-world natural graph data and synthesized graph data to perform a large number of experiments.Compared to the state-of-the-art graph processing system GridGraph,experiment results have shown that GraphDse can improve performance significantly.In the preprocessing phase,GraphDse can achieve up to 60.1% performance improvement.In the update phase,for PageRank application,GraphDse can achieve up to 83.0% performance improvement.For BFS application,GraphDse can achieve up to 44.4% performance improvement.For WCC application,GraphDse can achieve up to 86.6% performance improvement.