Accession Number:

ADA443334

Title:

A Parabolic Theory of Load Balance

Descriptive Note:

Corporate Author:

CALIFORNIA INST OF TECH PASADENA DEPT OF COMPUTER SCIENCE

Personal Author(s):

Report Date:

2006-01-01

Pagination or Media Count:

19.0

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.

Subject Categories:

  • Numerical Mathematics
  • Computer Programming and Software

Distribution Statement:

APPROVED FOR PUBLIC RELEASE