Lab 5 - Cache Me If You Can

A load from the L1 cache can be 100 times faster than a load from main memory, even though both loads are written the same way in both C and in x86-64 assembly. In this lab, you will take advantage of such timing differences to measure multiple parameters of a real processor's CPU cache.

As part of this lab, we will also get more practice with C structs and pointers by using them to implement a linked list, which we will use as part of a benchmarking tool. At the heart of our benchmarking is one linked list memory load and its execution time:

current = current->next;

By building lists of different sizes and arranging their nodes at different addresses, we will find that the time required for traversing the list will also change. We will use these timing changes to estimate cache capacity and associativity.

Lab Overview

The lab has two main parts:

Our measurement code assumes that the cache block size for this lab is 64 bytes, the conventional block size for modern CPU caches. The starter code contains the timing and plotting machinery. Your work is to implement multiple linked list operations, run the experiments, and interpret the results.

⚠️Important! Run your measurements on krebs. Results measured on another computer will describe that other computer's caches, not the caches on krebs!

Lab Files

You should find several key files in your lab directory:

You will modify list.c, answers.txt, and the indicated L1_CAPACITY_KIB constant in associativity.c. Leave the tests and measurement code unchanged so that everyone performs the same experiments.

Part 1: Structs and Linked Lists

Defining a Struct Type

A struct groups several fields into one C value. Unlike an array, the fields of a struct may have different types, but similar to an array the fields of a struct are laid out sequentially in memory.

This lab's linked list is modeled as a list of nodes. In list.h, we define this node type as the following struct:

typedef struct node {
    struct node *next;
    unsigned char padding[CACHE_BLOCK_BYTES - sizeof(struct node *)];
} node_t;

This declaration does two related things:

The first field:

struct node *next;

stores the address of another struct node, namely, the next node in the list.

The second field is an array of otherwise unused bytes. Together, the pointer and the padding make each node_t occupy exactly 64 bytes, the size of a typical CPU cache block. Thus, each node is large enough to exactly fill one entire cache line.

Accessing Struct Fields

C has two closely related operators for accessing a struct field:

The arrow expression is shorthand for dereferencing the pointer and then selecting the field:

current->next       /* means the same as (*current).next */

Although this syntax is semantically equivalent to the arrow syntax, C programmers idiomatically use the arrow syntax in their code.

The expression &node takes the address of a struct value. Thus, if nodes is an array of structs, &nodes[3] is a pointer to the struct stored at array index 3.

Circularly Linked Lists

A conventional linked list ends when the final node points to NULL:

first -> node -> node -> node -> NULL

The timing programs instead use a circularly linked list. The final node points back to the first:

          +-----------------------+
          |                       |
          v                       |
first -> node -> node -> node ----+

The advantage of using a circular list in this lab is that it lets the benchmarking program follow pointers millions of times without the overhead of needing to check for NULL and restarting the traversal.

Implementing follow()

Complete the follow() function in list.c. It must execute:

current = current->next;

exactly steps times and return the final value of current. If steps is zero, the function should return the original pointer without following any links.

Implementing link_cycle()

Complete link_cycle() in list.c. The function must construct a linked list according to the following steps:

  1. Connect each node in nodes to the next node according to the order specified by order. The order array is of length count.
  2. Connect the final node back to the first, making the list circular.
  3. Return a pointer to the first node.

Note: the order of the nodes in the array will generally be different than the order in the linked list that you create.

This lab's experiments allocate an array of node_t structs:

nodes[0]  nodes[1]  nodes[2]  nodes[3]  ...

Because each array element is exactly 64 bytes, consecutive elements begin 64 bytes apart. However, array order and linked-list order are independent. The structs have fixed positions in the array, while their next fields determine the order in which they are visited when traversing the linked list.

For example, suppose:

order = {3, 0, 2, 1}

The resulting circular list should be:

nodes[3] -> nodes[0] -> nodes[2] -> nodes[1] -> nodes[3] ...

In other words, the structs should remain in their original array positions. Only the pointers stored in their next fields determine the order of the linked list.

The spacing Parameter

The shared link_cycle() function also receives a value named spacing. Part 1 passes spacing == 1, so the example above uses:

nodes[3], nodes[0], nodes[2], nodes[1]

If spacing == 5, the same order array would instead select:

nodes[15], nodes[0], nodes[10], nodes[5]

In general, entry order[i] should select the node at:

nodes[order[i] * spacing]

Part 2 will use this parameter to place selected structs much farther apart in the array without changing the linked-list algorithm.

Fisher-Yates Shuffle

If the program linked the nodes in increasing array-index order, it would access consecutive addresses. Processors can often recognize a regular access pattern and fetch later blocks before the program asks for them. That would make it harder to observe the access time of the cache level that actually holds the list.

