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 
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/