MPI is widely used in scientific computing where researchers use parallel programs to model some aspect of the real world. Many of these involve 2D or 3D spaces which are partitioned into sections divided among processors. These simulations include weather models, diffusion models (such as the spread of disease), and physics simulations.
This program will provide a relatively simple example of such a simulation. Specifically, it will simulate a forest of trees where lightning occasionally strikes a tree causing it to catch on fire. If a burning tree is next to other trees, they will catch on fire as well. New trees will occasionally start growing in the forest too.
Your job is to simulate the forest given its initial configuration of trees, the probability that a tree will be struck by lightning, and the probability that a new tree will begin growing.
For our purposes, the forest grid will consist of 40 rows and 80 columns. Each spot in the grid can either be empty, have a tree in it, or have a burning tree in it. The simulation consists of successive generations. At each generation, the following rules are applied:
Here "neighbors" refers to positions in the grid that are to the left, right, top, bottom or diagonal of the given position. Each position in the grid has eight neighbors (except for the edges and corners of the forest).
Note that all of these rules should be applied independently. This means that all of the actions should be carried out each generation regardless of any other changes made that generation. For example, if there is a tree which will become a burning tree in the next generation, it should still count as a tree for all other decisions made this generation, and only become burning at the start of the next generation.
Your program should take four parameters:
Your program should simulate $N$ generations, according to the rules above, and output the final state of the grid to stdout.
You should use MPI in your program to break the grid into different regions that each process is in charge of simulating.
Most of the work in each process is independent of the others, however the edges of each region must be shared with the adjacent regions - in order to calculate the neighbors of each location in the grid.
Because a singe row of a 2D array can be shared with a single MPI call, it is much easier and faster to break the grid into regions based on rows.
So, for example, if the number of processes is two, the first would work on the first twenty rows, and the second would work on the second twenty. The middle two rows would need to be shared between the two processes.
Your program should work with 1, 2, 4, or 8 processes.
You can use the following test files to test your program:
To test that your program is passing data correctly between processors, use the topfire.txt and bottomfire.txt input files, with 0 for both $I$ and $G$. The fire should spread throughout the whole forest. This is the result of running topfire.txt for 35 generations.
If you get these results for every number of processes, it's likely you are doing the message passing correctly!
You should also test the $I$ and $G$ variables to see that they influence the simulation. A good starting point for testing out the simulation is:
mpirun -np 8 a.out random.txt 1000 0.001 0.001
This should generally produce sparse forests with no or few active fires. If you use time(NULL) + rank as your initial seed, you will get different results each time you run the program. Increasing $I$ will increase the number of fires, thus decreasing the number of trees. Increasing $G$ will increase the number of new trees grown, but also increase the number of fires since more trees will catch fire. Play with these variables to see that your simulation behaves as expected.
When your program works, email the source code of the parallelized version to firstname.lastname@example.org.
Copyright © 2018 Ian Finlayson | Licensed under a Creative Commons Attribution 4.0 International License.