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 toits ease of use and programming. However, when dealing with asynchronous graph analytics,frameworks based on vertex programming perform inefficiently. The reason is that first, vertexprogramming must guarantee the sequential consistency, which means frequent use of locksor atomic operations, and second, the algorithms are parallelized in vertex level and latentparallelismof the algorithms cannot be exploited. To improve parallel efficiency of asynchronousgraph processing, the Gauss-Seidel style algorithms in particular, this paperproposes a schedulingmodel using Gauss-Seidel-based matrix computation, which converts the vertex programminginto two main matrix operations and then algorithms are parallelized by row and columnvectors. Compared to vertex programming, our model parallelizes algorithms in a finer wayto exploit more latent parallelism, while retains the ease-of-programming advantage of vertexprogramming. Instead of using locks to guarantee the sequential consistency, our model uses ahybrid synchronization policy to reduce serializability among threads and overheads of contextswitching. Furthermore, this model strengthens locality of the program. Experiment results showthat our model outperforms vertex-centric asynchronous frameworks in both performance andscalability. Moreover, it even surpasses the matrix-based synchronous framework GraphMatwith some non-Gauss-Seidel style algorithms.