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.
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!
You should find several key files in your lab directory:
list.c: skeleton implementations of the three functions you will complete: shuffle(), link_cycle(), and follow().list.h: the definition of the node_t struct and declarations of the three list functions.list_test.c: tests for your implementation of list.c.cache_sizes.c: the Part 1 timing experiment.associativity.c: the Part 2 timing experiment — you will replace one constant in this file after completing Part 1.plot.py: a program that converts each experiment's CSV output into a PDF plot.answers.txt: the questions you must complete.Makefile: used to build, test, and run the experiment.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.
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:
struct node { ... } defines a new struct type with fields named next and padding.typedef ... node_t gives that type the shorter name node_t. Afterward, node_t can be used like any other type name.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.
C has two closely related operators for accessing a struct field:
node is a struct value, use a period: node.next.current is a pointer to a struct, use an arrow: current->next.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.
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.
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.
link_cycle()Complete link_cycle() in list.c. The function must construct a linked list according to the following steps:
nodes to the next node according to the order specified by order. The order array is of length count.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.
spacing ParameterThe 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.
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:
j from 0 through i - 1.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.
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.
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!
Once make check succeeds, run the Part 1 experiment:
$ make part1
This command creates two files:
cache_sizes.csv: The numerical measurement data.cache_sizes.pdf: A plot of linked-list traversal performance by list size.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!
The processor searches for data through a hierarchy:
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.
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!
Here is an example capacity plot generated on a different machine. Your plot will have the same axes, but the measured values will differ:
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.
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:
S be the number of sets;E be the number of lines in each set; andB be the number of bytes in each cache block.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.
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.
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.
Run:
$ make part2
This command creates:
associativity.csv: The numerical measurement data.associativity.pdf: A plot of linked-list traversal performance by competing block count.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.
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.
This plot was generated on a machine with an 8-way set-associative L1 cache.
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:
nodes[3]&nodes[3]nodes[3].nextCompiler 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!
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.
After the tests pass, consider using Valgrind on the test program:
$ valgrind ./list_test
make: Compile the tests and both timing programs.make check: Compile and run the linked-list tests.make part1: Create cache_sizes.csv and cache_sizes.pdf.make part2: Create associativity.csv and associativity.pdf.make allparts: Regenerate both CSV files and both PDF plots.make part1-data: Regenerate the Part 1 CSV without plotting it.make part2-data: Regenerate the Part 2 CSV without plotting it.make justpdfs: Regenerate both PDF plots from existing CSV files.make clean: Remove compiled and generated files.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:
list.cassociativity.c with only L1_CAPACITY_KIB changedanswers.txt with your predictions and reasoning*.csv and *.pdf filesYour work will be graded on program correctness and experimental reasoning. In particular, evaluation will consider:
answers.txt) of the cache sizes and the L1 cache's associativity is well-reasonedA 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.
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!