Molecular Dynamics Exercise 4

Exercise 4: The Waves are Getting Huge Out Here: Load Imbalance

Objectives

  1. Gain experience getting around one of the biggest impediments to parallel scalability, load imbalance.
  2. To think more about data layout and distribution.

You can move on when?

You have implemented a data distribution strategy that will in some part alleviate the load imbalance.

Description

Now that you have made it though implementing this algorithm for a fairly uniform set of data, now we are going to shake things up a little bit. In this exercise, we are going introduce a procedure that will artificially imbalance the number of atoms in each cell. Throughout our workshop you have heard of load imbalance and how, especially at large processor counts, can limit greatly the parallel efficiency of a program. So, after introducing this procedure, you will need to do some sort of analysis that will divide the work as evenly as possible across the set of processors. You will not be perfect, but do the best you can.

Instructions

  1. To setup the load imbalanced version of this code, one needs to replace the ComputeAtomsPerShell function (or subroutine) with the code located here for C/C++ and FORTRAN. This piece of code will take the number of atoms and create a random distribution of atoms of the total number across the whole space. The piece of code is meant for the serial version of the code, so you will need to incorporate it into the parallel code you have created.

  2. Now, with this incorporated, rerun the scaling runs from above and see how your new results vary from the previous runs.

  3. Using the information from our profiling and performance section of the workshop, profile a parallel run of the code. There should be significant difference is the run-time of each processor.

  4. Create a scheme that instead of just dividing up the work as it comes on the processors actually estimates the amount of work each cell will do, and try to balance the workload using this estimate. See if you can come up with something that will improve the performance.

Tips

  1. You will need to be able to arbitrarily assign a cell to a processor. The basic global map will not be sufficient for this, you will need to devise a local map scheme in order to build up the work you need to do.
  2. One method for dividing up the work is as follows:
    1. Run through and assign each processor at least one cell (must enforce that the number of cells is greater than the number of MPI Tasks), keeping track of how many atoms ends up in each processor.
    2. Sort the processors in order of the number of atoms on each.  
    3. If adding new particles to the cell is below a certain threshold (in this case, NParticles/NCPUS, which is the ideal number of particles per processor), assign this cell to the current processor, otherwise go to the next MPI task.
    This is the method implemented in the solution, here is some code from the solution that accomplishes this as well as a function for a QuickSort algorithm.

Questions

  1. One fairly effective strategy for balancing load across a parallel job is the so-call "master-worker" or ?bag of tasks? methods, which dynamically assign work to processors on the basis of when their current assigned work is completed. To really get this algorithm to scale to Petascale, why do you think this is not a good strategy?

Hints

  1. If you made the communication above independent of processors, redistributing the work here should be pretty straight-forward.

  2. A full solution to the exercise is available C++.