A new metric enabling an exact hypergraph model for the communication volume in distributed-memory parallel applications

• A new hypergraph model to map FEM triangulations to parallel processes is proposed.
• This data distribution is formulated as a hypergraph partitioning problem.
• The objective involves a novel metric representing the communication volume exactly.
• We develop a bipartitioning heuristic to solve the hypergraph partitioning problem.
• We present detailed numerical results for an FEM solver on up to 1024 processes.

A hypergraph model for mapping applications with an all-neighbor communication pattern to distributed-memory computers is proposed, which originated in finite element triangulations. Rather than approximating the communication volume for linear algebra operations, this new model represents the communication volume exactly. To this end, a hypergraph partitioning problem is formulated where the objective function involves a new metric. This metric, the λ(λ-1)λ(λ-1)-metric, accurately models the communication volume for an all-neighbor communication pattern occurring in a concrete finite element application. It is a member of a more general class of metrics, which also contains more widely used metrics, such as the cut–net and the (λ-1)(λ-1)-metric. In addition, we develop a heuristic to minimize the communication volume in the new λ(λ-1)λ(λ-1)-metric. For the solution of several real-world finite element problems, experimental results based on this new heuristic demonstrate a small reduction in communication volume compared to a standard graph partitioner and do not show significant reductions in communication volume compared to a hypergraph partitioner using the common (λ-1)(λ-1)-metric. However, for this set of problems, the new approach does reduce actual communication times. As a by-product, we observe that it also tends to reduce the number of messages. Furthermore, the new approach dramatically reduces the communication volume for a set of sparse matrix problems that are more irregularly-structured than finite element problems.