An Optimization Mechanism For Asynchronous Incremental Computation On Dynamic Graph Processing

In dynamic graph processing systems,it is important to keep the results of graph computation up-to-date.Incremental computation is demonstrated to be an efficient solution to update calculated results.It reuses the result of the prior computation to accelerate convergence of a graph.However,these solutions still suffer from sub-optimal convergence speed,since they not only ignore the influence of some important vertices(important to convergence speed)to the state propagation efficiency,but also ignore the inherent connection between the vertices.The random distribution of data leads to a high communication cost between data partitions,and at the same time,it increases random access and reduces system performance.In order to solve the problem that the existing asynchronous incremental graph processing system lacks of effective graph partitioning method and scheduling method,we propose a novel graph processing optimization framework based on asynchronous delta-based accumulative iterative computation model.It first introduces a dynamic graph partitioning method based on important vertices.Since a few important vertices in a natural graph are easily accessed at high frequencies during iterative computation,the dynamic graph partitioning method adopts the strategy of gathering important vertices and their adjacent edges to hot chunks.It further improves access locality by managing each partition with data chunks.On the basis of dynamic graph partitioning method,the optimization framework then proposes a priority-based scheduling algorithm.It assigns some chunks that have a significant influence on the state change propagation with a higher priority for accelerating the state change propagation efficiency.In iterative graph processing,by using the optimization framework,these important vertices inside a partition will have a better locality,and the state propagation efficiency of vertices will increase.The experimental results show that the designed framework can operate stably,and it is able to reduce the number of updates and increase the locality,thereby reducing the convergence time.Compared with state-of-the-art systems,our method reduces the number of updates by 30%,and reduces the total execution time by 35%.