Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published April 25, 2001 | Submitted
Report Open

A Parabolic Load Balancing Method

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

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.

Attached Files

Submitted - postscript.pdf

Submitted - postscript.ps

Files

postscript.pdf
Files (4.7 MB)
Name Size Download all
md5:3ff7cb26d397b6c9ef677eae789c80c0
2.1 MB Download
md5:1b47a87cf6d3b273e07699664f5465f4
2.6 MB Preview Download

Additional details

Created:
August 20, 2023
Modified:
January 13, 2024