You may work on thie mini lab alone, or with 1 or 2 other students (groups of 3 or less)

A Mini Lab is one that I anticipate that you can complete in a few hours; finish or be close to finishing by the end of a Thursday lab session. The purpose of Mini labs are to introduce you to a parallel or distributed programming language/utility without having you solve a larger problem using the language/utility.

I give you only about 24 hours to complete a mini-lab because I want you to stop working on it and get back to focusing your effort on your course project. Really, don't spend more than 3 hours on this.

If you don't get a mini lab fully working, you can submit what you tried if you tried it. If you don't submit a solution, it is not a big deal. Mini Labs count very little towards your final grade, and not nearly as much as regular Labs--they are mini.

If you submit a solution, make sure to add the submission string in the README.md file and the names of your 1 or 2 partners if it is a joint solution. If you work with 1 or 2 other students, please only one of you submit your joint solution in one of your repos (the easiest way to share .c file code changes remotely is via email, just cut and paste chunks of code that have changed and email them to each other). See Submit instructions) for more details.

Contents:

Lab Details
Getting Started
Resources and Example Code
Submit

For this mini lab, you will start with a sequential implementation of matrix multiply, and then use OpenMP to parallelize the code.

Parallel Matrix Multiply

The starting point code contains a complete implementation of sequential Matrix Multiply. The code runs some iterations of multiplying to matrices together. This is an example of a kernel benchmark program: it is likely not so useful as a stand-alone program, but instead implements a common sub-operation that might be part of larger parallel programs.

Your job in this lab is to use OpenMP to parallelize the code.

OpenMP

You do not need to learn an enormous amount of OpenMP to solve this problem. You will need to use the #pragma omp parallel to fork a set of threads to do something in parallel, and you will want to add a parallel for loop and maybe some synchronization.

You should be careful to stick with the fork-join, fork-join, ..., model of OpenMP; don't do things in the parallel parts that are really not parallel or you will get some weird/unexpected behavior. Do not try to "optimize" your code by reducing fork-join blocks. You should, however, think about minimizing other parallel overheads as you design a solution; your goal is a solution designed such that there is a performance improvement from parallelization. If your 1 thread execution wins out over the multi-thread ones, think about how you can remove some parallel overhead (think of space/time trade-offs, think about synchronization costs, ...). Make sure you are comparing runs for large enough problem sizes (N and M) with enough iterations.

I encourage you to try different partitioning of all or some of the matrices and see if you get different timed results. For example, see if you can partition one or more matrices by rows or by columns across threads:

row                                  column
---                                  ------
1 1 1 1 1 1 1 1                      1 1 2 2 3 3 4 4 
1 1 1 1 1 1 1 1                      1 1 2 2 3 3 4 4 
2 2 2 2 2 2 2 2                      1 1 2 2 3 3 4 4 
2 2 2 2 2 2 2 2                      1 1 2 2 3 3 4 4 
3 3 3 3 3 3 3 3                      1 1 2 2 3 3 4 4 
3 3 3 3 3 3 3 3                      1 1 2 2 3 3 4 4 
4 4 4 4 4 4 4 4                      1 1 2 2 3 3 4 4 
4 4 4 4 4 4 4 4                      1 1 2 2 3 3 4 4 

1. Get your LabO5 ssh-URL from the GitHub server for our class: cs87-s20
2. On the CS system, cd into your cs87/labs subdirectory
3. Clone a local copy of your shared repo in your private cs87/labs subdirectory:

   cd cs87/labs
   git clone [your_Lab05_URL]
   

   Then cd into your Lab05-you subdirectory.

If all was successful, you should see the following files when you run ls:

Makefile README.md matrixmult.c

If this didn't work, or for more detailed instructions on git see: the Using git page.

Starting Point files

• Makefile: builds both openMP parallel version and sequential executables (mm_par, mm_seq).
• README.md: see notes about #defines and sizes
• matrixmult.c: full sequential implementation of matrix multiply. You will add openMP directives to parallelize it.
  NOTE: comment out #define DEBUG to turn off debugging output for larger (and timed) runs.
  NOTE: M and N dimesions are defined in the .c file, for larger sizes change their #define sizes and recompile.

Getting Started

1. I suggest first trying out my simple openMP examples in my public directory:

   cp  -r ~newhall/public/openMP_examples .
   

2. Next, take a look at the matrixmult.c file, and try compiling and running it to understand what it does.
3. Finally, try to add in some openMP code to parallelize parts of the matrix multiply program.

With the starting point code, the sizes of N and M are small and the DEBUG definition is on. This will print out matrices and debug info as the code runs.

Once you have your openMP version working, comment out DEBUG and make N and M big and try some timed runs to see if you get performance improvements with your parallel solutions. For example:

time ./mm_par 100 0
time ./mm_seq 100 0

Note: these executables take at least two command line options, the first is the number of iterations, the second specifies row-wise or column-wise partioning, and an optional third takes a partitioning block size. The row/column-wise and the block-size options are there if you want to use them, you don't have to; these are just a couple more command line options that you can use if you'd like to try different partitioning.

• Try out my simple openMP examples, you can copy them over from here:

  cp -r ~newhall/public/openMP_examples .
  

• Dive into Systems 10.7 has an overview of OpenMP with some examples.
• OpenMPlinks The tutorial is a good place to start.

• top -H (or htop) to see system usage info on a per-thread basis

• Lab Machine specs page contains information about most of the lab machines, including number of cores.
• My help pages

If you do not want to submit your solution, don't push anything to your repo.

Before the Due date, you (or only one of you in a partnership):

1. At the top of the README.md file add the following line if you are submitting a solution to this lab (and cut and paste exactly this line):

   @@@@@ WE ARE SUBMITTING THIS FOR GRADING
   

   And add the names of you and up to 2 other students whose joint solution this is, after NAMES:. For example:

   # add submission string here if you submit this for grading:
   @@@@@ WE ARE SUBMITTING THIS FOR GRADING
   # Is this a joint solution with other students?
   add names of any students who worked with you on this
   (groups of at most 3 are the limit)
   NAMES: Tia, Vasanta, Kevin
   

   (Note: I'll only grade solutions with the submission string and NAMES.)

2. push your changes to github:

   git add README.md
   git add matrixmult.c
   git commit
   git push
   

If you have git problems, take a look at the "Troubleshooting" section of the Using git page.