Mesh Partitioning

We have developed an efficient partitioning heuristic based on minimizing the geometric aspect ratios of the final partitions. A feature of our implemenation is the ability to dynamically update partitions after mesh modifications, without resorting to a complete repartitioning of the mesh.

As grid points are dynamically added and deleted in the mesh, good partitionings must be determined for distributed memory architectures. For uniform meshes a good partitioning of grid points may be determined a priori by the geometric domain. However, for unstructured, adaptive meshes the partitioning cannot be predetermined as it changes with each new refinement of the mesh. We require that the partitioning simultaneously maintains good load balancing and minimizes interprocessor communication costs. Hence we need to evenly distribute grid points to the processors and also minimize the latency and transmission costs by minimizing the number of partition neighbors and number links crossing the partition boundary, respectively.

Previous Work

Spectral Techniques: (Donath and Hoffman, Barnes , Pothen, Simon, and Loui) These algorithms have the advantage of global access to information about the graph to find good separators at the cost of eigenvalue/eigenvector computation. Although the eigenvectors generally do not need to be found to much accuracy (Pothen, Simon, and Loui), spectral methods fail to utilize the the geometric information known about the vertices of the mesh which may significantly decrease execution time.

Orthogonal Recursive Bisection: (Berger and Bokhari) The ORB algorithm makes an initial cut to divide the grid points in half. Orthogonal cuts are then made recursively in the new subdomains until the grid points are equally distributed among the processors. Although this algorithm obtains good load balancing, it ignores the communication minimization problem. Long, thin partitions may be created which have a high ratio of links crossing the partition boundaries to total number of links in the partition. This leads to high communication to computation ratios.

Our Algorithm

Unbalanced Recursive Bisection: To address the problems of the ORB algorithm, we have developed a modification of ORB which we call Unbalanced Recursive Bisection (URB). Instead of dividing the unknowns in half, we choose the cut which minimizes partition aspect ratio and divides the unknowns into kn/p and (p-k)n/p size groups where n is the total number of unknowns, and p is the total number of processors, and k=1,2,..., p. This algorithm leads to an even distribution of grid points with more balanced partition aspect ratios.

In addition we note that it is not always necessary to repartition the graph as the mesh is adaptively refined. While the partition aspect ratios remain better than some user defined tolerance we simply shift the partition boundaries, otherwise we repartition.

Previous: Adaptive Mesh Refinement
Next: Sparse Linear System Solution
Back: Unstructured Mesh Home Page