CISC 879/PHYS 838: PARALLELIZATION FOR SCIENTIFIC APPLICATIONS
Fall 2000
MPI Programming Assignment 2
Due Date: start of class, September 14, 2000
The objective of this assignment is to
write a simple MPI program
involving matrices distributed to the processes.
A 2-dimensional binary cellular automaton consists of a
two-dimensional rectangular grid together
with an initial assignment of zeroes and ones to the
vertices, or cells, of the grid and a next-state function for updating
the values at the vertices. The updating function is applied simultaneously
to all of the cells.
Typically, the value of the next-state function at an individual cell
will depend on the current value at the grid point and the
four neighbors immediately above, below, to the right,
and to the left of the cell. However,
it is also quite common for the next-state function to depend on the four diagonally adjacent
neighbors as well - upper-left neighbor, upper-right neighbor, lower-left neighbor,
and lower-right neighbor.
John Conway's game of life is a well-known example. In it, cells with ones are ALIVE, while cells with zeroes are DEAD.
Updating corresponds to finding the next generation, and the new value of
a cell depends on all eight immediately adjacent neighbors. The
rules are the following:
a. Living cells with 1 or 0 neighbors will die from loneliness.
b. Living cells with 2 or 3 neighbors will survive into the next generation.
c. Living cells with 4 or more neighbors will die from
overcrowding.
d. Empty cells with exactly 3 neighbors will come to life.
- 1.
- Write a parallel program that simulates a 2-dimensional binary cellular automaton.
Use Conway's Life as an example to clarify your thinking, but allow for
the possibility that the update rule can be changed.
The program should take as input the order of the automaton (number of rows and
number of columns), the maximum number of generations, and an initial configuration.
After each new generation is computed, the program should print it out.
Also, print out your initial configuration.
You need to answer the following questions before programming your data
distribution.
How should the cells be partitioned among the processes? How should this
be decided?
- 2.
- Your program should dynamically allocate the appropriate space
for the matrix on each process in response to the matrix size input.
- 3.
- You should program this with two different data distributions.
- 4.
- Compile and run both versions of your program with matrix sizes of 10 x 10, 100 x 100, and 1000 x 1000,
each with 1, 4, and 8 processes.
Script the runs as specified in the What to Hand In section.
- 5.
- Comment out the print statements, and
run the program again as specified above, and
report a comparison of the timings for the two different data distributions for
the different matrix sizes and numbers of processes.
- 6.
- What to hand in.
- A hardcopy of your complete program (with routine).
- A script that shows compiling your program and running it for 1,4 and 8
processors for matrix size of 10 and number of generations=8. This is only to show correctness.
- A discussion of your timing results for the different matrix
sizes and number of processes, and the two different data distributions.
In order to get reliable timing data, you need to make sure that no one
else is using the cluster. On the DEC alpha cluster,
you should run the spyall command
just prior to making a performance run. Also, from past experience,
leaving the timings until the last evening before the assignment due date
makes getting reliable timing runs very difficult to obtain due to
the many other folks trying to get access to the cluster for timings.
Please staple all parts of your lab together, and label each piece.
Your lab will be evaluated according to the following criteria:
- 1.
- 15 pts: correctness of overall Life program
- 2.
- 5 pts: 2 different data distributions
- 3.
- 5 pts: Generality of program
- 4.
- 5 pts: Time and Space Efficiency
- 5.
- 5 pts: Timings for matrix size 10, 100, and 1000,
for 1, 4, and 8 processes
- 6.
- 5 pts: Written discussion: comparison of data distributions,
explanation of timing results
This document was generated using the
LaTeX2HTML translator Version 98.1p1 release (March 2nd, 1998)
Copyright © 1993, 1994, 1995, 1996, 1997,
Nikos Drakos,
Computer Based Learning Unit, University of Leeds.
The command line arguments were:
latex2html -split 0 mpilab2.tex.
The translation was initiated by Lori Pollock on 2000-09-03
Lori Pollock
2000-09-03