Description
Description
Your task is to parallelize general matrix multiplication (GEMM) with OpenMP 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 two functions using OpenMP:
void GemmParallel(const float a[kI][kK], const float b[kK][kJ], float c[kI][kJ]);
void GemmParallelBlocked(const float a[kI][kK], const float b[kK][kJ], float c[kI][kJ]);
GemmParallel: A parallel version of the given matrix multiplication routine using OpenMP pragmas.
Please note that some loop permutation might be needed to enable more concurrency.
GemmParallelBlocked: Blocked matrix multiplication with OpenMP. 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. Please describe every optimization you performed in the report.
Tip
● We will use m5.2xlarge instances for grading.
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/lab1
./setup.sh
make gemm
./gemm
It should run without error and finish in a few seconds.
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 OpenMP
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 first task is to implement a parallel version of GEMM. You can start with the sequential version
provided in gemm.cpp. You should edit omp.cpp for this task.
Your second task is to implement a parallel version of blocked GEMM. You should continue working
on your results from the first task. You should edit omp-blocked.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 omp.cpp omp-blocked.cpp
git commit -m “lab1: 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.
● You can run the sequential GEMM by make gemm && ./gemm sequential. Be aware that this is
very slow.
● If your code produces wrong results, make test will fail.
● Make sure your code produces correct results!
Submission
You need to report your performance results of your OpenMP 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:
● The results comparing the sequential version with the two parallel version on three different
problem sizes (1024³, 2048³, and 4096³). If you get significantly different speedup number for
the different sizes, please explain why.
● omp-blocked only : For the problem size 4096³, please quantify the impact of each
optimization, including the block size selection and any other optimization you performed.
● omp-blocked only: Please find out how many threads are supported on m5.2xlarge. Also, for
the problem size 4096³, please report the scalability of your optimized code with different
number of threads, including 1, 2, 4, etc.
● A discussion of the your results.
● Optional: The challenges you faced, and how you overcame them.
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
└
├ omp.cpp
├ omp-blocked.cpp
└ lab1-report.pdf
You can make the tarball by copying your lab1-report.pdf to the lab1 directory and running
make tar 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 parallel implementation with different problem sizes, including
but not limited to 1024³, 2048³, and 4096³. Note that we do not provide fast baselines for other
problem sizes than those three; you need to change the host code a little bit to verify against the
sequential version.
Performance (25%)
Your performance will be evaluated based on the performance of problem size 4096³. 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.
