Graph Processing Research On Single Multi-core Systems

Graph-based applications become more and more common due to the rising of all kinds of online social networks.How to analyse,debug and develop an agile graph processing system becomes one of the most urgent problems facing systems researchers.Though some approaches have been proposed,however,these approaches still have some unresolved problems.For example,the distributed approaches have load balancing,communication latency and the cost issues.While the low degree of the concurrency and the poor fault-tolerant remains in the single machine approaches.Motivated by this,in this paper,we introduce GPSA(a Graph Processing System with Actors),a single-machine graph processing system based on a parallel BSP(Bulk Synchronous Parallel)computation model with actors by considering the compatibility,convenience and fault-tolerant.First,GPSA takes advantage of actors to improve the concurrent degree and the throughput on a single machine,which could not only make full use of multi-core but also avoid the performance loss caused by the frequent context switching.Second,GPSA improves the BSP model.The traditional BSP based system has two main procedures: the computing and the message dispatching.Because of the locality of the graph processing,the two procedures in the vertex-centric implementation are executed sequentially.GPSA improves the BSP computation model to fit actor programming model by decoupling the message dispatching procedure from computing procedure to remove the dependencies of two adjacent superstep and making the two procedures executed parallelly.At last,GPSA optimizes the I/O by separating the graph into two parts: the vertex data and the edge data.For the vertex data,GPSA exploit memory mapping to improve the IO performance to avoid frequent data loading or unloading operation by mapping the vertex into memory and store the edge data in the disk which is accessed sequentially.We show,through experiments and theoretical analysis,processing large-scale graph on a single machine with GPSA could not only improves the performance but also gains fault-tolerant and flexibility.