Research On Graph Data Layout And Access Optimization Based On Application Operating Characteristics

Graphs are very important unstructured data that can be used to model various problems in the real world and are widely used in important areas such as transportation,finance,and social networking.However,due to the severe structural dependence in the graph computing process,memory random access is severe when the application is executed,and the memory bandwidth becomes an important factor in limiting the performance of the graph computing system.Moreover,the memory access characteristics of different types of graph algorithms are significantly different.A single memory graph data layout is not enough to meet the diverse memory access requirements of various graph algorithms.To solve the above problems,analyze the dynamic running characteristics and the difference of memory data access of common graph algorithms,and divide graph algorithms into traversal and iterative,study the efficient graph data organization strategy under different executing characteristics.Specifically,for the traversal graph algorithm,by analyzing its operation process,it is found that there is a difference of correlation between the same vertex and different neighboring nodes,and the access order to the neighboring nodes is an important factor affecting the Cache hit ratio during the operation of the algorithm.Based on this,a graph vertex remapping algorithm GDL-VC based on relevance degree is proposed,and the sliding window model SW is used to achieve reasonable layout of memory graph data.The layout results can reflect the structural characteristics of the graph,make the distribution of the associated vertex IDs appear local and orderly,and reduce memory random access during graph algorithm running.For the iterative graph algorithm,by analyzing the convergence characteristics of the algorithm,it is found that the "super-vertex" in the graph structure can not reach the convergence state for a long time,which results in the long tail phenomenon applied to the iterative graph algorithm.For this reason,a graph vertex remapping algorithm GDL-DR based on influence is proposed.The layout algorithm completes the layout of graph data according to the vertex influence(vertex degree).In the late execution of the graph algorithm,when the state of the active vertex is about to update,the associated neighbor nodes are compactly distributed,which can reduce memory random access,make the vertices reach the convergence state faster,and shorten the application execution time.The test results show that: The GDL-VC layout algorithm can improve the average memory access efficiency by 25.4% and 27.5% for traversal graph applications(ConnectedComponent,Single-Source Shortest Path),some data sets exceed 50%.The GDL-DR layout algorithm can increase the average memory access efficiency by 23.9% and 17.1% for iterative graph applications(PageRank,Label Propagetion Algorithm)with a maximum increase percentage of 42.9%.For the GridGraph test platform,both layout algorithms can bring average system performance improvements of over 35%,and the system acceleration ratio both reach 1.5×,and part of the graph data exceeds 2×.The Cache hit rate is increased to 90%.