Homework 1:  Due 18 January 2005

1.) What is the optimal time to broadcast a message from one node to all in a 
two-dimensional m by n torus?  (A torus is a an array that "wraps around").
For m = n = 3, draw a picture numbering the wires indicating at what stages a 
message will cross them.  Repeat this exercise for a reduction operation.

2.) Implement a parallel version of the matrix-vector multiply for a 
one-dimensional finite difference method for -u'' = f.  You don't need to 
explicitly store the matrix, just compute its action on a vector.  You
should have an array on each processor that stores the "local" components of 
the vector.  You may use C, Fortran, Python, or any other language that I can 
read and you can get MPI bindings for.

Perform a "scalability study" for your code.
Measuring the time it takes to perform the 
matrix-vector product on a vector of length N as a 
function of the number of processors.  This is a fixed problem size scaling 
result (amount of work is constant).  How does your result vary with N
(say N=10,100,1000,10000,100000...)
Also check the constant work per processor scaling -- on p processors, do the 
matrix-vector product on a vector of length p * N.  How do the results vary 
with N = 10,100,1000,10000,100000...?  with p = 1,2,3,4,5,6,7,8?

Note that if p >= 4, you are running more than one process per node.  How 
should this affect your performance?