MPI Code Implementing the Midpoint Method for N-Body Particle Simulations

by John L. Weatherwax.

Introduction
This is code I have written implementing the Midpoint method, a parallelization algorithm for particle simulations. This algorithm was introduced in the paper:

As I worked on this algorithm I keep a simple document outlining any questions I had, their answers, and any additional information I felt helpful to record. This document also helped me to remember what coding still needed to be finished when, due to other commitments, there were gaps in the time I had to work on this project. You will find this document below.

Core Routines:
• Makefile: to build the entire program
  
• midpoint.c: the main routine
  
• fillSimConsts.c: assigns simulation constants (global box size, number of particles, etc)
  
• doInitialGridConstruction.c: sets up the underlying virtual processor grid
  
  • periodicGridMaps.c: determines each processor neighbors (North, South, East, etc)
    
• saveParticles.c: save particles to disk for visualization
  
• initializeNumToExport.c: initialize "to zero" how many total particles will go to each neighbor
  
• determineExportRegion.c: determine which particles at this timestep will be exported to neighbors
  
• packageParticlesForMPISends.c: store particles to be exported in temporary storage required by MPI
  
• exhangeNumberOfParticlesToSend.c: the MPI send/receives to inform neighbors of how much data to expect
  
• createSpaceForParticlesToReceive.c: allocates memory for the particles that one will receive
  
• exportParticles.c: actually exchange the particle information
  
• computeShortRangeForces.c: compute the forces will all of the data received
  
• createSpaceForForcesToReceive.c: allocates memory for any forces computed on my home particles
  
• exportForces.c: actually exchange the particle forces
  
• updatePositions.c: using the received forces update each home particles position
  
• determineEvictedParticles.c: determine which particles at this timestep need to be passed to another neighbor
  
• packageEvictedForMPISends.c: store particles to be evicted in temporary storage required by MPI
  
• exhangeNumberOfParticlesToEvict.c: the MPI send/receives to inform neighbors of how much data to expect
  
• createSpaceForEvictedParticlesToReceive.c: allocates memory for the particles that one will receive due to eviction
  
• evictParticles.c: actually exchange the particle requiring eviction
  
• updateHomeParticles.c: update the data structure associated with the new particles received and the ones evicted
  
• freeParticleExhangeMemory.c: free's the memory allocated to pass particles
  
Data Structures Etc:
• global_grid.h: data structure definition of the virtual processor grid
  
• sim_consts.h: definition of the structure that holds the simulation constants
  
Auxiliary Routines:
• parseInputArgs.c: to extract command line arguments
  
• saveBoxes.c: save boxes to disk for visualization
  
• sub2ind.c: C versions of the Matlab command of the same name
  
• ind2sub.c: C versions of the Matlab command of the same name
  
Algorithm Verification/Debugging Routines:
• sequential_short_range.c: a serial version of the short range force integrator (to test the correctness of the parallel version)
  
• supplyDebuggingInitialConditions.c: supplies some very simple initial conditions used to check codes correctness.
  
Scripts:
• r_ps.sh: script to easily run both the serial and parallel version of the code.
  
• run_mdpt.sh: script to run the parallel version of the code.
  
• cmp_algos.sh: script to easily compare the outputs of the parallel and serial version of the code.
  
• cmp_all_ts.sh: script to easily compare the outputs of the parallel and serial version of the code for all timesteps.
  
• cmp_forces.sh: script to easily compare the force calculation between the parallel and serial version of the code.
  
• cmp_all_forces.sh: script to easily compare the force calculation between the parallel and serial version of the code for all timesteps.
  
• cmp_update.sh: script to easily compare the position update between the parallel and serial version of the code.
  
• run_speed_up_timings.py: script to run the parallel and serial codes comparing runtimes needed for calculating algorithm speedup.