Instead, our lab's benchmarking program initializes an array of node indexes:

values = {0, 1, 2, ..., count - 1}

and will use the Fisher-Yates shuffle algorithm to put those numbers in a pseudorandom order. The algorithm works by beginning shuffling the end of the array and then working toward the beginning. For i = count, count - 1, ..., 2:

  1. Choose j from 0 through i - 1.
  2. Swap values[i - 1] and values[j].

The basic loop is:

srand(seed);

for (size_t i = count; i > 1; --i) {
    size_t j = (size_t) rand() % i;
    /* Swap values[i - 1] and values[j]. */
}

After an iteration places a value at position i - 1, later iterations should not change that position again. Restricting j to the unshuffled portion of the array is essential to the correctness of the algorithm.

Implementing shuffle()

Complete shuffle() in list.c using the Fisher-Yates algorithm to shuffle the given values array. The values array is of length count.

It is important that you pass the seed argument to srand so that the same seed produces the same shuffled order on repeated runs, which keeps the experiment reproducible.

Note that, unlike in link_cycle() where we should not swap array values, in this function we should swap array values.

Testing the List Code

After implementing all three functions, run:

$ make check

The tests check the shuffle, the links between structs, the circular final link, the spacing calculation, and pointer traversal. A successful run ends with:

List tests passed 🎉

Make sure to fix all compiler warnings and failed tests before collecting any benchmarking measurements. The list_test executable includes debugging information and is compiled without optimization, so its structs, pointers, and local variables are easy to inspect in GDB. The measurement programs are compiled separately with optimizations enabled, making them more difficult to debug using GDB. Ergo, debug using the list_test executable whenever possible!

Measuring Cache Capacities

Once make check succeeds, run the Part 1 experiment:

$ make part1

This command creates two files:

The program constructs shuffled circular lists of all the required sizes and performs the same number of pointer loads for each size.

The generated CSV columns are:

list_kib,ns_per_load,million_loads_per_second

Using this generated data, plot.py plots list size against millions of pointer loads per second. Note that the vertical axis uses a logarithmic scale and that the horizontal axis is also a nonlinear scale!

Performance Drops Reveal Cache Capacities

The processor searches for data through a hierarchy:

  1. L1 is the smallest and fastest cache.
  2. L2 is larger and slower than L1.
  3. L3, on processors that have an L3 cache, is larger and slower than L2 and shared by all of the processor's cores.
  4. Main memory is larger and slower than the caches.

When the complete list fits in L1, repeated traversal is fast because the next node can usually be obtained from L1. When the list becomes too large for L1, more pointer loads must be served by L2, so the pointer-load rate drops. The same reasoning applies when the list becomes too large for later cache levels.

In a linked list, the address of the next load is stored in the current node. The processor must load the current node and read its next field before it knows which address to load next. This dependency makes the traversal time sensitive to the cache level supplying each node. Shuffling the list also avoids a simple increasing-address pattern that the processor could easily fetch ahead.

Interpreting the Capacity Plot

Look for three clear, lasting performance drops. One isolated, slow measurement is weak evidence and may simply reflect other activity on the machine.

If a run is noisy, run make part1 again and look for a boundary that persists. If the results are just never looking good, then you may have a bug in your code!

Example Capacity Output

Here is an example capacity plot generated on a different machine. Your plot will have the same axes, but the measured values will differ:

