 |
Center for Nonlinear Studies |
Scalability of particle simulations on parallel computers strongly depends on the distribution of work onto the processors. For complex geometries, inhomo-geneous particle distributions or particle interactions based on different force field complexities, the work distribution is often inherently inhomogenous, re-sulting in a variation of work load over the processors. Several methods will be summarized which are able to iteratively adjust the load on each processor to the system average work. This principle is similar to iterative PDE solvers and therefore have a relaxation time which increases quadratically with system size. For large processor counts relaxation based load balancing schemes can therefore introduce large overhead or take many iteration steps until work load equilibrium is reached. In order to overcome the quadratic increase in relaxation time, ideas from multigrid techniques are applied to achieve fast convergence. Recursive bisection is used to construct an L-level tree where the underlying work distribution is transferred across the tree as density plaquettes, which is recursively refined as a multi-level V-cycle. Therefore, minimal information ex-change is needed on higher tree levels and explicit particle transfer is only done on the highest tree level L. For several test cases it is demonstrated that ex-ponential convergence is achieved. For continuous test cases accuracies with errors can be reached. For discrete particle systems, accuracy is limited by the commensurability of particle number and processor count. In most cases 2-4 V-cycles are sufficient to reach accuracies with errors < 1% of work distributions.
Host: Christoph Junghans