LEADER 00000nam 2200325 4500
001 AAI3258771
005 20081029093601.5
008 081029s2007 ||||||||||||||||| ||eng d
035 (UMI)AAI3258771
040 UMI|cUMI
100 1 Venkata, Sumanth Jannyavula
245 10 Dynamic load balancing of many-body molecular dynamics
simulations in grid environments
300 146 p
500 Source: Dissertation Abstracts International, Volume: 68-
03, Section: B, page: 1743
500 Advisers: David R. Swanson; Hong Jiang
502 Thesis (Ph.D.)--The University of Nebraska - Lincoln, 2007
520 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
520 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)
520 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
590 School code: 0138
590 DDC
650 4 Computer Science
690 0984
710 2 The University of Nebraska - Lincoln
773 0 |tDissertation Abstracts International|g68-03B
856 40 |uhttp://pqdd.sinica.edu.tw/twdaoapp/servlet/
advanced?query=3258771