A Parabolic Theory of Load Balance

Abstract

We derive analytical results for a dynamic load balancing algorithm modeled by the heat equation. The model is appropriate for quickly diffusing disturbances in a local region of a computational domain without affecting other parts of the domain. The algorithm is useful for problems in computational fluid dynamics which involve moving boundaries and adaptive grids implemented on mesh-connected multicomputers. The algorithm preserves task locality and uses only local communication. Resulting load distributions approximate time asymptotic solutions of the heat equation. As a consequence it is possible to predict both the rate of convergence and the quality of the final load distribution. These predictions suggest that a typical imbalance on a multicomputer with over a million processors can be reduced by one order of magnitude after 105 arithmetic operations at each processor.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 2006
Accession Number
ADA443334

Entities

People

  • Alan Heirich
  • Stephen Taylor

Organizations

  • California Institute of Technology

Tags

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • Boundaries
  • Computational Fluid Dynamics
  • Dynamic Loads
  • Equations
  • Fluid Dynamics
  • Information Operations
  • Load Distribution

Readers

  • Fluid Mechanics and Fluid Dynamics.
  • Operations Research
  • Parallel and Distributed Computing.