Implementing and evaluating an efficient dynamic load-balancer for distributed molecular dynamics simulation

Introduces and evaluates a new efficient dynamic load-balancing scheme for parallel molecular dynamics simulation on distributed memory machines. It decomposes a spatial domain of particles into disjoint parts, each of which corresponds with a processor and dynamically changes its shape to keep almost the same number of particles throughout simulation. In contrast to other similar schemes, ours requires no long-distance inter-processor communications but only those among adjacent processors (and, thus, little communication overhead), whereas it still guarantees fast reduction of load imbalance among the processors. It owes these advantages mainly to the following features. (1) The sufficiently correct global load information is effectively obtained with the stepwise propagation of appropriate information via nearest-neighbor communication. (2) In addition to the global load balancing, another load-balancing procedure is also invoked on each processor without global load information in order to suppress the rapid increase or decrease of loads. Thus, information from remote processors can provide reliable values even after a certain period of delay. To evaluate the effectiveness of our scheme, we have integrated our load balancer into the publicly-available NAMD simulation system, through replacing its built-in load-balancing component. Preliminary experiments on a cluster of workstations connected through Myrinet switches shows that it successfully reduces load imbalance and improves the simulation performance