CS61C Fall 2017 Project 3: Optimization

TAs: Julian Early and Connor Brennan

Due Monday, November 20th, 2017 @ 11:59 PM


IMPORTANT INFO - PLEASE READ


Overview

In this project you will be implementing a slower version of numpy. Your version of numpy, numc (cause, you know, this is CS61C) will be much slower than numpy, but much faster than the naive version, dumbpy. It will compile into code that can be run in Python3, and will feel very similar to numpy, however it will not have all of the fancy algorithms and opitmizations of numpy. You will be given the naive code and you will need to optimize it to run much faster. Do not expect it to be as good as numpy, but you should expect a very large speedup compared to the naive solution.

FAQ

As questions are asked, this will be updated. If you ask a question that is answered in the spec or in the FAQ, the staff reserves the right to ignore your question. It is up to you to stay up to date on the FAQ section. This FAQ will also be updated on Piazza.

I added SIMD/unrolling/pragma, why did my code get slower? - Adding these things generally helps speedup your code, but sometimes they add more overhead than they do speed up. If you are running into this issue, double check your implementation, and maybe get rid of it and try something else. You can always come back and put it in later if you think it will help then.

How long should it take to run my code? - The inital code that we give you, with no changes should take about 12 minutes to run make speedup. If you're optimization is taking longer than 15 minutes, chances are it isn't working and you should try something else.

When I run make, it tells me No rule to make target, what should I do? - You must run all make commands from the root directory of the project. It will not work in any subdirectory

There is a warning saying that it cannot uninstall things and/or that it cannot find a conda environment, what should I do? - Try running make speedup once to install the conda virtual environment if you haven't already. Once you have installed the environment, you can ignore any errors along these lines.

Are we allowed to import and use packages that we have not talked about in class? - If they are already installed on the hive machines and the code will compile without adding anything new, please feel free to use the package. Please note that that the staff reserves the right to not help you debug if you use these packages.

The measured speedup from running make speedup is much greater than when I run make check, which do I trust? The timing is done differently, make check is unreliable at measuring speed. make check will let you determine the correctness of your matrix operations. The speedup measured by make speedup will determine your grade, assuming that make check determines that your implementations are correct.

Checking for correctness with make testAll and then make test2 is slow, can I test correctness on smaller matrices first? Yes. If you look in testing/shared.h, you'll see two arrays called row_numbers and col_numbers. During testing started by make testAll, random matrices are generated in the dimensions specified by those arrays. For example, matrices of size (mxn) will be generated if row_numbers[i] == m and col_numbers[i] == n for some i. What make check does is perform all the matrix operations possible (based on dimensions matching appropriately) on randomly generated matrices of the specified dimensions. Note, as a cautionary example, that this means that if you don't specify creation of any (mx1) matrices, no outer products will be calculated, which could lead you to believe that your outer_product implementation is correct even if it isn't.

Setting Up

Getting the file

The files are hosted on github. You will need to set up your own repository. Once you have gotten into the folder you want do the project in, run the following:

git init # Only do this if you haven't made this a git repo yet
git remote add skeleton https://github.com/61c-teach/fa17-proj3-starter.git
git pull skeleton master # Pull the files to start working

Setting up your repo

If you are working alone, you need to do this, but just do it for only your login. You will need to create a new Bitbucket repository for you and your partner. This should be created in the form: proj3-(your login)-(partner login) (example: proj3-aaa-bbb).

In order to copy over your files into your new directory, run the following steps:

cd proj3-XX                  # Go inside the project directory
git remote add origin https://USERNAME@bitbucket.org/USERNAME/proj3-XXX-YYY.git
git push origin master

Getting Started

The code you will be modifying for this project is all in the performance directory. You can modify both matrix.c and matrix.h. You may NOT do the following:

You are allowed to:

The Assignment

Your job is to make the code in the performance folder run as fast as you can. Specifically you will change performance/matrix.c and performance/matrix.h. The breakdowns for what speeds give what grades are given at the end of this spec. Please use any and all tricks you know to make it run faster. You may not break the rules that are listed above and the functionality of everything must be the same as the naive version.

To test that you are functionally correct, run the following:

make check

After running this once, you can do a faster test in the future with:

make test2

This command will give you a speedup, but that is not the speedup that your grade is based on, it is only a preliminary one.

Once you have code that is functionally the same, you can check the speedup amount by running:

make speedup

Do note that this can be pretty slow. It does test your speedup first, so you can kill the process after if you don't wnat to wait for the naive version to run.

Tips and Tricks

