Dynamic Load Balancing and Data Migration for Adaptive Numerical Methods

Adaptive numerical methods that automatically refine or coarsen meshes and/or vary the order of accuracy of a method offer greater reliability, robustness, and computational efficiency than traditional approaches for solving partial differential equations. On parallel computers, however, adaptivity introduces complications that do not arise when simpler solution strategies are implemented. Adaptive algorithms use unstructured or hierarchical data structures that change dynamically with adaptivity, making the task of decomposing and redistributing data more difficult than with non-dynamic structures. A balanced decomposition will, furthermore, become unbalanced as additional degrees of freedom are introduced or removed by adaptive refinement.

Sandia is currently making large investments in hierarchical adaptive mesh refinement of unstructured grids for the application codes MPSalsa, ALEGRA, and SIERRA. Each of these projects uses quadtree/octree data structures to represent the refined meshes; that is, during refinement, elements are split into smaller elements which are stored as "children" of the initial "parent" elements in a hierarchical data structure. Quadtrees and octrees are widely used in both mesh generation and adaptive refinement on serial computers. Using a local load-balancing technique, we have successfully balanced quadtrees dynamically for 2D adaptive, structured-mesh methods with local time-stepping (see results). However, many issues must be resolved for the more general cases of 3D unstructured grids, steady-state problems, and method-of-lines time-stepping. These issues include

  • Designing efficient dynamic load-balancing methods that account for data's current location to reduce migration costs;
  • Developing load-balancing heuristics for hierarchical meshes;
  • Efficiently distributing octree data structures on parallel computers; and
  • Incorporating accurate models and measurements of processor work loads and migration costs into load-balancing algorithms.
  • To address these and related issues, we are developing a dynamic load-balancing tool which we call Zoltan. A general purpose tool for this class of problems raises a number of challenging software-engineering issues.

  • How does a tool support applications with different data structures?
  • What is the best way to interface to a suite of load-balancing algorithms?
  • How can we support generality without sacrificing efficiency?
  • Our solution to these problems is to use an object oriented design which is data-structure neutral. To improve performance, we are writing Zoltan in C. The interfaces have been carefully designed with consideration of the applications as well as the algorithms.

    Zoltan will provide dynamic load balancing support for a range of applications. Adaptive PDE solvers like those discussed above are the most significant target. But the tool will also be used to support particle calculations, contact detection in crash simulations and other dynamic and adaptive codes. Version 1.01 of the code is currently being supported which includes the necessary basic functionality. In the course of the next year we will be adding additional load-balancing algorithms, support for heterogeneous computers, tools for data migration and other enhancements.

    2D Results

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

    Page 2