18-646: How To Write Fast Code II (Spring 2021)
Mini-Project 1 – Multicore Programming
Due: Monday, March 8th, 11:59PM EST
The goal of this project is to use your understanding of parallel computing resources in a multicore microprocessor to optimize two fully functional applications. The applications are Matrix Multiple and K-Means Clustering.
For a functional description of the applications, please refer to:
http://en.wikipedia.org/wiki/Matrix_Multiplication http://en.wikipedia.org/wiki/K-Means
The code optimization techniques you may want to consider are explained in Module 1 and Module 2 which includes:
• Cache blocking
• OpenMP pragma-based optimizations o omp parallel
o omp for
o omp atomic
o omp reduction
• Intrinsics Programming
18-646: How To Write Fast Code II (Spring 2021)
Grading Criteria
• 30% – Correctness – Correctness of the results (program output)
• 30% – Performance
o matrix_mul/omp/matrix_mul.cpp (Matrix Multiply):
Achieve at least a 2x speed up compared to the current OpenMP version (SUM of all
the testcases on matrix_mul_03.dat) o kmeans/omp_kmeans.c(K-means):
Achieve at least a 5x speed up compared to the current OpenMP version (SUM of all tests)
• 30% – Write up – For each performance optimization explored, describe clearly: o How the speed up works
o What is the expected speed up
o What is the observed speed up
o An explanation of any difference between the expected and observed speed ups
• 10% – Code quality – Good coding practices and well commented code
Guidelines for the write up:
Minimum of one 8.5×11 page write-up for each optimization. The write up should include:
• Optimization goal:
o Hardware resources being optimized toward? (cache? SIMD? multicore?) o What is the specification of the hardware you are optimizing for?
• Optimization process:
o Data considerations
o Parallelization considerations
• Optimization results:
o Performance before optimization o Performance after optimization
The three teams with the fastest implementations will present the techniques they attempted in a 10- minute presentation during the project review session.
18-646: How To Write Fast Code II (Spring 2021)
Mini-Project 1 – Setup
Step 1: Download the initial version of the code and commit to GIT (see Task 5 from Homework 1)
$ cd ~/
$ cp /afs/andrew.cmu.edu/course/18/646/MP1/18646_MP1.tar.gz ~/
$ tar xzvf 18646_MP1.tar.gz
$ ln -s /afs/andrew.cmu.edu/course/18/646/MP1/data/*.dat ~/18646_MP1/data/ $ tree 18646_MP1
18646_MP1
├── data
│ ├── kmeans01.dat -> /afs/… …/data/data/kmeans01.dat
│ ├── kmeans02.dat -> /afs/… …/data/data/kmeans02.dat
│ ├── kmeans03.dat -> /afs/… …/data/data/kmeans03.dat
│ └── kmeans04.dat -> /afs/… …/data/data/kmeans04.dat
├── kmeans
│ ├── file_io.c
│ ├── kmeans.h
│ ├── Makefile
│ ├── omp_kmeans.c
│ ├── omp_main.c
│ ├── seq_kmeans.c
│ ├── seq_main.c
│ └── wtime.c
└── matrix_mul
├── matrix_mul_01.dat
├── matrix_mul_02.dat
├── matrix_mul_03.dat
├── omp
│ ├── Makefile
│ ├── matrix_mul.cpp <<== To optimize (Matrix Multiply) │ ├── matrix_mul.h
│ └── tests.cpp
└── tests
└── testutil.h
5 directories, 20 files
<<== To optimize (K-Means)
18-646: How To Write Fast Code II (Spring 2021) Step 2: Optimize your code
• For the project “matrix_mul”, please apply your optimization only to the content of the “matrix_multiplication” function in “matrix_mul/omp/matrix_mul.cpp”.
• For the project “kmeans”, only make changes to the file “kmeans/omp_kmeans.c”.
Note: DO NOT change the function interface. Any changes in the interface could result in your work not
working in our test infrastructure and you will receive no credit.
To compile the code, simply type “make” in the appropriate project directory.
For matrix_mul:
$ cd ~/18646_MP1/matrix_mul/omp
$ make
$ ./matrix_mul -i ../matrix_mul_03.dat -o
For kmeans:
$ cd ~/18646_MP1/kmeans
$ make
$ ./omp_main -i ~/18646_MP1/data/kmeans03.dat -n 32
Step 3: Submit your optimized code ( matrix_mul.cpp and omp_kmeans.c ) and project write up to gradescope
Submit your optimized version of matrix_mul.cpp to the Matrix Multiply programming assignment on gradescope: https://www.gradescope.com/courses/241050/assignments/998372
Submit your optimized version of omp_kmeans.c to the K-Means programming assignment on gradescope: https://www.gradescope.com/courses/241050/assignments/1025865
Submit your team project writeup to: https://www.gradescope.com/courses/241050/assignments/997551