Dynamic load balancing of many -body molecular dynamics simulations in grid environments

In heterogeneous distributed environments such as the Grid, the available resources, namely the network and computational power, are continually changing with respect to every available node. To optimally utilize these dynamic resources, a scheduler should be able to continually adapt to the changes and suitably vary the workload and data amounts scheduled to each node. Two such scheduling algorithms are proposed in this dissertation and applied in detail to Molecular Dynamics (MD) simulations. MD, a computationally intensive problem, is used by researchers in various fields, and computational parallelism inherent in this application can be exploited in parallel and distributed environments. Nonetheless, the general ideas developed here will apply directly to any time-dependent simulation or iterative numerical technique. The proposed scheduling algorithms build and continually update a model of the distributed system, which it then uses to make decisions about how to optimally redistribute the load in the system at every time step of the MD simulation. The scheduling algorithm can additionally handle dynamic changes in the number of nodes available for computation at runtime. The performance of the scheduling algorithms has been evaluated in a heterogeneous distributed environment that we developed and implemented. One scheduling algorithm is used in conjunction with the atom-decomposition MD technique, while the other is used with force-decomposition. MD simulations based on spatial-decomposition (for short-range potentials) technique assuming heterogeneous compute power and homogeneous links exist in the literature. To the best of our knowledge, this work is the first to consider force- and atom-decomposition and shortand long-range potentials implemented on fully heterogeneous systems (dynamically changing compute power and network links). In this work, we present two force matrix transformations that are capable of exploiting the symmetries in a 3-body force matrix in both a homogeneous and a heterogeneous environment while balancing the load among all the participating processors. The first transformation distributes the number of interactions to be computed uniformly among all the slices of the force matrix along any of the axes. The transformed matrix can be scheduled using any well known heterogeneous slice-level scheduling technique. The second transformation distributes interactions to be computed uniformly over the entire volume of the force matrix allowing us to perform a block decomposition of the force matrix. The transformed force matrix can be scheduled by any block level scheduling algorithm. We also derive theoretical bounds for efficiency and load balance for prior work in the literature. We then prove some interesting and useful properties of our transformations and evaluate their advantages and disadvantages. A loop reordering optimization for our transformations is also described. The performance of an MPI implementation of the transformations is studied in terms of the Step Time Variation Ratio (STVR) in a homogeneous and heterogeneous environment