McGill University
School of Computer Science

Computer Science 308-767: Parallel Computing

Gaussian Elimination Using MPI : In this assignment, you will use what you learned about parallelizing Gaussian elimination with partial pivoting to develop a scalable message passing implementation using MPI. You should write your program in C+MPI. You may want to use some of the MPI collective communication primitives in your program.

Use problem size 6000 x 6000 to evaluate the performance of your implementation. You should randomly generate the input matrix a and solution vector b.

Your program should measure the elapsed time of your solver, which includes the elimination and back solve phases, but not the matrix initialization or answer verification.

Write a document that describes how your program works. This document should not include your programs, though it may include figures containing pseudo-code that sketch the key elements of your parallelization strategy for each implementation. Explain how your program partitions the data, work, and exploits parallelism. If your program uses collective communication, explain how; if not, explain why not. Your writeup should include a table with timing measurements for your solver on the processors which you use. Plot the parallel efficiency of your program executions. The x axis should show the number of processors. The Y axis should show your measured parallel efficiency for the execution.

Submitting your Assignment

Your assignment should be submitted in two parts.
  • A tar file containing a separate directory for each of your programs. Each directory should contain your source code and a Makefile.
  • Your writeup about the programs.
Email me a message with a text attachment containing the program and a second attachment containing your writeup (in either Word or pdf format). The program is due on Tuesday, April 3 at midnight.

Grading Criteria

  • 10% Program correctness.
  • 40% Program clarity, elegance and parallelization. The programs should be well-documented internally with comments.
  • 10% Program scalability and performance.
  • 40% Writeup. Your grade on the writeup includes the quality of the writing, whether all of the required elements are included, and the clarity of your explanations.

Due date

Friday, November 2, 2007