Improving parallel efficiency for asynchronous graph analytics using Gauss-Seidel-based matrix computation

Graph analytics is extensively used in big-data applications such as social networks, web analysis, bio-informatics, etc. Most graph processing frameworks adopt vertex-centric model due to its ease of use and programming. However, when dealing with asynchronous graph analytics, frameworks based on vertex programming perform inefficiently. The reason is that first, vertex programming must guarantee the sequential consistency, which means frequent use of locks or atomic operations, and second, the algorithms are parallelized in vertex level and latent parallelism of the algorithms cannot be exploited. To improve parallel efficiency of asynchronous graph processing, the Gauss-Seidel style algorithms in particular, this paper proposes a scheduling model using Gauss-Seidel-based matrix computation, which converts the vertex programming into two main matrix operations and then algorithms are parallelized by row and column vectors. Compared to vertex programming, our model parallelizes algorithms in a finer way to exploit more latent parallelism, while retains the ease-of-programming advantage of vertex programming. Instead of using locks to guarantee the sequential consistency, our model uses a hybrid synchronization policy to reduce serializability among threads and overheads of context switching. Furthermore, this model strengthens locality of the program. Experiment results show that our model outperforms vertex-centric asynchronous frameworks in both performance and scalability. Moreover, it even surpasses the matrix-based synchronous framework GraphMat with some non-Gauss-Seidel style algorithms.