CaltechAUTHORS
  A Caltech Library Service

A Parabolic Theory of Load Balance

Heirich, Alan and Taylor, Stephen (1993) A Parabolic Theory of Load Balance. Computer Science Technical Reports, California Institute of Technology , Pasadena, CA. (Unpublished) http://resolver.caltech.edu/CaltechCSTR:1993.cs-tr-93-25

[img]
Preview
Postscript - Submitted Version
See Usage Policy.

873Kb
[img] PDF - Submitted Version
See Usage Policy.

670Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechCSTR:1993.cs-tr-93-25

Abstract

We derive analytical results for a dynamic load balancing algorithm modeled by the heat equation ut = V2u. 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. For large n the time complexity to reduce the expected imbalance is effectively independent of n.


Item Type:Report or Paper (Technical Report)
Additional Information:© 1993 California Institute of Technology. The research described in this report is sponsored primarily by Lite Defense Advanced research Projects Agency, DARPA Order number 8176, and monitored by the Office of Naval Research under contract number N00014-91-J-1986.
Group:Computer Science Technical Reports
Funders:
Funding AgencyGrant Number
Defense Advanced Research Projects Agency (DARPA)8176
Office of Naval Research (ONR)N00014-91-J-1986
DOI:10.7907/Z91R6NJD
Record Number:CaltechCSTR:1993.cs-tr-93-25
Persistent URL:http://resolver.caltech.edu/CaltechCSTR:1993.cs-tr-93-25
Usage Policy:You are granted permission for individual, educational, research and non-commercial reproduction, distribution, display and performance of this work in any format.
ID Code:26765
Collection:CaltechCSTR
Deposited By: Imported from CaltechCSTR
Deposited On:25 Apr 2001
Last Modified:25 May 2017 20:37

Repository Staff Only: item control page