Research Of Multilevel Hypergraph Partitioning Algorithms And Its Application In Large-scale Parallel CFD Computations

With the rapid development of high performance computer systems and improvement of the numerical methods, parallel computing has become a basic supporting technology for solving large-scale scientific and engineering problems. The primary task of large-scale parallel computing is to allocate computing resources more reasonably. On the one hand, we hope to reduce idle time by balancing the computing loads among processors. On the other hand, we hope to improve parallel performance by reducing communication cost and time among processors.Hypergraph partitioning is an extremely efficient method for load balancing in parallel computing. Data are represented as vertices in a hypergraph, and hyperedges represent data dependencies. Hypergraph partitioning attempts to minimize the number of crossedges in the hypergraph between processors, as these result in application communication.It has excellent characteristics both in more accurate measurement model and more efficient partitioning quality, which has attracted researchers much more attentions for this method in recent years. However, the improvement of partitioning algorithms still fall far short of actual needs. Therefore, the existing hypergraph partitioning algorithms cannot meet the changing application requirements.This thesis details our researches on multilevel hypergraph partitioning algorithm used in CFD computations with the unstructured mesh. The coarsening, initial partitioning and uncoarsening phases of multilevel framework is studied with the proposal of a series of heuristic algorithms to meet the actual requirement of CFD computations. Then, the multilevel algorithm, which has important theoretical significance and practical value, is used in large-scale CFD computations.The main research achievements of this thesis are as follows.(1)A hierarchy-based weighted inner products matching coarsening algorithm is presented.This thesis discusses the problem of existing coarsening algorithms, and analyzes the importance and the impact on partitioning performance of coarsening phase in detail.Firstly, in order to hide more edge weight, a weighted inner products matching system based on common hyperedge is proposed. Secondly, in order to produce higher coarsening rate, two hierarchical rules that determine the access sequence and merge order of vertices are established. Based on research the above-mentioned idea, the hierarchy-based weighted inner products matching(HWIPM) coarsening algorithm is proposed. The numerical experiments show that HWIPM is far superior in respect of coarsening rate, edge weight hiding and run-time, and is beneficial for the final partitioning performance.(2)A genetic uncoarsening algorithm based on locked gain and directed K-way partitioning is presented.To begin with,this thesis concretely analyses the advantages and defects between recursive bipartitioning and direct K-way partitioning, and puts forward two optimizing strategies aimed at existing problems. In the first place, a maintenance policy based on binary heap for the vertex gain, which is used in K-way boundary refinement, could greatly reduce the computation complexity. In the second place, a new calculating method of locked gain, which is used in vertex movements, could optimize partitioning performance.Next, combining above strategies, an uncoarsening algorithm(LKFM) based on locked gain and directed K-way partitioning is proposed. Furthermore, to take advantage of the ability of global optimization of genetic algorithm, a hybrid genetic(MHGA) algorithm with above local search heuristic algorithm is presented. The numerical experiments show that MHGA is obviously advantageous in terms of partitioning performance and run-time.(3)A multi-object particle swarm uncoarsening algorithm for cutsize and maximum subdomain degree minimization is presented.After analyzing the relationship of the unity of opposites between cutsize and maximum subdomain degree minimization, this thesis proposes a multi-objective optimization model to intelligently deal with the problem. Aiming at this problem, a multi-phase and multi-objective refinement(MKFM) algorithm is put forward, which is based on highquality, cut based, K-way partitioning strategy and layered sorting, and linear weighted mixing method. In order to improve the performance of MKFM, the combination of particle swarm algorithm and the local search is developed. The numerical experiments show that MHPSO explicitly minimize the maximum subdomain degree and ensure that the cutsize and run-time does not significantly increase. And it is especially powerful when applied in CFD computing area.(4)The multilevel hypergraph partitioning method is applied to partition unstructured mesh in parallel CFD computation.The multilevel hypergraph partitioning algorithm is used in CFD computation of unstructured mesh. Thus a parallel solution method is developed for large-scale unstructured mesh based on hypergraph partitioning strategy and MPI message-passing approach. The numerical examples of three typical problems are implemented. And the algorithm performance including partitioning quality, correctness and parallel performance are verified in Tianhe-1 supercomputer. The experimental results indicate that when applied in the field of CFD computations on unstructured mesh, our partitioning method can assure the correctness of the computation result, with higher parallel efficiency and better scalability.