HPC Project 3: The Monte Carlo Pattern


Computational models that use the Monte Carlo pattern model a physical phenomenon using randomness, probability, and the average of many repetitions or trials to compute "typical" behavior. However doing many trials can turn a fast program into a slow one, especially as the size of the problem (in this case, the forest size) increases.

Your homework assignment this week is to take a sequential version of this model and "parallelize" it using MPI. Download this tarball of the sequential model. You can extract its contents by opening a terminal, navigating to the folder where you downloaded the file, and entering:

   tar xvzf firestarter.tgz
Compile it using the included Makefile and then run the program.

This version uses 5000 trials for each of 101 probabilities (0, 1, 2, ... 100) to model the burning of a forest of size 20x20. When it is done, it displays the burn-probabilities and their corresponding percentage-burned values, plus a simple graph that plots the percentage-burned values against the burn-probabilities.

In the ULab

  1. Modify this program so that in addition to the percentage-burned values, it also calculates and displays the times (i.e., the number of iterations) for each burn. You may find the malloc or calloc command useful for this.
  2. Even with a "small" (20x20) forest, this sequential program takes a non-trivial amount of time to compute its results. Rewrite this program using MPI to spread the computation of these burn-percentage and time values across N processes. You should be able to develop a good parallel solution to the problem, using the patterns we have explored so far. Given that the cluster has nearly 400 cores, think carefully about how you can "parallelize" your program to maximize its scalability.
  3. Add MPI timing commands to benchmark how fast your parallel program runs in "wall clock" time.
  4. Develop, test, and debug your program, using the 20x20 forest and 1, 2, and 4 processes.

    Using 1, 2, and 4 processes, record in your spreadsheet (i) the percent-burned values and (ii) the burn-times that your program produces. Create charts for these two values, and verify that these results are consistent with those produced by the sequential version, regardless of the number of processes used.

  5. When your program is fully tested and debugged, move it to the cluster.

On The Cluster

On the cluster, build and run your program using three forest-sizes: 20x20, 40x40, 80x80 (none of which are very big compared to an actual forest).

For each forest-size:

  1. Open a new tab in your spreadsheet and record your program's run-times for 1, 2, 4, 8, 16, 32, 64, 128, and 256 processes.
  2. Create a chart that displays these run-times, with the number of processes on the X-axis and the time on the Y-axis.
Be sure to give your charts titles and label your axes.

Hand In

Hard copies of:

  1. The spreadsheet charts and data you created in this exercise;
  2. A script file in which you use cat to list your program, and use make to show that it compiles correctly.
  3. The ".o" file produced from running it on the cluster using 256 processes and the 20x20 forest.
  4. A 1-2 page analysis -- as quantitatively as possible -- of what you can deduce from this model about the behavior of a fire in a forest, and why it behaves that way, including:
Please staple these pages together and make certain that your name is on each page.


CS > 374 > Exercises > 03 > Homework Project


This page maintained by Joel Adams.