Parallel Algorithm Design For Super-large-scale Graph Partition

Graph partition is a classic graph-theoretical and combinatorial optimization problem,which can be widely used in VLSI design,protein molecular structure design,high-performance computing and so on.At present,with the continuous increase of the data size and the continuous improvement of computing power,the graph that needs to be divided becomes larger and larger,and the number of vertices can reach 100 million or more.It is impractical to use the existing serial algorithm to solve the problem of super-large-scale graph partitioning.Therefore,it is urgent to solve this problem by using parallel method.This thesis mainly studies the design of parallel algorithm for super-large-scale graph partitioning,and applies it to CGNS(CFD(Computational Fluid Dynamics)General Notation System))grid partitioning.First,We introduce the previous graph partitioning algorithm,and design a new parallel super-large-scale graph partitioning algorithm to make it strong scalable and suitable for graph with scale of 100 million or more.Second,we studies the load balance partition problem on superlarge-scale CGNS computing grid,a practical application scenario for graph partition problem.For this problem,we give a grid-to-graph algorithm,which can quickly convert the CGNS grid data into graph data,and use the algorithm designed to divide the graph,so as to complete the load balancing partition of the super-large-scale CGNS computing grid.Then,we implement the designed algorithm on personal computer and super-computer respectively,and select grid data of different magnitudes for experiments.It can be seen from the experimental results that the grid conversion algorithm designed in this thesis can effectively convert the CGNS grid data into the corresponding graph data; compared with the serial algorithm of graph partitioning,the super-large-scale graph partitioning parallel algorithm designed in this thesis works well,the load imbalance rate is basically the same as the serial result,the parallelism reaches 50%,and the scalability is strong.Furthermore,Fennel,a streaming graph partitioning algorithm,and its distributed algorithm are introduced,and a parallel algorithm to ensure the partition effect is designed.Through serial experiments,thread parallel experiments and process parallel experiments,it is found that under the premise of ensuring the partition effect,the parallelism of the parallel algorithm is limited; if the parallelism of the algorithm is to be greatly improved,the division effect needs to be lost to a certain extent.At last,we concludes this thesis and looks forward to future research work.