Heuristic Dynamic Load Balancing Algorithm Applied to the Fragment Molecular Orbital Method
Authors: Yuri Alexeev (Argonne National Laboratory), Prasanna Balaprakash (Argonne National Laboratory)
Abstract: Load balancing for large-scale systems is an important NP-hard difficulty problem. We propose a heuristic dynamic load-balancing algorithm (HDLB), employing covariance matrix adaptation evolution strategy (CMA-ES), a state-of-the-art heuristic algorithm, as an alternative to the default dynamic load balancing (DLB) and previously developed heuristic static load balancing algorithms (HSLB). The problem of allocating CPU cores to tasks is formulated as an integer nonlinear optimization problem, which is solved by using an optimization solver. On 16,384 cores of Blue Gene/Q, we achieved an excellent performance of HDLB compared to the default load balancer for an execution of the fragment molecular orbital method applied to model protein system quantum-mechanically. HDLB is shown to outperform default load balancing by at least a factor of 2, thus motivating the use of this approach on other coarse-grained applications.
Two-page extended abstract: pdf