Graph Partitioning for the Finite Element Method: Reducing Communication Volume with the Directed Sorted Heavy Edge Matching

Abstract

A technique called the Finite Element Method is primarily utilized to numerically solve Partial Differential Equations, most commonly by the use iterative methods, over a compact domain. The partial differential equations domain is represented by a mesh of information which needs to be distributed among all available processors or cores in a parallel computer. Distributing the mesh, known as the mesh partitioning problem, is NP-complete. Much effort focuses on graph partitioning and parallelization to address it. An increasing variety of general purpose techniques and libraries has been and is being developed in recent time, many of which provide great effectiveness. However, the load balancing of the mesh is still an open problem; newer and larger simulations bring new requirements into play. These techniques have to scale linearly on large clusters of hundreds of thousands of processors. They have to be resource aware and take into consideration the heterogeneity of current processors and network infrastructures in the partitioning process. Equal size meshes, provided by traditional partitioning methods, no longer fulfill the main goals. New enhancements to existing libraries and algorithms are required to support even more complex applications and the constantly evolving hardware architectures. In this work, we give an overview of current graph partitioning techniques used on large-scale parallel machines for load balancing of finite element computations. We introduce a new vertex matching model called Directed Sorted Heavy Edge Matching to reduce the communication volume during FEM simulations and ensure efficient execution on a distributed system. Finally, we provide performance analysis of the proposed model and comment on its benefits.