CS 441/541 Introduction to Parallel
Computing
Homework #5 - 200 points
Date Assigned: July 15, 2004
Date Due:
Individual Work Only
Problem Statement:
1. Implement the Broadcast-Multiply-Roll algorithm (Fox's algorithm) for parallel matrix-matrix multiplication of square matrices uniformly distributed on square process grids (See paper by Li et. al. on the class webpage and program lab6.c from the MPI Tutorial).
a. Measure
the time taken for the matrix size 512 X 512 on process grids of size 1 X 1,
2 X 2, and 4 X 4 and plot the efficiency of the parallel algorithm.
b. Execute the parallel algorithm using the following process grids and matrix sizes and compute the scaled-speedup.
|
No. |
Matrix Size |
Process Grid |
|
1 |
512 X 512 |
1 X 1 |
|
2 |
1024 X 1024 |
2 X 2 |
|
3 |
1536 X 1536 |
3 X 3 |
|
4 |
2048 X 2048 |
4 X 4 |
2. Design and implement a parallel merge-sort algorithm. Measure the time taken for sorting integer vectors of length 1000, 5000, and 10000 and plot the efficiency of the parallel algorithm on 1-8 processors. [Graduate Student only, Bonus Question for Undergraduate Students]
Follow the instructions give at http://www.cis.uab.edu/cs541/instructions.html for accessing the cluster, compiling MPI programs, and executing these programs. See MPI man pages and tutorial slides for more information on MPI.
NOTE: 10% of the grade for each problem will be allocated for the speedup obtained. A perfectly working program producing correct results but poor performance will loose 10% of the points.
Submission
Guidelines:
Program
Documentation and Testing:
Use appropriate file names and
include comments to indicate various operations performed by the program. Your
program must have the following header information within comments:
/*
Name:
BlazerId:
Homework #
Lab Section #
*/
Source
Code and Report Submission:
Please
email the source code as attachments to cs541@cis.uab.edu
with the subject "Homework5". When you send an email to the class
account you will receive an automated response indicating that your email was
received. If you do not receive this message check with the
TA to make sure you have turned in your homework. For the analysis part
of the homework, type your answers using any text editor or word processor and
email the document (preferred formats are PS, PDF, Word, Text) along with your
source code as an attachment.
Late
Submission:
Late submissions will lose 10%
for every 24-hour period, up to a maximum of 50% (weekends and holidays count
as one 24-hour period) as per the course late submission policy. Submissions
turned in a week late will receive a score of zero and you must still turn in
this homework even if it is late to pass this course.