CS 267 Homework 0

Various Methods of Parallelization of Molecular Dynamics Simulations

Molecular Dynamics (MD) is a computational method of investigation of nanoscale-sized systems via computation of changes in trajectories of individual molecules and evaulation of ensemble-based properties.  MD simulations require a great deal of computational effort, so several methods of parallelization have been developed to shorten computational time.  The following are examples of parallelization for simulations containing simple 2-body interatomic potential functions.

1st Method - Replicated Data Algorithm
- For a system of N particles and P processors; divide the system up such that the first (N/P) particles are assigned to processor 1, the next (N/P) particles to processor 2, and so forth.

Advantages: easy to code, straightforward, even load balancing, same molecules on each processor at each time step
Disadvantages:particles may not interact with each other, low speedup

2nd Method - Spatial Domain Decomposition
- For a system of N particles and P processors, divide the domain into equally-sized subdomains; each processor is assigned to a subdomain.

Advantages: particles interact with each other, higher speedup from less memory storage, good for large systems with small time steps
Disadvantages: more difficult to code than replicated data algorithm, uneven load balancing, not good for long run times

3rd Method - Systolic Loop
- Same as replicated data, except loop is decomposed such that calculations for particle 1 and particle N are handled at the same time, then particle 2 and N-1, and so forth, since ideally low-numbered and high-numbered particles do not interact with each other.

Advantages: even load balancing, fairly straightforward, better speedup than replicated data algorithm
Disadvantages: not valid when decomposed particles interact with each other

4th Method - Spatial Domain Decomposition with Subdomain Load Balancing
- Same as 2nd method, except subdomains are sized such that each contains the same number of molecules.

Advantages: particles interact with each other, even load balancing
Disadvantages: very difficult to code, subdomains change size and shape at each time step

5th Method - Point-Centered Domain Decomposition
- Intially divide up the domain such that subdomains are of equal size.  Move the subdomains such that the center of each domain is located at the center of mass of that particular domain.

Advantages: more even load balancing than 2nd method
Disadvantages: difficult to code, overlapping occurs

6th Method - Dynamic Particle Grouping
- For a system of clusters of molecules, divide up the clusters using spatial domain decomposition.  This transforms a molecular interaction problem into a molecular cluster interaction problem.

Advantages: easier to conceptually divide systems containing large clusters of molecules, fairly even load balancing
Disadvatages: useful only for systems containing only clusters of molecules.

7th Method - Embarassingly Parallel Computations
- These are essentially P independent identical computations whose statistics are combined upon simulation completion.

Advantages: no application of parallel code, very simple
Disadvantages: useful only in equilibrium situations

Applications and Examples
 

Created by: Aaron Wemhoff on September 3, 2002.