Parallel Multilevel Diffusion Algorithms for Repartitioning of Adaptive Meshes

Abstract

Graph partitioning has been shown to be an effective way to divide a large computation over an arbitrary number\nof processors. A good partitioning can ensure load balance and minimize the communication overhead of the computation\nby partitioning an irregular mesh into p equal parts while minimizing the number of edges cut by the partition.\nFor a large class of irregular mesh applications, the structure of the graph changes from one phase of the computation\nto the next. Eventually, as the graph evolves, the adapted mesh has to be repartitioned to ensure good load balance.\nFailure to do so will lead to higher parallel run time. This repartitioning needs to maintain a low edge-cut in order to\nminimize communication overhead in the follow-on computation. It also needs to minimize the time for physically\nmigrating data from one processor to another since this time can dominate overall run time. Finally, it must be fast and\nscalable since it may be necessary to repartition frequently. Partitioning the adapted mesh again from scratch with an\nexisting graph partitioner can be done quickly and will result in a low edge-cut. However, it will lead to an excessive\nmigration of data among processors. In this paper, we present new parallel algorithms for robustly computing repartitionings\nof adaptively refined meshes. These algorithms perform diffusion of vertices in a multilevel framework and\nminimize data movement without compromising the edge-cut. Furthermore, our parallel repartitioners include parameterized\nheuristics to specifically optimize edge--cut, total data migration, or the maximum amount of data migrated\ninto and out of any one processor. Our results on a variety of synthetic meshes show that our parallel multilevel diffusion\nalgorithms are highly robust schemes for repartitioning adaptive meshes. The resulting edge-cuts are close to\nthose resulting from partitioning from scratch with a state-of-the-art graph partitioner, while data migration is substantially\nreduced. Furthermore, repartitioning can be done very fast. Our experiments show that meshes with around\neight million vertices can be repartitioned on a 256-processor Cray T3D in only a couple of seconds.