Research On Locality Mining And Optimization Of Traversal Class Applications In Graph Computing

In the context of big data,the scale of graph data in the physical world has exploded,and applications such as social network analysis,data mining,biological networks,and recommendation systems are closely dependent on graph computing systems.However,due to the unstructured and irregular nature of graph data,when graph computing faces practical problems such as traversal and search,it results in strong randomness and poor locality of memory access.However,the high "memory access calculation ratio" with simple operation and strong real-time performance of graph computing not only requires high bandwidth,but also wastes serious bandwidth.In order to solve this problem and improve the performance of the graph computing system,this paper proposes a graph data reordering algorithm and a novel deep branch reordering double-compressed sparse row data format based on a comprehensive trade-off<graph application,graph data>performance parameter evaluation model.Alleviate the challenges posed by poor locality.Firstly,in order to reveal the differences between different graph computing frameworks,a comprehensive trade-off<graph application,graph data>performance parameter evaluation model is constructed to form a sufficient criterion for graph computing framework analysis.Select workloads and representative datasets to conduct in-depth analysis and research on Ligra,Gemini,and GraphBIG graph computing frameworks.Focusing on the factors that affect the performance of the graph computing system,including graph data structure information,the specific implementation of graph computing applications,and the performance indicators of the graph computing system,perf is used to conduct performance measurement and characteristic analysis for various real graphs,and then build a graph-based computing framework.Locality performance evaluation model.The exprimental results show that the Gemini framework has the best performance in terms of execution time and computation volume,Ligra has the best performance in terms of data movement,and the GraphBIG framework has the worst performance,especially in terms of cache miss rate and execution time.Secondly,to solve the problems of strong randomness and poor locality of data access in the implementation of graph applications,a deep branch reordering algorithm based on locality features is proposed.According to the constructed performance evaluation model,hierarchical community and deep community locality mining is carried out for traversal applications,and the potential locality of data is discovered.Based on this,a deep branch reordering algorithm is proposed to compare and analyze the algorithm performance and mining results.The experimental results show that when the reordering algorithm takes the dataset Amazon as the input data,the sorting process consumes the shortest time and has the best performance.The time overhead of the DBR algorithm is 36.6%lower than that of the Gorder algorithm,and 10.6%lower than that of the SeqDFS algorithm.In terms of cache hit rate,the DBR algorithm is significantly higher than the two.Using the Wiki dataset as the input data for BFS applications,the L1 cache miss rate of the DBR algorithm is 18.6%better than that of the Gorder algorithm and 13.5%better than that of the SeqDFS algorithm.Thirdly,according to the performance requirements of traversal applications,an appropriate data organization format is selected to improve the performance of graph computing systems,and a new graph data organization format DBR_DCSR is designed.Research the relationship between traversal applications and different data organization formats,including COO,CSC,CSR,DCSC,CSCI.According to the memory usage and performance test results of different organization formats,a new graph data organization format DBR_DCSR is designed,and its performance is compared,verified and analyzed.The experimental results show that the DCSC compression format effectively improves the memory storage efficiency,the CSR compression format effectively reduces program execution time,data movement and energy consumption,and the DBR_DCSR compression format reduces the memory usage by 8.2%～11.9%compared to the DCSC compression format with the lowest memory usage.Finally,in order to ensure the efficiency of the local optimization scheme,the GraphBIG graph computing framework is selected for testing and verification.Build a test environment based on a high-performance server and design an overall verification scheme.Compare and analyze the performance of data movement,computation,execution time and cache miss rate with the current typical graph computing framework.The experimental results show that the locality performance of the DBR_DCSR compression algorithm achieved by the traversal class application on GraphBIG is the best.Taking the CA dataset as the input data to implement the BFS application,the execution time of GraphBIG_DBR_DCSR is reduced by 17.6%compared with the DBG algorithm and 8.7%compared with the LBR algorithm.Compared with the original data of Ligra and Gemini frameworks,it is reduced by 56.4%and 11.1%respectively.In terms of data movement,GraphBIG_DBR_DCSR is 7.4%and 28.6%less than the original data of Ligra and Gemini frameworks,respectively.In terms of cache miss rate,GraphBIG_DBR_DCSR is 19.7%and 15.6%lower than the original data of Ligra and Gemini frameworks.