Research On Graph Partitioning Algorithms And The Applications In The Large-scale Numerical Parallel Computation

Numerical parallel computation is an important approach to solve the problem oflarge-scale science and engineering applications. In parallel computation, we are hopingfor reducing idle time by distributing computing tasks reasonably and balancing thecomputing loads among all computing nodes on one hand. On the other hand, we arehoping for reducing communication cost among all computing nodes and improvingparallel efficiency. In order to solve above load balancing problem much better, taskgraphs can be used to carry on the modelling, by which load balancing problem can beabstract to graph partitioning problem.Graph partitioning problem is a hot issue in the field of parallel computing.Domestic and foreign scholars have proposed many excellent partitioning algorithmsand models on the process of scientific research and exploration for many decades.However, many existing partitioning algorithms can not fit with the changingapplication requirements. So, more powerful partitioning models, more excellentpartitioning algorithms and more efficient methods of application is urgent to study.Against above background, graph partitioning problem is regarded as the starting pointof this thesis. Graph partitioning algorithms and the applications in the numericalparallel computation is mainly studied, which have important theoretical significanceand practical value. The main contributions of this thesis are as follows.1. Cluster-based multilevel algorithm for static graph partitioning.For the problem of static graph partitioning, multilevel algorithm is studied as thestarting point. This thesis elaborates the typical strategies used in all phases according totheir distinguishing characteristics and briefly compares all strategies. Then, aquantitative analysis is conducted on multilevel algorithm on the basis of Miller’sassumptions. According to results of the quantitative analysis, we develop a highlydetailed profile on the shortcomings and limitations of existing matching-basedcoarsening strategies and propose a cluster-based multilevel algorithm(CBML). CBMLproduce results that are substantially better than METIS in most cases, especially forlinear programming and VLSI design problems, which is proved to be effective byexperimental results.2. Multilevel-based repartitioning model for dynamic graph partitioning.For the problem of dynamic graph partitioning, this thesis elaborates varioustypical repartitioning algorithms and compares their performance and applicableconditions. In order to overcome the limitations of existing repartitioning algorithms,we define communication-migration ratio and cost function of repartitioning problem.The perfomance of repartitioning is evaluated more accurately by the cost function. Andthe optimization objective of repartitioning is represented as minimization of cost function. On this basis, we propose a multilevel-based repartitioning model(MBRM) bymaking use of the advantage of multilevel algorithm. Finally, the dynamic process ofcomputing load is simulated by structure perturbations and calculation amountperturbations and the performance of MBRM is tested and compared to ParMETIS. Theperformance of MBRM is better than ParMETIS, especially under the condition thatcommunication cost and migration cost is close.3. Improved hypergraph-partitioning-based nested dissection ordering algorithm.For the problem of fill reducing ordering, this thesis elaborates various typicalordering algorithms and focuses on nested-dissection-based hybrid approaches. Then weanalyse the key factor in affecting the performance, which is the quality of vertexseparators of all subgraphs. However, shortcomings and limitations are existed in bothtwo exsiting strategies of computing vertex separators. In order to overcome theshortcomings and limitations, we propose an improved hypergraph-partitioning-basednested dissection ordering algorithm(HBND) by translating vertex separator probleminto hypergraph partitioning problem. The ordering quality produced by HBND is betterthan METIS, which is proved by experimental results.4. Grid partitioning optimization for parallel CFD examples of unstructured grid.The CBML algorithm is used for parallel CFD computations of unstructured grid.For three parallel CFD examples which are airfoil NACA0012, ONERA-M6andDLR-F6, grid partitioning is optimized by CBML, which is compared to METIS.Finally, parallel performance is tested in Tianhe1-A. By comparing the parallelperformance index of accelerate rate and efficiency, we analyse the effectiveness of bothtwo partitioning algorithms. Parallel performance is better when CBML is used for gridpartitioning by experimental results.