【作者】 肖威；

【导师】 华强胜；

【作者基本信息】 华中科技大学 ， 计算机软件与理论， 2018， 硕士

【摘要】 在动态图处理系统中,保持图计算结果实时更新至关重要,增量计算能重用历史计算结果来保持计算结果实时更新。然而,现有的异步增量图处理系统仍受限于欠佳的图计算收敛速度,这是因为它们忽略了一些重要顶点(对图收敛速度很重要)对状态传播效率的影响,而且它们忽略了顶点之间的固有连接性,数据的随机分布使得各数据分区之间的通讯开销大大增加,同时也增加了随机访问,降低了系统性能。面向动态大图异步增量计算的优化机制在原异步增量计算系统上设计实现了一个新的优化框架,着重解决现有异步增量图处理系统缺乏有效的图划分方法与调度方法的问题。首先,该优化框架提出了一种基于重要顶点的动态图划分方法,由于图中的少数重要顶点在迭代计算过程中容易被高频访问,该方法采用优先集中放置重要顶点及其关联的边的策略,以数据块管理各个分区,使得迭代计算具有较好的局部性。然后,在基于重要顶点的动态图划分方法的基础上,该优化框架提出了一种基于数据块的优先级的调度策略,该调度策略优先选择更具有传播影响力的数据块进行处理,能有效提高顶点状态传播效率。图迭代计算过程中,通过使用该优化框架,分区内的重要顶点将拥有更好的局部性,顶点状态传播效率将会增加。实验表明,面向动态大图异步增量计算的优化机制能在原系统上正确稳定运行,有效地减少迭代计算更新次数,增加局部性,减少图计算收敛时间。相对于原系统,顶点总体迭代更新次数减少了30%,总体计算时间减少了35%。更多还原

【Abstract】 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%.更多还原