CS107 Lab 9: C Code and Cache Performance

Lab sessions Mon Mar 13 to Thu Mar 16

Lab written by Julie Zelenski

Learning goals

After this lab, you will have

Experimented with the cache simulator features of the callgrind tool
Practiced exam-like problems on the topic of cache design

Share a computer with somebody new. Tell each other how you will spend all that free time you'll have after you're finished with CS107.

Lab exercises

Get started

Clone the lab starter project using the command

hg clone /afs/ir/class/cs107/repos/lab9/shared lab9

This creates the lab9 directory which contains various Python source files and data files.

Pull up the online lab checkoff and have it open in a browser so you'll be able to jot down things as you go. At the end of the lab period, you will submit that sheet and have the TA check off your work.

1. Callgrind

The callgrind tool (part of the valgrind suite) is a code profiler that provides statistics about instruction counts and cache efficiency. If you haven't already, see our guide to callgrind for a quick introduction on how to run callgrind and use the annotator on the callgrind.out file to prepare the profiling report. Here are two experiments to run:

Run valgrind callgrind on the swap program to generate a callgrind.out file and then run the annotator on that file:
```
myth> valgrind --tool=callgrind ./swap

==24256== Callgrind, a call-graph generating cache profiler
==24256== Command: ./swap
...

myth> callgrind_annotate --auto=yes callgrind.out.24256
// replace 24256 with your process num
```
In the callgrind report, each line is annotated with the number of instructions required to execute that line. Use those counts to identify hot spots and get a sense of the relative cost of operations. How much more expensive is calling malloc versus allocating on the stack? Is a malloc call more costly than a free call?
If you add the simulate-cache option when running valgrind callgrind, it simulates the processor caches and report on cache hits/misses. Try this on the matrix program:
```
valgrind --tool=callgrind --simulate-cache=yes ./matrix rows
```
and a second run with
```
valgrind --tool=callgrind --simulate-cache=yes ./matrix cols
```

Read the cache miss counts from the report. What is the difference in the number of data cache (D1) misses when traversing by rows versus columns?

2. Exam practice problems

There are several extra problems in Monday's lecture slides that you can do for practic of cache problems for the final exam. The slides are here, start on slide number 39. The answers are in the slides (usually on the slide(s) following the question). You can also try out the practice exam on the exams page.

Check off with TA

Before you leave, be sure to submit your checkoff sheet (in the browser) and have lab TA come by and confirm so you will be properly credited for labIf you don't finish everything before lab is over, we strongly encourage you to finish the remainder on your own. Double-check your progress with self check.

Lab 9: C Code and Cache Performance