Dependency-aware Incremental Processing Accelerator For Directed Evolving Graph

The update dependency in the evolving directed graph is that the state of the destination vertex depends on the state of the source vertex on the same edge.It has following characteristic,i.e.,the vertices can quickly propagate their new states to others along the directions of update dependencies only when they are asynchronously handled along their order on these directions within each round in a sequential way.However,existing graph frameworks and graph accelerators are not aware of such a characteristic of update dependencies at runtime.As a result,existing methods cannot achieve fast convergence speed at a low preprocessing overhead when performing incremental processing on evolving directed graphs.Motivated by above challenges on evolving directed graph,a dependency-aware directed graph asynchronous execution model is proposed.First,to eliminate the preprocessing overhead on dependency extraction,a runtime dependency extraction method is designed to dynamically determines the next vertex to traverse according to the currently processed vertex and then it forms a local topological vertex sequence with the traversed vertices on the evolving directed graph.Second,to use the update dependency information at runtime,a dependency-aware asynchronous iterative graph processing method is designed to dynamically dispatches the processing order of vertices according to the local topological vertex sequence,and then asynchronously processes vertices to accelerate vertex state propagation,which can effectively reduce the number of redundant vertex updates.Based on above model,an evolving directed graph incremental processing accelerator,Graph HP is proposed to further reduce the runtime overhead.A runtime dependency-aware strategy is implemented to offload the dependency extraction method to hardware scheduler,which efficiently reduces runtime overhead.Graph HP performs exact prefetching for vertex and edge data to reduce access latency of graph structure data.It simultaneously performs runtime dependency extraction methods and dependency-aware asynchronous iterative graph processing methods by decoupling hardware datapath,which shortens the critical path.The experimental results show that,compared with traditional asynchronous graph processing method,when performing different directed graph algorithms on the evolving directed graph,the speedup of Graph HP is up to 2.7 times,the number of vertex updates is reduced by up to 70%.