Accelerating Graph Traversal By Graph Ordering

With the development of computer technology,graphs have been widely used in many areas,such as bioinformatics,mathematics,computer science,physics,and chemistry.The corresponding graph algorithms turn to be the kernel for solving many realistic problems.The overheads of graph algorithms could be divided into 1)the graph traversal overheads and 2)the computing overheads.Although the optimization of the graph algorithms has been studied for decades,subject to the graph structure and the special execution model,the graph algorithms'traversal performance could hardly be improved.The thesis studies traversal acceleration algorithms for I/O intensive graph applications based on the background mentioned above.The thesis mainly solves three challenges:1)nodes sorting method for depth-first traversal and sequence first traversal algorithm,2)vertices sorting algorithm and vertex sorting model for breadth-first traversal,3)reachable query method based on traversal acceleration.Among the three aspects of the research,the vertex sorting method for specific memory access features is the basis of all the research in this paper.It provides a basic and efficient optimization strategy,which can significantly improve the data locality during algorithm execution,and then designs a more efficient traversal algorithm and model on this basis.The contribution of our methods is listed below:First,this thesis proposes to use the DFS tree to speed up the DFS procedure.The thesis proposes transforming the graph into a DFS sequence and presenting a new method to speed up the traversal.Based on greedy strategy,the method tries to cover as many edges as possible,and a Maximum cover DFS sequence is constructed.Furthermore,this thesis proposes a new DFS method that could use the DFS tree information.The tree edges and non-tree edges will be processed in different manners.We could improve performance from better data locality and branch prediction accuracy.Finally,the thesis proposes a sequence maintenance algorithm based on dynamic graphs.To the best of my knowledge,it is the only method supporting sequence maintenance in dynamic graph scenarios.The experiments show that the proposed method could significantly improve the DFS performance and perform well in sequence maintenance.Second,this thesis proposes a new graph ordering model that could improve the performance of breadth-first search(BFS).Compared with the DFS,BFS has a different memory access pattern,and it relies more on sibling relationships.Thus,this thesis presents the Maximum Overlap(MO)method.It improves the BFS performance from two aspects.First,nodes will be processed according to their visit frequency.Nodes that are frequently visited will be processed in priority.Second,maximize the overlap of common child nodes.Nodes that share more common father nodes will be clustered together.As the memory copy and moving is expensive,we adapt a linked array to simulate the graph ordering procedure.According to the experiments,the proposed method could achieve comparable performance with the state-of-the-art methods,while the preprocessing overheads are only 1/15.Third,this thesis presents graph-ordering-based methods to speedup strongly connected components(SCC)detection,bridge detection,and reachability query.This thesis proposes a new strategy for SCC detection and bridge detection to eliminate the node visit state checking.Thus,it could significantly improve branch prediction accuracy.According to the experiments,for SCC detection and bridge detection,the method could achieve an average speedup of more than 2x.Furthermore,reachability queries is used to validate the proposed method's efficiency.Following the state-of-the-art method,Label+G strategy is adopted.Most of the reachability queries will be answered by the index.Then,pruned graph traversal will be executed for the other queries that the index could not answer.Experiments prove that the proposed method is more effective in dynamic scenarios.Compared with the state-of-the-art methods,the proposed method could be an order of magnitude faster.