A low-cost hypercube load-balance algorithm

We have developed a divide-and-conquer approach to dynamic load balancing for a 1024-processor hypercube that requires only O(1) additional storage and O((log/sub 2/P)/sup 2/) additional operations. The balancing is done with global information rather than the nearest-neighbor information used in less effective techniques. Unlike previous global load balancers, the balancing is distributed over the ensemble rather than performed by a single processor. The algorithm has been tested using particle simulation, and is quite fast. The technique appears applicable to the efficient parallelization of Particle-In-Cell methods, finite difference and finite element methods with adaptive meshes, molecular dynamics calculations and other timestepping applications where dynamic load balancing is required.