面向动态有向图的单调图算法硬件加速机制

An efficient hardware accelerator for monotonic graph algorithms on dynamic directed graphs

随着现实世界中动态图计算需求的快速增长,现有的研究工作已经提出了多种方法来有效支持单调图算法在动态有向图中的处理.然而,由于动态有向图的图结构频繁发生变化,其相邻图顶点之间的状态更新存在复杂的依赖关系,这使得现有的软硬件方法在处理单调图算法时依然面临着数据访问成本高和收敛速度慢的问题.为此,本文提出了一种面向动态有向图的单调图算法加速器DSGraph,它能够充分利用图顶点之间的依赖关系来加快单调图算法在动态有向图处理中的收敛速度,并有效降低数据访问成本.具体来说,DSGraph通过实时提取动态有向图中图顶点的局部拓扑依赖顺序来执行异步迭代处理,从而显著减少冗余的图顶点状态更新.同时,DSGraph设计了一种异步迭代流水线架构,其按照依赖顺序对图顶点状态进行异步迭代处理,从而加速图顶点状态传播速度并减少数据访问开销.最后,DSGraph提出了一种无阻塞数据同步机制,通过并行执行本地图顶点的状态更新和外部图顶点的数据同步来减少系统同步开销.实验显示,与目前最先进的面向单调图算法的动态图处理系统KickStarter相比,DSGraph将动态有向图处理速度平均提升了11.2倍.

With the rapidly growing demand for dynamic graph processing in the real world,existing research has proposed various methods to efficiently support the processing of monotonic graph algorithms on dynamic directed graphs.Despite of many research efforts,for iterative analysis of evolving directed graphs,existing solutions suffer from slow convergence speed and high data access cost,because many vertices are ineffectively reprocessed for lots of rounds so as to update their states according to other active vertices regardless of their dependencies.In this paper,we propose a novel and efficient accelerator DSGraph for incremental processing of dynamic directed graphs for monotonic graph algorithms.Compared with existing methods,the unique feature of DSGraph is that it can efficiently take advantage of the dependencies between the vertices to reduce the data access cost and improve the convergence speed of iterative processing of dynamic directed graphs.Specifically,DSGraph performs asynchronous iterative processing according to the topological dependency order of vertices on dynamic directed graphs at runtime,thus significantly reducing redundant vertex state updates.Meanwhile,DSGraph designs a multi-stage pipeline architecture.It performs asynchronous iterative processing of vertices according to the dependency order,which speeds up the vertex state propagation and reduces the data access overhead.Finally,DSGraph proposes a non-blocking data synchronization mechanism to reduce the system synchronization overhead by performing state updates of local vertices and data synchronization of external vertices in parallel.Experimental results show that DSGraph speeds up iterative dynamic graph processing by 11.2 times on average in comparison with the state-of-the-art software dynamic graph processing systems.