Mesh partitioning is an indispensable tool for efficient parallel numerical simulations. Its goal is to minimize communication between the processes of a simulation while achieving load balance. Established graph-based partitioning tools yield a high solution quality; however, their scalability is limited. Geometric approaches usually scale better, but their solution quality may be unsatisfactory for "non-trivial" mesh topologies. In this paper, we present a scalable version of k-means that is adapted to yield balanced clusters. Balanced k-means constitutes the core of our new partitioning algorithm Geographer. Bootstrapping of initial centers is performed with space-filling curves, leading to fast convergence of the subsequent balanced k-means algorithm. Our experiments with up to 16 384 MPI processes on numerous benchmark meshes show the following: (i) Geographer produces partitions with a lower communication volume than state-of-the-art geometric partitioners from the Zoltan package; (ii) Geographer scales well on large inputs; (iii) a Delaunay mesh with a few billion vertices and edges can be partitioned in a few seconds.
Most geometric partitioning techniques in wide use consider points and optimize for load balance @cite_31 @cite_6 @cite_9 . Established geometric methods include the recursive coordinate bisection ( @cite_9 @cite_29 ) and recursive inertial bisection ( @cite_44 @cite_24 ). Deveci al @cite_31 introduce a multisection algorithm, called Multi -Jagged (MJ), as a generalization of the traditional recursive techniques. The space is divided into rectangles while minimizing the weight of the largest rectangle. This method has better running time and is more scalable but yields less balanced partitions compared to RCB. Many common geometric partitioning methods are implemented in the Zoltan toolbox @cite_10 .
@cite_9 @cite_29 @cite_6 @cite_44 @cite_24 @cite_31 @cite_10
2073890622 2111516947 1997481890 2096159022 2062897411 2138388932
Abstract Many large-scale computational problems are based on unstructured computational domains. Primary examples are unstructured grid calculations based on finite volume methods in computational fluid dynamics, or structural analysis problems based on finite element approximations. Here we will address the question of how to distribute such unstructured computational domains over a large number of processors in a MIMD machine with distributed memory. A graph theoretical framework for these problems will be established. Based on this framework three decomposition algorithms will be introduced. In particular a new decomposition algorithm will be discussed, which is based on the computation of an eigenvector of the Laplacian matrix associated with the graph. Numerical comparisons on large-scale two- and three-dimensional problems demonstrate the superiority of the new spectral bisection algorithm. We consider the partitioning of a problem on a domain with unequal work estimates in different subdomains in a way that balances the workload across multiple processors. Such a problem arises for example in solving partial differential equations using an adaptive method that places extra grid points in certain subregions of the domain. We use a binary decomposition of the domain to partition it into rectangles requiring equal computational effort. We then study the communication costs of mapping this partitioning onto different multiprocessors: a mesh- connected array, a tree machine, and a hypercube. The communication cost expressions can be used to determine the optimal depth of the above partitioning. In this paper we investigate the additional storage overhead needed for a parallel implementation of finite element applications. In particular, we compare the storage requirements for the factorization of the sparse matrices that would occur on a parallel processor vs. a uniprocessor. This variation in storage results from the factorization fill-in. We address the question of whether the storage overhead is so large for parallel implementations that it imposes severe limitations on the problem size in contrast to the problems executed sequentially on a uniprocessor. The storage requirements for the parallel implementation are based upon a new ordering scheme, the combination mesh-based scheme. This scheme uses a domain decomposition method which attempts to balance the processors' loads and decreases the interprocessor communication. The storage requirements for the sequential implementation is based upon the minimum degree algorithm. The difference between the two storage requirements corresponds to the storage overhead attributed to the parallel scheme. Experiments were conducted on regular and irregular, 2-D and 3-D problems. The meshes were decomposed into 2–256 subdomains which can be executed on 2–256 processors, respectively. The total storage requirements or fill-in for most of the 2-D problems were less than a factor of two increase over the sequential execution. In contrast, large 3-D problems had zero increase in storage or fill-in over the sequential execution; the fill-in was less for the parallel execution than the sequential execution. Thus, we conclude that the storage overhead attributed to the use of parallel processors will not impose severe constraints on the problem size. Further, for large 3-D applications, the combination mesh-based algorithm does better than minimum degree for reducing the fill-in. If a finite element mesh has a sufficiently regular structure, it is easy to decide in advance how to distribute the mesh among the processors of a distributed-memory parallel processor, but if the mesh is unstructured the problem becomes much more difficult. The distribution should be made so that each processor has approximately equal work to do, and such that communication overhead is minimized. If the mesh is solution-adaptive, i.e. the mesh and hence the load-balancing problem change discretely during execution of the code, then it is most efficient to decide the optimal mesh distribution in parallel. In this paper three parallel algorithms, orthogonal recursive bisection (ORB), eigenvector recursive bisection (ERB) and a simple parallelization of simulated annealing (SA) have been implemented for load balancing a dynamic unstructured triangular mesh on 16 processors of an NCUBE machine. The test problem is a solution-adaptive Laplace solver, with an initial mesh of 280 elements, refined in seven stages to 5772 elements. We present execution times for the solver resulting from the mesh distributions using the three algorithms, as well as results on imbalance, communication traffic and element migration. The load-balancing itself is fastest with ORB, but a very long run of SA produces a saving of 21 in the execution time of the Laplace solver. ERB is only a little slower than ORB, and yet produces a mesh distribution whose execution time is 15 faster than ORB. Geometric partitioning is fast and effective for load-balancing dynamic applications, particularly those requiring geometric locality of data (particle methods, crash simulations). We present, to our knowledge, the first parallel implementation of a multidimensional-jagged geometric partitioner. In contrast to the traditional recursive coordinate bisection algorithm (RCB), which recursively bisects subdomains perpendicular to their longest dimension until the desired number of parts is obtained, our algorithm does recursive multi-section with a given number of parts in each dimension. By computing multiple cut lines concurrently and intelligently deciding when to migrate data while computing the partition, we minimize data movement compared to efficient implementations of recursive bisection. We demonstrate the algorithm’s scalability and quality relative to the RCB implementation in Zoltan on both real and synthetic datasets. Our experiments show that the proposed algorithm performs and scales better than RCB in terms of run-time without degrading the load balance. Our implementation partitions 24 billion points into 65,536 parts within a few seconds and exhibits near perfect weak scaling up to 6K cores. Partitioning and load balancing are important problems in scientific computing that can be modeled as combinatorial problems using graphs or hypergraphs. The Zoltan toolkit was developed primarily for partitioning and load balancing to support dynamic parallel applications, but has expanded to support other problems in combinatorial scientific computing, including matrix ordering and graph coloring. Zoltan is based on abstract user interfaces and uses callback functions. To simplify the use and integration of Zoltan with other matrix-based frameworks, such as the ones in Trilinos, we developed Isorropia as a Trilinos package, which supports most of Zoltan's features via a matrix-based interface. In addition to providing an easy-to-use matrix-based interface to Zoltan, Isorropia also serves as a platform for additional matrix algorithms. In this paper, we give an overview of the Zoltan and Isorropia toolkits, their design, capabilities and use. We also show how Zoltan and Isorropia enable large-scale, parallel scientific simulations, and describe current and future development in the next-generation package Zoltan2.