| As a pre-processing method of finite element parallel computing,graph partitioning algorithm is widely used for grid partitioning in parallel computing because of its simplicity and efficiency.With the increasing complexity of actual engineering problems,the existing partitioning algorithm is not only difficult to obtain better partition quality,but also has low partition efficiency,which can no longer meet the needs of practical applications.At the same time,there are very few researches on the grid partition part in the finite element parallel design.Therefore,this article focuses on the application of the partition method in large-scale coarse-grained finite element parallel computing,and conducts an in-depth theoretical analysis of the multi-level partition method,improves its shortcomings and limitations,and conducts experimental verification and analysis.The specific research work of this article is as follows:(1)Degree-Sorted Weight Match Algorithm is suggested in the coarsening phase.The algorithm uses the information of the node degree to match the vertex which has little relevance around it firstly,and overcomes the defect of generating outliers by randomly picking points for matching.Secondly,the heavy-edge matching adds a weight control mechanism while maximizing the hidden weight of the heavy-edge,which effectively prevents the imbalance of vertex weights after matching;Finally,for those vertices whose weights are still very small after coarsening,they are merged into the adjacent nodes with the smallest weights to further ensure the balance of the vertices.(2)Bordered Region Growing Algorithm is suggested in the initial partitioning phase.The algorithm selects the starting point at the edge of the graph to perform the growth partitioning,which avoids dividing the same subset into disconnected regions effectively,thereby obtaining a smaller edge cut and improving the quality of the partition.(3)Global refinement algorithm is suggested in the refinement phase.The algorithm reduces the criteria for boundary point selection and expands the movement chance of boundary point;Secondly,the movement of the vertex is no longer strictly constrained by the positive return,allowing it to optimize in the direction of poor partition quality within acceptable iteration steps,and it is easy to jump out of the local optimal solution,then use the backtracking method to find the optimal solution's step to obtain the global optimal quality.(4)Developed a serial partition algorithm based on multilevel partition algorithm.Combining the optimization strategies of coarsening,initial partitioning and refinement,a modified multilevel partitioning algorithm(MMPA)is proposed.Aiming at the problem that the file reading time affects the efficiency of the partition seriously,the program of the file reading part has been optimized to improve the efficiency of file reading.After that,a multi-partition test was carried out on several 2D and 3D instances with different grid types.The results show that compared with the traditional mpmetis graph partitioning algorithm,the partitioning effect of the MMPA has been improved significantly,and the file reading efficiency has been increased by 2 times approximately.(5)Developed a parallel partitioning algorithm based on MPI and OpenMP mixed programming.The parallel partitioning algorithm is proposed by mixing programming model of MPI and OpenMP.The main optimization ideas are divided into two aspects: The first is to use MPI technology to realize the parallelization of the coarsening process.Aiming at the problem of interference in vertex matching between processes,a reasonable vertex pairing strategy is proposed;The second is to use OpenMP technology to realize the parallelization of the division process from the perspective of loop parallelization and region parallelization.Finally,a numerical example of a door handle verifies the efficiency of the parallel partitioning algorithm. |
PDF Full Text Request