Lab Home | Phone | Search
Center for Nonlinear Studies  Center for Nonlinear Studies
 Colloquia Archive 
 Postdoc Seminars Archive 
 Quantum Lunch 
 CMS Colloquia 
 Q-Mat Seminars 
 Q-Mat Seminars Archive 
 Kac Lectures 
 Dist. Quant. Lecture 
 Ulam Scholar 
 Summer Research 
 Past Visitors 
 History of CNLS 
 Maps, Directions 
 CNLS Office 
Monday, August 19, 2019
3:00 PM - 4:00 PM
CNLS Conference Room (TA-3, Bldg 1690)


Multi-Level Load Balancing for Particle Simulation Methods

Godehard Suttmann
Forschungszentrum Jülich

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