DYNAMIC LOAD BALANCING FOR PARALLELIZED PARTICLE SIMULATIONS ON MIMD COMPUTERS

The problem of load balancing for parallelized particle simulations implemented on MIMD machines is discussed and a simple dynamic load balancing algorithm is introduced. Furthermore a mapping to a deterministic cellular automaton is given which allows detailed studies of this algorithm. In particular it is shown that for strip decomposition, the time, tau, need for the system to convergence from an initially unbalanced state to a well balanced state grows like tau alpha P-alpha, with P being the number of processors and alpha = 0.089 +/- 0.009. This convergence time can be considered 'fast', enabling this algorithm to track fluctuations in the particle density as the simulation progresses.