A Local Load Balancing Algorithm

To load balance our adaptive methods, we have used a local load-balancing algorithm based on the work of Wheat and Leiss and Reddy. Within the problem domain, "neighborhoods" of processors are defined as a central processor and all processors whose assigned elements share edges with those in the central processor. Each processor is the center of its own processor neighborhood, resulting in overlapping neighborhoods as shown above. Inexpensive local load balancing is performed within each processor neighborhood. Global load balance is achieved after several iterations of the local balancing algorithm, as work diffuses from neighborhoods to their adjacent neighborhoods.

Outline of the Local Algorithm

  • Determine processor work load from computation phase.
  • Compute neighborhood average work load.
  • Request work from processor with greatest work load in neighborhood.
    Each processor makes only one request.
    A processor may receive more than one request.
    If any requests are received, always export at least one element.
  • Select elements to satisfy work requests.
    Give priority to elements with neighbors in the importing processors.
    Do not allow work load to fall below neighborhood average work load.
  • Notify importing processors and neighboring processors.
  • Transfer elements between processors.

    • References

    K. Devine and J. Flaherty. "Parallel adaptive hp-refinement techniques for conservation laws." Applied Numerical Mathematics, 20 (1996) 367-386.

    S. Wheat. A fine grained data migration approach to application load balancing on MP MIMD machines. Ph.D. Dissertation, University of New Mexico, Albuquerque (1992).

    E. Leiss and H. Reddy. "Distribution load balancing: design and performance analysis." W.M. Keck Research Computation Laboratory, 5 (1989) 205-270.

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


    Back