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
See Usage Policy.
Other (Adobe PDF (2.5MB))
See Usage Policy.
Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechCSTR:1994.cs-tr-94-13
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  this requires 82.5 microseconds wall-clock time.
|Item Type:||Report or Paper (Technical Report)|
|Group:||Computer Science Technical Reports|
|Usage Policy:||You are granted permission for individual, educational, research and non-commercial reproduction, distribution, display and performance of this work in any format.|
|Deposited By:||Imported from CaltechCSTR|
|Deposited On:||25 Apr 2001|
|Last Modified:||26 Dec 2012 14:05|
Repository Staff Only: item control page