Descript 
146 p 
Note 
Source: Dissertation Abstracts International, Volume: 6803, Section: B, page: 1743 

Advisers: David R. Swanson; Hong Jiang 

Thesis (Ph.D.)The University of Nebraska  Lincoln, 2007 

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 timedependent 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 atomdecomposition MD technique, while the other is used with forcedecomposition. MD simulations based on spatialdecomposition (for shortrange 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 atomdecomposition and shortand longrange 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 3body 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 slicelevel 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 

School code: 0138 

DDC 
Host Item 
Dissertation Abstracts International 6803B

Subject 
Computer Science


0984

Alt Author 
The University of Nebraska  Lincoln

