Link to this document's Jupyter Notebook

There are two due dates for this assignment. First, you need to set up your assignment git repository on or before March 31th so your instructor can test and make sure everything is working as expected. Second, you then need to complete the assignment instructions and then add/commit/push your files to your git repository on or before 11:59pm on Thursday April 8. Your instructor highly recommends committing early and often.

Homework 3: Genetic Search (aka Evolutionary Algorithms)

Graphical Icon representing a genetic algorithm.

In a genetic algorithm, a population of candidate solutions (called individuals, creatures, or phenotypes) to an optimization problem is evolved toward better solutions. Each candidate solution has a set of properties (its chromosomes or genotype) which can be mutated and altered; traditionally, solutions are represented in binary as strings of 0s and 1s, but other encodings are also possible.

The evolution usually starts from a population of randomly generated individuals, and is an iterative process, with the population in each iteration called a generation. In each generation, the fitness of every individual in the population is evaluated; the fitness is usually the value of the objective function in the optimization problem being solved. The more fit individuals are stochastically selected from the current population, and each individual's genome is modified (recombined and possibly randomly mutated) to form a new generation. The new generation of candidate solutions is then used in the next iteration of the algorithm. Commonly, the algorithm terminates when either a maximum number of generations has been produced, or a satisfactory fitness level has been reached for the population.

A typical genetic algorithm requires:

  1. genetic representation of the solution domain,
  2. fitness function to evaluate the solution domain.

A standard representation of each candidate solution is as an array of bits. The main property that makes these genetic representations convenient is that their parts are easily aligned due to their fixed size, which facilitates simple crossover operations. Variable length representations may also be used, but crossover implementation is more complex in this case.

Once the genetic representation and the fitness function are defined, a GA proceeds to initialize a population of solutions and then to improve it through repetitive application of the mutation, crossover and selection operators.

In this assignment, you are going to modify and improve the processing speed of a "REVERSE Conway's Game of Life" program using MPI.

The Reverse Conway's Game of life is when we have a target state which we want to reach using the forward Conway game of life rules (see HW3). The reverse problem is much harder because the math itself is not reversable. to solve this problem we will "guess" a state, forward propigate the game to the end state and then compare the target end state to our guess end state.

Consider a $50 \times 50$ Conway's GOL target. All possible states are $2^{(50 \times 50)}$ or

This is a big number and it is impossible to find a solution in a reasonable amount of time using brute force. We are going to try to solve this problem using Genetic algorithms.

✅ DO THIS: On or before March 31th Fork the instructor's repository, set the permissions, clone your fork to your HPCC account and make sure you can compile and run the software.

  1. Navigate to the Reverse_Conway repository using your web browser and hit the "fork" button (upper right corner) and fork a copy to your personal namespace.
  2. Invite your instructor to be a "member" of your forked repository by selecting the "members" setting (lower left) and inviting entering their email (colbrydi@msu.edu) and setting the role to "Reporter".
  3. Change your "Project visibility" setting to "private" which can be found under "settings"-->"General" and clicking the "expand" button next to "Visibility, project features, permissions".
  4. Copy the URL for your forked repository and paste it to the following online form on or before March 31th (so your instructor can test permissions): Git repository Submission form
  5. Clone your forked repository on the HPCC and work from there.
  6. Change to the repository directory on a development node and run the following commands to verify the code is working:
    make clean
make
make test
  7. To complete this assignment add/commit all of your changes to your forked repository on or before 11:59pm on Thursday April 8

Note: if for any reason you can not figure out git, please review the git tutorial and go to your instructors office hours. If you would like, you may "tar zip" (tgz) a backup of your repository to your instructor on the by 11:59pm on Thursday April 8.

Goals for this assignment:

By the end of this assignment, you should be able to:

Homework Assignment

For this assignment you will do the following parts:

  1. Establish Serial Benchmark
  2. Pleasantly Parallel Benchmark
  3. Consolidate the results at the end using MPI
  4. Share intermittent state using MPI.
  5. Final Report
  6. Deliverables

1. Establish Serial Benchmark

✅ DO THIS: Benchmark the code provided using the "random" setting by using the following command:

SEED=1
time ./revROC cmse2.txt $SEED

