Cache Optimization

Overview

For this assignment, you will explore optimizing the cache performance of program ImageMatcher.c, on your Pi or another cache-based machine.

Directions

Basic

  1. Read and understand ImageMatcher.c. Comment the lines to understand the code. Build it using -O3 optimization to create an ImageMatcher executable.
  2. Use the time utility to determine how long ImageMatcher takes to run with 16000 grids. time ImageMatcher 16000
  3. Create ImageMatcherChars.c, which is just like ImageMatcher.c, but uses a simple char value for vals, instead of long longs. Recompile and run it. Be sure the check sum matches for both versions. You should see about a 4x speedup. This is not due to faster computation.
  4. Run cachegrind on the two ImageMatcher versions to see what's going on with L1 cache, and explain why there is such a difference.

Bronze

  1. Speed up ImageMatcher on a grid count of 16000 by a factor of at least 3 by loop-tiling. Create ImageMatcherTiled.c to make it easier to experiment with different tile sizes. This version has a second commandline argument for the tile size.
  2. Verify that the ImageMatcherTiled output is the same as that for ImageMatcher, including checksums.
  3. Experiment to find an optimal tile size. Explain why this tile size produces the best results.

Silver

  1. Increase the image dimensions for ImageMatcherTiled.c to 256x256. Reduce the test size to 1000 to compensate.
  2. Try optimizing a tile size for this case. You should find you can get only modest speedup regardless of tile size. (Compare performance with various tile sizes vs performance of ImageMatcherTiled 1000 1000, which effectively turns off tiling.) Why is this? What is causing even the modest speedup?

Gold

  1. Revise the tiling system, creating ImageMatcherTiled2.c so that you can again improve speed by 3x with appropriate tiling.

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.