Topology Preserving Dynamic Load Balancing for Parallel Molecular Simulations

We develop a parallel simulation environment to mask the complexity of heterogeneous computing resources. We propose a dynamic load balancing algorithm, Positional Scan Load Balancing which preserves the original ordering of the problem. PSLB allows for dynamic processing powers and is suitable for embedding in a runtime system. A performance model is described and cost prediction formulae derived. We introduce crossover points at which it becomes beneficial to use the algorithm. We examine the algorithms performance on a 256 processor Cray T3D and a shared memory multiprocessor. We present results detailing overhead, performance gain, and speedup of the algorithm.