We recommend you start out by adding loop unrolling and SIMD instructions to your code first. Once you have done that, try out OpenMP. Finally, look at cache blocking for some added performance increase

In addition to performing the tricks discussed above, we recommend you look at the way that the data is stored in the struct. You are welcome to change the struct definition, and we encourage it. However, if you do change the struct, you will need to change every function in the matrix.c file to work with the new struct. If you do not, you will probably fail some of the tests. If you are ever having seg faults, please make sure that the functionality of the matrix is the same as the naive version.

Running the code you wrote in Python3

The code you are writing does get compiled into Python3 code that can be run. Please note that this code is pretty buggy, so please bear with it. If you want to try out the code yourself, you will need to step into the virtual environment we created for this project. The following commands only work after you have run make speedup at least once. To do so, run:

source activate venv

Once you are in your virtual environment, you will need to install the packages. Run this command in the main directory of your project:

pip install .

Now your package is installed and can be imported. Checkout testing/speedup.py for information on how to use the packages.

When you are done, you can leave the virtual environment by running:

source deactivate

Extra Credit

The extra credit for this project is as follows: you will continue to use your numc code to speedup a neural net. There will be two changes for this extra credit from the rest of the project. The first is that you may modify the python/numc.c file that acts a wrapper for the python file. You may not modify the struct declaration inside of this file, but you may modify the implemention of the methods and add more methods as you see fit. Do note that you may not modify the neural net (nn/letters_neural_net.py). The second is that the grading will be on the accuracy of your neural net, not on a speedup. You can see your accuracy after you run the makecommand:

make ec

You will be graded on the accuracy of the Validation Error. If you get higher accuracy than the staff solution, you will get 1 point of extra credit. From here it will be a competion between students. Whoever has the highest accuracy will get 5 points of extra credit in total (4 for winning and 1 for probably beating the staff solution). Second place will recieve 4 points, and third will recieve 3 points.

You will need to fetch the new files to do this, you can do this by pulling from the github repo:

git pull skeleton ec

Finally, you will need to download the data to run the neural net on. You can download it here

To submit, submit performance/matrix.h, performance/matrix.c, and python/numc.c. You must submit separately to enter the contest and be eligible for extra credit. Submit with:

submit proj3-ec

Submission

There are two steps required to submit proj3-2. Failure to perform both steps will result in loss of credit:

  1. First, you must submit using the standard unix submit program on the instructional servers. This assumes that you followed the earlier instructions and did all of your work inside of your git repository. To submit, follow these instructions after logging into your -XX class account:

    cd ~/proj3-XX                             # Or where your shared git repo is
    submit proj3

    Once you type submit proj3, follow the prompts generated by the submission system. It will tell you when your submission has been successful and you can confirm this by looking at the output of glookup -t.


  2. Additionally, you must submit proj3 to your Bitbucket repository:

    cd ~/proj3-XXX                             # Or where your shared git repo is
    git add -u                           
    git commit -m "project 3 submission"       # The commit message doesn't have to match exactly.
    git tag "proj3-sub"                        # The tag MUST be "proj3-sub". Failure to do so will result in loss of credit.
    git push origin proj3-sub                  # This tells git to push the commit tagged proj3-sub

Resubmitting

If you need to re-submit, you can follow the same set of steps that you would if you were submitting for the first time, but you will need to use the -f flag to tag and push to Bitbucket:

# Do everything as above until you get to tagging
git tag -f "proj3-sub"
git push -f origin proj3-sub

Note that in general, force pushes should be used with caution. They will overwrite your remote repository with information from your local copy. As long as you have not damaged your local copy in any way, this will be fine.

Deliverables

These should come from your performance directory

matrix.h
matrix.c

If you submit anything else, it will be ignored. Additionally, if your code does not compile, it will recieve a 0. It is on you to make sure it compiles!

Grading

This project will be graded based on the amount of speedup that you get. You will not be given an autograder for this project because the test suite that your grade is based on is given to you. When you submit, we will compile your code and run it the same way that you run it when you use make speedup. Your grade will be based on the following table:

Speed Up Amount Score (as percentage)
<= 1x 0
~5x 50
~10x 75
~15x 90
>= 20x 100

Note that the inital speedups are worth the most. Later speedups will be worth less.

You should test on the hive machines, but keep in mind that others will also be doing so, and when many processes are running at once, you may not see an accurate reflection of how much you've sped up the code. Unfortunately it's difficult to work around the fact that there are orders of magnitude more students than Hive machines. When we grade your submissions we will ensure that no one else is using the hive machine. Keep in mind that your code may perform (modestly) better during grading. To figure out what machine will be best to use to test, checkout hivemind

Good luck!