Dynamic Load Balancing for Peta-Scale Quantum Monte Carlo Applications

Diffusion Monte Carlo is the most popular Quantum Monte Carlo method used for obtaining accurate results. Unlike with simpler Monte Carlo techniques, load imbalance can be a significant factor affecting its performance on massively parallel machines. We propose a new dynamic load balancing technique and evaluate it theoretically and empirically. An important feature of this algorithm is that the load can be perfectly balanced with each process receiving at most one message. It is also optimal in the maximum size of messages received by any process. We optimize its implementation to reduce network contention, and provide empirical results on the peta-flop Jaguar supercomputer at ORNL showing up to 30% improvement in performance on 120,000 cores com pared with existing methods for this problem . The contribution of this work lies in proposing an efficient load balancing algorithm which can be used by applications dealing with independent tasks requiring identical computational effort.