On The Optimization Of Storage Structure And Memory Access Of Graph Traversal For Graph500

The advancement information technology has promoted the development of our society.The emerging industries have generated more and more sophisticated data,and the output data volume of each industryis changing dramatically.The rapid growth of data promotes the demand for big data analytics and high performance computing technologies.The graph processing method is widely used in the processing of big data in various fields.Breadth First Search(BFS)Algorithm is a classic graph problem,and also serves as a core test program for the Graph500 benchmark.Similar to the big data problem,the BFS algorithm has the characteristics of large data access and low calculation complexity.In addition,BFS algorithm often shows memory access irregularity,and poor locality in time and space,these problems further cause the computer's Cache failure rate to rise.So that,the Graph500 cannot meet the requirements of high efficiency and high performance;Moreover,the scale of the tested generated graph of is huge,so the programs often with the problem of data cross-border due to insufficient computer memory.In order to solve these problems two aspects on Memory and access be optimized to further improve the calculation efficiency of the Graph500 benchmark test program,and reduce the consumption of memory space while the program is running.For memory optimization,we adopt the method of compressing the data type length of the graph variables to generate the new graph.For memory access optimization,the format allocation program for generating graph data is downgraded,so the effective data on each Cache line will be increased during data transmission,and the addressing ability of the CPU can be improved.This thesis mainly focuses on the optimization design of the Graph500 benchmark program installed and running on a single node server,from two aspects: the memory space consumption by compressing the length of variable data types in the generated graph,and downgrade the data allocation program to improve the utilization of Cache,thus improving the addressing ability of CPU.The test results of Graph500 installed on the Baode server show that the optimized program saves 33.33% of memory space compared with before the optimization;And the test results under standard input conditions show that the maximum traversal speed max_GTEPS of the test program in omp-csr format is increased to 1.8 times before optimization,and the max_GTEPS in the seq-csr format test program is 2.238 times before optimization.Finally,the optimized program is installed on three different servers for peak value and data cross-border test to further verify the optimization effect.The peak value test results show that the computing performance of Graph500 is affected by the Cache capacity and CPU frequency;the peak value of the optimized Graph500 program's omp-csr format test program can reach about 3 times before optimization.