Introduction to Parallel Computation Exercise 2: Message Passing Programming

Write on the Convex SPP parallel programs in Fortran or C solving the "All Pairs Shortest Path" problem. Take the sequential program as the starting point and use the MPI library to develop the parallel program in the message passing model.

1. Compile the sequential program with -O2. Measure the execution times for matrix dimensions 256 and 384 and take these times as the base times of all your comparisons with the parallel programs.
2. Write a MPI program that implements a row/column-oriented solution organizing all processors in a ring as discussed in class. Compile the program with -O2 and and measure the execution times for both input sizes and 1, 2, 4, 8, 16 processors (2ⁱ, as many as available).
3. Write a MPI program that implements a block-oriented solution organizing all processors in a matrix as discussed in class. Compile the program with -O2 and and measure the execution times for both input sizes and 1, 4, 9, 16 processors (i², as many as available).
4. For developing the MPI programs
   • call mpa -sc parallel to move to subcomplex "parallel",
   • include /usr/convex/mpich/bin in your PATH variable,
   • compile the program with mpicc or mpif77 (-O2),
   • call mpirun -np n program to run program with n processes.
   • use MPI_Wtime to measure wall clock times (see the man page),
   Manual pages are available for MPI, mpicc, mpif77, mpirun, and mpiclean and for all the MPI library calls. Various environment variables can be used to customize the execution (see the man pages).
5. Write a report documenting your results including
   • the source code,
   • execution times (numerical tables and graphical diagrams),
   • speedups (numerical tables and graphical diagrams),
   • efficiencies (numerical tables and graphical diagrams),
   • a comparison of the behavior and performance of both programs,
   • any other findings, problems, comments, etc.

Deliver your preliminary report by the first deadline shown below; be prepared to present and to discuss it in class. Based on our discussions, overwork your programs and deliver the final report by the second deadline shown below. Both reports will be used for grading.

First Report and Presentation: January 12
Final Report and Presentation: January 26