Home CPSC 425

Forest Fire Simulation

Due: November 26

Objective

To gain experience writing complex multi-process programs with MPI, by writing a parallel program to perform a forest fire simulation.


Forest Fire Simulation

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:

  1. A tree that is next to a burning tree will turn into a burning tree itself.
  2. A burning tree will turn into an empty space.
  3. A tree with no burning neighbors will ignite with probability $I$ as a result of a lightning strike, where $I$ is the ignition probability given to your program.
  4. An empty space will turn into a tree with probability $G \times (n + 1)$ where $G$ is the growth probability given to your program and $n$ is the number of non-burning trees neighboring this space.

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.


Program Details

Your program should take four parameters:

  1. The name of the file giving the initial configuration of the forest. This will be a plain text file 40 lines long with each line containing 80 characters. Each character will be either 'T', 'X', or ‘ ’, indicating a tree, a burning tree, and an empty space respectively.
  2. The number of generations to simulate, $N$.
  3. The ignition probability, $I$, as a real number between 0 and 1.
  4. The growth probability, $G$, as a real number between 0 and 1.

Your program should simulate $N$ generations, according to the rules above, and output the final state of the grid to stdout.


Parallelization

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.


Tips


Testing Your Program

You can use the following test files to test your program:

  1. empty.txt
  2. full.txt
  3. random.txt
  4. topfire.txt
  5. bottomfire.txt

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.


Submitting

When your program works, email the source code of the parallelized version to ifinlay@umw.edu.

Copyright © 2018 Ian Finlayson | Licensed under a Creative Commons Attribution 4.0 International License.