✅ DO THIS: Write a script (called timecheck.sh to run the code 10 times with 10 different input seeds. Note the average time and the best result Fitness in your report. Save the best solution as serial_best.txt.

NOTE: this will take a while. Feel free to make the script a SLURM submission script and run it on the HPCC. Just make sure you give it plenty of time (4 hours?) to finish.

✅ DO THIS: Commit the timecheck.sh and serial_best.txt files to your repository.

2. Pleasantly Parallel Benchmark

We should be able to run this code on different cores using different random seeds. Basically create lots of workers that are each searching for the best answer at the same time (and not talking to each other). When they all are done we can see which of the workers "wins".

✅ DO THIS: Write a job script (called job_array.sb) to run the program on 50 CPUs using a simple job array (see quiz1). Give each job the following:

✅ DO THIS: Review the output for all 50 jobs and note the best result Fitness in your report. Save the best solution as pp_best.txt.

✅ DO THIS: Commit the job_array.sb and pp_best.txt file to your repository.

3. Consolidate the results at the end using MPI

To make things a little simpler, I would like to split up the MPI problem into two steps. This first step we are just going to use MPI to "Consolidate" all of the answers. Generally speaking the results will not be any different from the Pleasantly parallel runs but this is the "easier" step so I think it should go first.

✅ DO THIS: Make a copy of reverseGOL.c called reverseGOL-mpi.c. Modify the makefile to compile this program using mpicc (keep the compile for the baseline reverseGOL.c).

✅ DO THIS: Modify the end of reverseGOL-mpi.c to have workers share their best result with the lead worker (rank ==0) and then have the lead worker print out the overall best result to the screen. This will involve the following steps:

  1. Set up MPI communication at the beginning the main function before the main loop.
  2. After the main loop, write an if statement to check if the current worker is the lead working (i.e. rank==0):
    • if the current worker is NOT the lead worker then send the best fitness and individual to the lead worker using two MPI_Send commands.
    • if the current worker IS the lead worker then loop over the other workers and receive their best fitness and individual fitness using two MPI_RECV commands. If the worker's fitness is better than the current best, replace the current best with the worker's solution otherwise discard that worker's solution. After the loop print out the final result.

✅ DO THIS: Write a job script (called mpi_job.sb) to run the program on 50 CPUs using MPI (mpirun). Give the job similar runtime to step 2, 100gb of memory (2gb per core). Run this on the cmse2.txt input target.

✅ DO THIS: Review the output and note the best result Fitness in your report. Save the best solution as mpi_basic_best.txt.

✅ DO THIS: Commit the mpi_job.sb, reverseGOL-mpi.c and mpi_basic_best.txt files to your repository. Also commit any changes to your makefile.

4. Share intermittent state using MPI

Both step 2 and 3 are basically pleasantly parallel (although step 3 saves us a lot of time reviewing files). The problem with these Pleasantly parallel codes is that there is no cross-communication between the search workers. one of the strengths of genetic search is that it can chase down good solutions by modifying okay ones.

In this step we are going to modify the code using MPI so that each search program can "talk" to each other and share their best results so far. This way the workers can all chase down solutions together.

There are a lot of correct ways to do this. We are going to try something simple as a starting point. After each generation and before the mutation we will have each worker share its best result so far with it's neighbor (using round robin). If the neighbor's fitness is better than our own current best, we will replace our current best with our neighbors and set our second best sbest to what was our current best.

✅ DO THIS: Modify revConway_MPI to do the following:

  1. Have each worker send the best fitness and best individual to the rank+1 neighbor. If the current worker is the last worker then have it send it's best fitness and best individual to the 0 worker (aka lead worker).
  2. Have each worker receive the best fitness and best individual from the rank-1 neighbor. If the current worker is the first worker (rank 0 aka lead worker) then have it receive it's best fitness and best individual from the last worker.
  3. Make sure you modify the program to avoid deadlock. Have the lead worker receive and then send and have all of the other workers send and then receive.
  4. If the neighbor's worker fitness is better than our current fitness, add our neighbor's individual to our population and update our best.

✅ DO THIS: Rerun our updated mpi program using the mpi-job.sh script. Review the output and note the best result Fitness in your report. Save the best solution as mpi_best.txt.

✅ DO THIS: Commit the mpi__best.txt file to your repository. Also commit any changes to your makefile.

5. Final Report

✅ DO THIS: Write a report describing what you learned (There is a template in the instructor's git repository). The report should be written in either Markdown or Jupyter notebooks.

Make a graph of the final fitness values to see what method "won" explain the graphs in your report text with a focus on any odd results you may see. Conclude with a general lessons learned.

6. Deliverables

✅ DO THIS: Prepare your files for the instructor. I recommend having two versions of the code; original serial version, MPI version. You can also have a third version for the intermediate MPI code if you did not get the file code to work. Update the provided Makefile to build all executables.

When you are done, add/commit and push all of your changes to your forked git repository. Your instructor will use the following command to compile and test your code on the HPCC:

make clean
make 
make test
sbatch job_array.sh
sbatch mpi_job.sh

Congratulations, you are done!

Submit your tgz file to the course Desire2Learn page in the HW1 assignment.

Written by Dr. Dirk Colbry, Michigan State University Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.