A Caltech Library Service

A Parabolic Load Balancing Method

Heirich, Alan and Taylor, Stephen (1994) A Parabolic Load Balancing Method. Computer Science Technical Reports, California Institute of Technology , Pasadena, CA. (Unpublished)

Postscript - Submitted Version
See Usage Policy.

PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


This paper presents a diffusive load balancing method for scalable multicomputers. In contrast to other schemes which are probably correct the method scales to large numbers of processors with no in-crease in run time. In contrast to other schemes which are scalable the method is provably correct and the paper analyzes the rate of covergence. To control aggregate cpu idle time it can be useful to balance the load to specifiable accuracy. The method achieves arbitrary accuracy by proper consideration of numerical error and stability. This paper presents the method, proves correctness, convergence and scalability, and simulates applications to generic problems in computational fluid dynamics (CFD). The applications reveal some useful properties. The method can preserve adjacency relationships among elements of an adapting computational domain. This makes it useful for partitioning unstructured computational grids in concurrent computations. The method can execute asynchronously to balance a subportion of a domain without affecting the rest of the domain. Theory and experiment show the method is efficient on the scalable multicomputers of the present and coming years. The number of floating point operations required per processor to reduce a point disturbance by 90% is 168 on a system of 512 computers and 105 on a system of 1,000,000 computers. On a typical contemporary multicomputer [19] this requires 82.5 µs wall-clock time.

Item Type:Report or Paper (Technical Report)
Additional Information:© 1994 California Institute of Technology. This research described in this report is sponsored primarily by the Advanced Research Projects Agency, ARPA Order number 8176, and monitored by the Office of Naval Research under contract number N00014-91-J-1986.
Group:Computer Science Technical Reports
Funding AgencyGrant Number
Advanced Research Projects Agency (ARPA)8176
Office of Naval Research (ONR)N00014-91-J-1986
Series Name:Computer Science Technical Reports
Record Number:CaltechCSTR:1994.cs-tr-94-13
Persistent URL:
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:26792
Deposited By: Imported from CaltechCSTR
Deposited On:25 Apr 2001
Last Modified:03 Oct 2019 03:18

Repository Staff Only: item control page