Thread Optimization

Overview

For this assignment, you'll optimize the program MatMult.c, speeding it up by a factor of up to 15x by using threads and tiling.

Directions

Basic

  1. Read and understand MatMult.c. Comment the lines to understand the code.
  2. Build MatMult.c using -O3 optimization to create a MatMult executable. Run the executable to print out m1, m2, and prd. Calculate the value of prd[2][3] by hand, to be sure you understand how one element of prd was obtained.
  3. Alter the MatMult.c code to create and multiply matrices of 2000x2000. Comment out the printing! Use the time utility to determine how long MatMult takes to run on such matrices. This should be about 30s.
  4. What is the order of complexity of matrix multiplication? If we double the dimensions of the matrices, by what factor does run time increase?

Bronze

  1. Read MatMultThreads.cpp, reviewing in particular the Thread base class.
  2. Create a subclass MatThread derived from Thread, with member data relevant to doing a matrix multiplication, and a Run method that does the multiplication (or one thread's worth of it.) I suggest you divide the work between threads by rows of the product matrix.
  3. Run MatMultThreads with just one thread to start with, then 2, 3, and 4. Verify that the checksum matches that for MatMult in every case, that the speed of MatMultThreads with 1 thread is about the same as that of MatMult, and that you get almost 4x speedup with 4 threads.

Silver

  1. Increase the speed by another factor of 3x or so by reorganizing the matrix multiplication to respect the size of L1 data cache. With some clever thinking, you can break a big matrix multiplication into smaller submatrix multiplications. For instance, a 2000x2000 matrix multiplication task can be broken into 400 100x100 multiplications, adding the results.
  2. Reorganize the MatMultThread along these lines, and get a final speedup of 15x from the original MatMult.

Notes

This assignment is reliant on your specific processor, so make sure you know how large your L1 cache is on your specific PI in order to complete the assignment.

Because you will need to test long runs, I recommend creating a bash script that will allow you to run many sets of data at a time while you go about other work.

Questions, of course, can be asked in lab or office hours.

Submitting

Standard submission process: Discuss your results with me first, and then submit the work you've done via Canvas, including answers to each of the questions in a file Answers.pdf, and all of the source versions you created.