Lecture 10 (10/3/2007)— Example of How to Use Parallel Constructs

()

Case Study: Molecular Dynamics

Molecular Dynamics is a form of computer simulation used in Biology and Chemistry. It models atoms and molecules and allows them to interact for a period of time under known laws of physics, giving a view of the motion of the atoms.

Problem: Simulate a box of water

Predict the behavior of biological systems
For Example: Protein Folding
  • The physical process by which a polypeptide, a liner chain of amino acids, folds into its characteristic three-dimensional structure.
  • Most reactions happen in a water based solution

Steps to Solution

0. Decide to use Simulation:

  • Simulate atomic interaction using discrete time steps and discrete values (floating point).

1. Build Data Structures & Set Initial Conditions

  • Create vectors for each atom and set the initial conditions of each:
    • Position Vectors (r) – describes the location of each atom
    • Velocity Vector (v) – describes the motion of the atom
    • Molecule Properties (m) - describes the characteristics and forces of the atom

2. Compute Forces

  • Iterate through all the atoms and calculate the forces affecting each atom
Force Vector (F) =
Bonds between atoms in a molecule (covalent bonds)
Non-bonded
  • Electro-static
  • Van der Waals (Lennard-Jones potential)
Non-bonded forces must be considered for the entire system (i.e. force drops as r−2 ) while covalent bonds only need to be considered for bonded atoms.

3. Integrate for new positions (based on current positions, velocities, and calculated forces):

F→ rt (integrate) = rt+1

4. Check Global Stability

Examine each new position to make sure the molecule stays within the bonds of the system, check for energy stability, …

5. Repeat

Loop as many times as needed to see experiment results.

Find Concurrency

Data decomposition

  • Computation of Forces may use the Super Position Principle — forces are additive (Divide and Conquer)
    • Total Forces = Bonded Forces + Non-Bonded Forces
  • Bonded Forces
    • Create a list of Bonds for each atom
A012
A103
A204
  • Compute partial force for bonded forces
 
[$[Get Code]]
  • Non-bonded forces
    • Potentially O(n2) calculations
    • Reduce the number of computations using approximations
      • For Example: Create a grid approximation
        • Build a grid structure –an acceleration structure
Approximate forces by only allowing elements of a certain distance from the molecule will be taken into account when doing force calculations.
Thus reducing total computations to O(n)
n/g = number of grids
g2 + Num_neighbors * g2  = Kg2
Kg2 * n/g = Kgn
[$[Get Code]]
New Algorithm becomes:
 
[$[Get Code]]
Next: Divide data among tasks and then sort them into their own grid cells (duplicate grid structures). Once everything is sorted, the duplicate grid structures are combined into 1.
 
[$[Get Code]]

Task Decomposition

Further Examination of the above Algorithm reveals task decomposition
  • Assign Grid
 
[$[Get Code]]
  • Find postion within vector
span class="co1">// or
[$[Get Code]]
  • Convert from Sequental to Parallel (potentially reducing calculation time (not number of computations) to O(log(n)) steps)
 
[$[Get Code]]

Scan

A simple and useful parallel building block
  • Work Efficient:
    • A parallel algorithm is work efficient if it does the same amount of work as an optimal sequential complexity
    • Scan executes log(n) parallel iterations
      • The steps do n-1, n-2, n-4,… n/2 adds each
  • Balance Tree Pattern
    • Build a balanced binary tree from the input data
Tree is not an actual data structure, but a concept to determine what each UE does at each step
  • For scan specifically:
    • Traverse down from leaves to root building partial sums at internal nodes in the tree
Root holds sum of all leaves
  • Traverse back up the tree building the scan from the partial sums
Total steps: 2 * log(n)
Total work: 2 * (n-1) adds = O(n)

Reduction

Combining many elements into one, or many into many (vectors into vector).
  • Sequential
For when reduction Operator is not associative
  • Tree Based
For when reduction Operator is associative and only one node needs the result
  • Recursive-doubling Reduction
For when reduction Operator is associative and multiple nodes need the result (faster then broadcast)

More patterns

  • Reductions
  • Scans
    • Building a data structure

More examples

  • Search
  • Sort
  • FFT as divide and conquer
  • Structured meshes and grids
  • Sparse algebra
  • Unstructured meshes and graphs
  • Trees
  • Collections
    • Particles
    • Rays