Description
Description
Your task is to parallelize general matrix multiplication (GEMM) with MPI based on the sequential
implementation we have provided. Specifically, for matrix multiplication C[I][J] = A[I][K] × B[K][J] ,
you will need to implement a blocked matrix multiplication function using MPI:
void GemmParallelBlocked(const float a[kI][kK], const float b[kK][kJ], float c[kI][kJ]);
You should select the block size with the best performance when you submit this lab. You are
welcome to add any other optimization to further increase the performance. However, you may not use
any OpenMP pragma in your code. Please describe every optimization you performed in the report.
Caution: All three matrices are created and initialized ONLY at processor 0 (see main.cpp for details).
That means your code need to explicitly send (part of) matrices a and b from processor 0 to other
processors. After the computation, processor 0 should collect the data from all processors and store
it in matrix c. The correctness and performance will be assessed at processor 0.
Tip
● We will use m5.2xlarge instances for grading.
● You can assume the matrix sizes are multiples of 1024 (e.g. 1024×2048 * 2048×4096 =
1024×4096)
● You can assume the number of processors is a power of 2
Preparation
Create an AWS Instance
Please refer to the tutorial slides and create an m5.2xlarge instance with a Ubuntu 18.04 AMI.
Please use your AWS educate classroom account for this lab.
Run Baseline GEMM
We have prepared the host code for you at GitHub. Log in to your instance and run the following
commands:
git clone https://github.com/UCLA-VAST/cs-133-19w -o upstream
cd cs-133-19w/lab2
./setup.sh
make gemm
./gemm
It should finish in a few seconds with a huge error since you haven’t implemented anything.
Tips
● To resume a session in case you lose your connection, you can run screen after login.
● You can recover your session with screen -DRR if you lost your ssh connection.
● You should stop your instance if you are going back and resume your work in a few hours or
days. Your data will be preserved but you will be charged for the EBS storage for $0.10 per GB
per month (with default settings).
● You should terminate your instance if you are not going to back and resume your work in days
or weeks. Data on the instance will be lost.
● You are recommended to use private repos provided by GitHub. Do not put your code in a
public repo.
Create Your Own GEMM with MPI
If you have successfully launched an instance and run the baseline, you can start to create your own
GEMM kernel. The provided code will generate the test data and verify your results against a baseline
fast GEMM implementation.
Your task is to implement a parallel version of blocked GEMM. Your program should be based on your
parallelization from lab 1. You should edit mpi.cpp for this task.
Tips
● To check in your code to a private GitHub repo, create a repo first.
git branch -m upstream
git checkout -b master
git add mpi.cpp
git commit -m “lab2: first version” # change commit message accordingly
# please replace the URL with your own URL
git remote add origin git@github.com:YourGitHubUserName/your-repo-name.git
git push -u origin master
● You are recommended to git add and git commit often so that you can keep track of the
history and revert whenever necessary.
● If you move to a new instance, just git clone your repo.
● Run make test to re-compile and test your code.
● If make test fails, it means your code produces wrong result.
● Make sure your code produces correct results!
Submission
You need to report your performance results of your MPI implementation on an m5.2xlarge
instance. Please express your performance in GFlops and the speedup compared with the sequential
version. In particular, you need to submit a brief report which summarizes:
● Please briefly explain how the data and computation are partitioned among the processors.
Also, briefly explain how the communication among processors is done.
● Please analyze (theoretically or experimentally) the impact of different communication APIs
(e.g. blocking: MPI_Send, MPI_Recv, buffered blocking: MPI_Bsend, non-blocking: MPI_Isend,
MPI_Irecv, etc). Attach code snippets to report if you verified experimentally. Please choose
the APIs that provides the best performance for your final version.
● Please provide the performance on three different problem sizes (1024³, 2048³, and 4096³). If
you get significantly different throughput number for the different sizes, please explain why.
● Please report the scalability of your program and discuss any significant non-linear part of
your result. Note that you can, for example, make np=8 to change the number of processors.
Please perform the experiment np=1, 2, 4, 8, 16, 32.
● Please discuss how your MPI implementation compare with your OpenMP implementation in
lab 1 in terms of the programming effort and the performance. Explain why you have observed
such a difference in performance (Bonus +5).
You will need to submit your optimized kernel code. Please do not modify or submit the host code.
Please submit to CCLE. Please verify the correctness of your kernel before submission.
Your final submission should be a tarball which contains the following files:
.tar.gz
└
├ mpi.cpp
└ lab2-report.pdf
You should make the tarball by copying your lab2-report.pdf to the lab2 directory and running
make tar UID=. If you made the tarball in other ways, you should put it in the lab2 directory
and check by running make check UID=.
Grading Policy
Submission Format (10%)
Points will be deducted if your submission does not comply with the requirement. In case of missing
reports, missing codes, or compilation error, you might receive 0 for this category.
Correctness (50%)
Please check the correctness of your implementation with different number of processors and
problem sizes, including but not limited to 1, 2, and 4, and 1024³, 2048³, and 4096³, respectively.
Performance (25%)
Your performance will be evaluated based on the performance of problem size 4096³, with np=4. The
performance point will be added only if you have the correct result, so please prioritize the
correctness over performance. Your performance will be evaluated based on the ranges of throughput
(GFlops). We will set five ranges after evaluating all submissions and assign the points as follows:
● Better than TA’s performance: 25 points + 5 points (bonus)
● Range A GFlops: 25 points
● Range B GFlops: 20 points
● Range C GFlops: 15 points
● Range D GFlops: 10 points
● Speed up lower than range D: 5 points
● Slowdown: 0 points
Report (15%)
Points may be deducted if your report misses any of the sections described above.
