A High Performance Graph Processing System Based On Low-redundancy Iteration Model

Graph structure is an abstract form of real world in some senarios.Graph processing is a way to analyze the real world,which has strong practical significance.Today's graph processing systems are mostly based on synchronous or asynchronous iterative model.These traditional iterative model have much computing redundancy because of the Cannikin Law of convergence.In the days of big data,huge amout of graph data bring much more computing redundancy,render inefficient processing speed and computing resources waste.SCC-DAG(Directed Acyclic Graph composed of Strongly Connected Components)iterative model abstracts graph data to a DAG which is composed by many SCCs.The iterative model regards SCC as an iteration unit and performs iteration inside SCC until the SCC convergence.And the order of SCC iteration performed is according to SCC-DAG.In this case,the SCC-DAG iterative model can reduce much computaing redundancy.The implementation of high parallel out-of-core graph processing system based on SCC-DAG iterative model has two aspects.One is a high parallel solution based on SCC-DAG iterative model,the other is an out-of-core solution based on SCC-DAG iterative model.The high parallel solution proposes a level algorithm to parallel the calculation among SCC and adopts path-centric graph parallel computation model inside SCC.To be load balanced,the solution adopts different parallel strategy between big SCC and small SCC.The out-of-core solution uses memory mapping mothod to access graph data and design a compressed storage format based on SCC-DAG.These method brings efficient data access and less I/O operation.The experiment results show that,compared with traditional iterative models,the SCC-DAG iterative model can reduce computing redundancy.The high parallel out-of-core graph processing system based on SCC-DAG iterative model has good scalability and high out-of-core performance.Compared with the mainstream graph processing systems,the system has accepted preprocessing time and less execution time.