Dynamic Load Balancing for 2D Structured-Mesh Methods

Burgers' Equation

We solve the 2D inviscid Burgers' equation with periodic boundary conditions and sinusoidal initial conditions. We use a discontinuous finite element method and adaptive hp-refinement with a 16x16-element base mesh and piecewise constant approximations (p = 0) initially. The problem is solved on 256 processors of the nCUBE/2. A local load-balancing algorithm is applied to the adaptive hp-refinement runs.

Initially, the solution is smooth and adaptive order enrichment (p-refinement) is performed. In time, however, the solution steepens to a shock, and a combination of mesh refinement and order enrichment (i.e., adaptive hp-refinement) is used.


Adaptive hp-refinement using higher-degree polynomials in smooth-solution regions and refined meshes near steep gradients.

The results in the table below demonstrate the reductions in execution time achieved using both adaptive hp-refinement and load balancing. The ratio of the average work load per processor to the maximum work load among the processors (the Avg./Max. Work Ratio) indicates how well the computation was load-balanced. By using the unbalanced adaptive hp-refinement method, the execution time was reduced by roughly 50% relative to the fixed-mesh, fixed-order method with comparable accuracy. The adaptive hp-refinement method with load balancing took only 22% as long as a fixed-mesh, fixed-order method with comparable accuracy.

Adaptive hp-refinement Method Fixed-mesh, Fixed-order Method
No Balancing With Balancing No Balancing
Global L1-Error 0.0220026 0.0220026 0.0218864
Avg./Max. Work Ratio 0.208 0.878 0.994
Total Max. Communication Time 319.49 secs. 459.73 secs. 583.65 secs.
Total Max. Balancing Time 0 secs. 40.99 secs. 0 secs.
Total Execution Time 2909.50 secs. 1285.78 secs. 5858.89 secs.
Performance comparison of fixed-mesh, fixed-order methods with adaptive hp-refinement methods with load balancing.

Euler Equations

We solve the 2D Euler equations for a problem involving a Mach 10 shock in air moving down a channel containing a wedge oriented at a 30-degree angle to the channel. Following Woodward and Colella, we solve the problem on a rectangular domain with the wedge oriented so that it lies along the bottom boundary of the domain. The initial conditions are such that they represent a Mach 10 scock making a 60-degree angle with the reflecting edge.

To solve this problem, we used a discontinuous finite element method and a local load-balancing algorithm on 512 processors of an Intel Paragon. Solutions with comparable accuracy are obtained from a fixed-mesh, fixed-order local finite element method with a 256x128-element mesh and piecewise quadratic polynomials (p = 2) and from an adaptive hp-refinement method with a 32x16-element base mesh and piecewise linear elements (p = 1) initially. Because of the computation efficiency of the adaptive scheme combined with the local load balancing, the adaptive hp-refinement method required only 43% as much time to obtain a comparable solution.


Density profile at time = 0.2 obtained from the
fixed-mesh, fixed-order method
(256x128-element mesh with p = 2).
Total execution time = 13,162 seconds.


Density profile at time = 0.2 obtained from the
adaptive hp-refinement method with load balancing
(32x16-element base mesh with p = 1 initially).
Total execution time = 5695 seconds.

References

P. Woodward and P. Collela. "The numerical simulation of two-dimensional fluid flow with strong shocks." J. Comput. Phys., 54 (1984) 115-173.

Last Updated: October 15, 1997
WWW Administration (www-admin@www.cs.sandia.gov)
Karen Devine (kddevin@cs.sandia.gov)


Back