In class, we discussed Ian Foster's 4-step approach to developing MIMD programs. You are to document
your application of this technique in designing a parallelized version of the simulation on a distributed memory
system with 8 processors (no shared memory).
Keep in mind how latency and transfer time (as a function of a channel's bandwidth) are critical factors in a
message-passing model. Assume you are dealing with the idealized interconnection network described in
chapter 1.2 of Foster's book, where the cost of sending a message between two nodes is independent of
both node location and other network traffic, but is dependent on message length (so, bandwidth is constant).
You can also assume the time to send is equal to the time to receive.
You should view this problem as having two sub-problems: the updates to the G and B grids and the global
recalculation of the probability p.
Consider the following model for simulating wildfires and their impact upon forest growth over time. The
simulation is represented by an m x m grid, G. Each cell in G can be in three distinct states: empty, tree, and
burning. A cell has 8 neighbors (Moore neighborhood). Edge cells do not wrap-around and should consider
missing neighbors as always empty. At each point of time, the following evolutionary rules occur in parallel:
1. A burning cell turns into an empty cell
2. A tree will burn if at least one neighbor is burning
3. A tree ignites from lightning with probability f, even if no neighbor is burning
4. An empty cell becomes a tree with probability p
You may assume that the grid is provided initially populated with empty cells and tree cells.
A visual depiction of this model may be viewed at http://aryannayra.com/randomstuff/forestfire.html
Additionally, a second m x m grid, B, is used to record the number of fires that have occurred for each cell in
the primary grid G. When a tree catches fire in G, the corresponding cell in B is incremented. Every cell in B is
initialized to 0 when the program begins.
The probabilities f and p are provided when the simulation is started. But, the value of p will be updated over
time as follows:
After every 365th time step, p is recalculated: