S. Schamberger (Germany)
Heuristic graph partitioning, shape optimization, multi graph scheme, diffusion.
To solve the graph partitioning problem, efficient heuris tics have been developed that are also capable of distribut ing the computational load in parallel Finite Element (FE) computations. Most of these heuristics try to minimize the global edge-cut, although it is known that this met ric does not always correlate with the real communication and computation costs. Furthermore, some parallel solv ing techniques are only applicable if additional constraints like well-shaped partitions and their connectivity are ful filled, what common partitioning libraries cannot guaran tee. Recently, we have proposed an alternative approach to deal with the FEM graph partitioning problem. The com puted partitionings are well-shaped and connected and the resulting communication costs are usually lower than in so lutions obtained by the state-of-the-art graph partitioning libraries. Furthermore, the new algorithm contains a high degree of parallelism. However, its drawback is its long sequential run-time. In this paper we adopt the multigraph schemes, that are known from multigrid FEM computations as well as from multilevel graph partitioning libraries, into the pro posed diffusive approach. Combinations of both multi graph schemes are possible. The results of our experiments show that we can shorten the run-time by one order of mag nitude without deteriorating the solution quality.
Important Links:
Go Back
