High Performance Scientific Computing	cs392
Lab 3	Fall 2007

Matrix Multiplication

This lab explores a seminal application used in scientific computing. Matrix Multiplication is used in image processing, graphics, as well as the solution of a linear system. Of particular interest is the tri-diagonal matrix which emerges in stencil calculations. A set of files will be made available as input to your applications; your goal is to develop a sequential and a parallel version.

Please proceed in the following sequence:

1. Design and implement a sequential version of matrix multiplication; consider a simple dot product first :-)
2. Profile the sequential code on at least two machines in the lab (you may want to try the extremes you discovered in Lab 1) -- we simply need a rough measure of the realized performance for the sequential version.
3. Now develop the parallel version using MPI -- you may choose to partition, replicate or some other strategy
4. Profile the parallel version, developing a plot of execution time vs. process count
5. Extra: implement two parallel strategies and compare (as a good computational scientist should)
6. Extra: implement the a parallel version that uses pipelining
7. Extra: implement the classic sequential version using Strassen's approach (recursive tiles); parallel anyone?

You will be asked to demonstrate your work for the instructor and answer any questions. You will also generate a report of your findings. You are welcome to collaborate, to do library research, even ask other science/math professors for help (at their convenience) -- you might even ask for real data.