Example plot of linked-list traversal performance by list size .chart-bg{fill:#fff}.chart-grid{fill:none;stroke:#b0b0b0;stroke-width:1;stroke-opacity:.25}.chart-axis{fill:none;stroke:#222;stroke-width:1}.chart-line{fill:none;stroke:#1f77b4;stroke-width:2}.chart-point{fill:#1f77b4}.chart-text{fill:#222;font-family:Arial,Helvetica,sans-serif}.chart-tick{font-size:10px}.chart-label{font-size:12px} 48162432364048525664961282565127688961024115212801536179220483072409661448192122881638420480245762867232768101001000 List size (KiB) Million pointer loads per second

This plot reflects an L1 cache size of 32 KiB, an L2 cache size of 256 KiB, and an L3 cache size of 8 MiB. Performance plummets after exceeding the L1 cache size and again after the L2 cache size, but note that the performance also starts plummeting at, not after, 8 MiB, the L3 cache size — this is because the L3 cache is shared across other processor cores, and so our experiment cannot completely utilize it.

Part 2: L1 Associativity

Sets and Associativity

Total capacity is not the only parameter of a cache. A cache is divided into sets, and each set contains a fixed number of cache lines. Let:

The total cache capacity is:

C = S * E * B

The value E is the cache's associativity. For example, if every set has four lines, the cache is four-way set associative. If five repeatedly accessed blocks all map to one set of that four-way cache, the set cannot hold all five at once. Accesses will repeatedly replace one another, making the traversal slower.

Choosing Blocks from the Same Set

To measure associativity, you need several blocks that all map to the same L1 set. The L1 capacity you measured in Part 1 provides a convenient spacing between such blocks.

Moving ahead by one L1 capacity, i.e., by C bytes, moves ahead by:

C / B = (S * E * B) / B = S * E

cache blocks. In the set-associative cache model used in class, set numbers repeat every S blocks. Because S * E is a whole-number multiple of S, a displacement of one cache capacity must also return to the same set number.

Although S and E are still unknown, following Part 1, you do know C and therefore their product: C / B. Spacing the nodes C bytes apart will therefore place them in the same set.

Entering the L1 Capacity

Open associativity.c and locate:

#define L1_CAPACITY_KIB 0

The only change you should make to this file is to replace 0 with your Part 1 L1-capacity result in KiB.

⚠️Important! You should not include * 1024 because the benchmarking program automatically applies that factor. For example, had your benchmarking results identically matched the earlier plot, then you would want to replace 0 with 32, but your plot from benchmarking krebs should reflect different cache parameters than those reflected in aforementioned example plot.

Since each array element occupies 64 bytes, the program calculates the array-index spacing as:

spacing = L1 capacity in bytes / sizeof(node_t);

It then builds circular lists from structs at:

nodes[0 * spacing]
nodes[1 * spacing]
nodes[2 * spacing]
...

The link_cycle() and follow() functions from Part 1 are reused without modification. Only the positions of the selected structs in the array change.

Measuring Associativity

Run:

$ make part2

This command creates:

The program measures circular lists containing 1 through 20 blocks that compete for one L1 set. Look for the first clear, lasting performance drop between two consecutive block counts.

If performance remains fast through E competing blocks and drops when the experiment adds block E + 1, you can infer that one set holds E cache lines and that the L1 cache is E-way set associative.

Example Associativity Output

Here is an example associativity plot from a machine with different cache parameters than krebs. Remember to use the plot from your own experiment when answering the questions in answers.txt.

Example plot of linked-list traversal performance by competing L1 block count .chart-bg{fill:#fff}.chart-grid{fill:none;stroke:#b0b0b0;stroke-width:1;stroke-opacity:.25}.chart-axis{fill:none;stroke:#222;stroke-width:1}.chart-line{fill:none;stroke:#1f77b4;stroke-width:2}.chart-point{fill:#1f77b4}.chart-text{fill:#222;font-family:Arial,Helvetica,sans-serif}.chart-tick{font-size:10px}.chart-label{font-size:12px} 12345678910111213141516171819201002004006001000 Blocks competing for one L1 set Million pointer loads per second

This plot was generated on a machine with an 8-way set-associative L1 cache.

Implementation and Debugging Advice

Draw the Structs and Pointers

When working with linked structures, a small diagram is often more useful than staring at the code. Draw each selected array element as a box, write its array index in the box, and draw an arrow from that struct to the struct whose address is stored in next. Keep these three ideas separate:

Compiler errors can also be helpful! A program that type checks is not necessarilly correct, but a program that doesn't type check is necessarily incorrect!

Collecting Reliable Measurements

Leave the measurement programs unchanged, and do not print anything from follow() when running the final measurements. Printing during the traversal would take far longer than the memory accesses you are trying to measure, so if you put a printf() call in there for debugging, make sure to remove it before generating your final data or plots.

Remember that you are running this experiment on a shared server. Timing measurements can be affected by other programs, including measurements being performed by your classmates! Focus on large changes that persist across several measurements. If the plot contains something that doesn't look right, try rerunning the experiment before drawing a conclusion.

Memory Checking

After the tests pass, consider using Valgrind on the test program:

$ valgrind ./list_test

Useful Commands

Logistics

The assignment will be distributed on krebs.

As usual, make sure that your final code, plots, and answers have been submitted using the usual submission script. Specifically, make your your submission includes the following:

Evaluation

Your work will be graded on program correctness and experimental reasoning. In particular, evaluation will consider:

A perfect evaluation won't require that the cache parameters that you predict be exactly correct! For instance if a parameter ends up being off-by-one (or off by a power of 2 as the case may be), that is fine. What's more important is that your reasoning is well thought out.

Epilogue

Ostensibly this lab concerns using information about when cache performance plummets to infer cache parameters, but we can also use the same findings to predict the conditions in which cache performance in the programs that we write will plummet and the size of the impact in performance that we can expect.

Overall, when writing a program, try to keep the program's actively required data set as small as possible, as close together in memory as possible, and try not to lay out your data such that frequently used data items are mapped to the same cache set. In this lab we can see the penalties when we fail to do so!