CS/ECE 566 Parallel Processing
Programming Assignment 2
1 Goals
Generate a large square matrix A of size n × n. Your goal is to find the determinant of this matrix, after
performing LU decomposition of the matrix. det(A) = det(L) det(U) = 1 · det(U) =
∏n
i=1 uii.
All steps should be performed in parallel on EXTREME. The parallel code for LU decomposition is
similar to the parallel code for Gaussian elimination to solve a system of linear equations, which is given in
the book in Chapter 8.
Your goal is to solve this FIND DET problem on a mesh of processors. Please observe the following
points.
1. You may work in pairs if you so wish.
2. Remember to start early, because EXTREME is a shared machine and there are users from all over
campus. You submit jobs in batch mode, and may not get the result immediately. (During bad times,
it takes a day or more for completion of even small jobs).
3. First get the basic programs correctly running. Then you can experiment with varying parameters,
and more interesting variants of decomposing the workload and of MPI primitives.
2 Experiment
1. Write running code to solve the problem.
2. Measure the timings.
If time permits, you can experiment with different values of n and p. The actual parameter ranges you
vary will depend on various factors such as the workload on and the availability of the EXTREME
nodes, OS limits etc..
3 Input and Testing
1. The program will take as inputs: n, p. Here, p is the number of physical processors (i.e., cores) you use
on EXTREME. The array A is created by one process only. You can use a random number generator
or any other mechanism.
2. While you debug your code, please work with small data sets. Check for correctness against the serial
computation of the determinant of A.
4 Output
1. Submit a hard copy of all the files including the code file.
2. Submit a hard-copy report describing your experiment. The report must have the following
sections/information.
1
(a) Formulations: Describe each of the formulations of your parallel FIND DET in about 2 pages
each. List clearly the MPI calls you used in the implementation of each formulation.
(b) Parameter ranges: For each of the formulations, describe the ranges of the parameters you
experimented with.
(c) Results: Give the tables and plot the graphs showing the timing variations for each of the
formulations, for the ranges of parameters you used. Remember to use appropriate scales for the
graphs.
(d) Analysis: Analyse the results. Give your interpretation and reading of the results for each
formulation. You should address questions such as the following:
• Which formulation is better? under what (or all) circumstances? Why?
• Can you measure the computation time versus communication time? How do the formulations
compare with each other with respect to this breakup of the time overhead?
Explain why you observe what you observe. In particular, any anomalous observations should be
explained.
(e) Lessons: What insights you learned from this assignment.
5 Grading
The problem is reasonably well-formulated but the experimental approach is open-ended.
A non-running program may get zero credit. Your assignment will be judged on how comprehensively
and methodically you have designed and run the experiment, and reported on the results. Your insights into
the analysis of the results will also be considered in judging the assignment.
2