CaltechAUTHORS
  A Caltech Library Service

A Parabolic Load Balancing Method

Heirich, Alan and Taylor, Stephen (1994) A Parabolic Load Balancing Method. California Institute of Technology . (Unpublished) http://resolver.caltech.edu/CaltechCSTR:1994.cs-tr-94-13

[img]
Preview
Postscript
See Usage Policy.

2054Kb
[img]
Preview
Other (Adobe PDF (2.5MB))
See Usage Policy.

2510Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechCSTR:1994.cs-tr-94-13

Abstract

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 microseconds wall-clock time.


Item Type:Report or Paper (Technical Report)
Group:Computer Science Technical Reports
Record Number:CaltechCSTR:1994.cs-tr-94-13
Persistent URL:http://resolver.caltech.edu/CaltechCSTR:1994.cs-tr-94-13
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
Collection:CaltechCSTR
Deposited By: Imported from CaltechCSTR
Deposited On:25 Apr 2001
Last Modified:26 Dec 2012 14:05

Repository Staff Only: item control page