Open-ended Portion (70%)

Select one of the following options per team. The open-ended portion is worth a considerable fraction of the grade for the lab, and your grade depends on how thorough the process that leads to your conclusion is.

Reverse-Engineering a Mystery Memory Subsystem

In this problem, we will try to infer fundamental parameters of a memory system by running user code and measuring execution latency. This is useful for a variety of reasons:

To help guide application optimizations when the underlying microarchitecture is unknown or undisclosed.
To validate memory system performance before tape-out. Some of the most insidious bugs in computer system design are performance bugs, since applications still execute correctly but only more slowly. We would like to catch these bugs before committing a design to silicon, but without a performance model of the target machine, they may go undiscovered.
Using the same principle as above, to help validate simulation models. The common approach of split timing and functional modeling makes it possible to build highly complex cache and memory models — but it is very easy to write “correct” yet fundamentally broken timing models.

We have provided a prebuilt simulator of a machine whose data cache you cannot see. There is no configuration to inspect and no build step: the source of its cache configuration is not in your repository.

What to find

Deduce these four parameters, and defend each one with measured data:

the L1 D cache line size
the L1 D cache capacity
the L1 D cache associativity, and the number of sets that follows from it
the L1 D cache replacement policy — LRU or random

What you can observe

The cycle counter, and nothing else. Every other counter the directed portion used — loads, stores, hits, misses, writebacks — reads 0 on this build. That is deliberate, not a fault; the provided harness detects it and says so. The counter block’s control register still works, and you will need it:

write to the control register	effect
`CS152_CTL_FLUSH`	write back every dirty line, then invalidate — this is how you get a cold cache
`CS152_CTL_ZERO`	zero the counters and start counting
`CS152_CTL_STOP`	freeze the counters, so a later read describes one instant

A FLUSH is asynchronous. The harness waits for it by touching cacheable memory, which cannot be served until the walk finishes.

The harness

lab/open1/probe.c is a harness, not a starting point for an answer. It gives you:


`flush()`	cold start, and the wait for it
`build_chase(n, strideBytes)`	lay out a cyclic pointer chase of `n` nodes, `strideBytes` apart
`chase(reps, warm, cold)`	flush first if `cold`, run `warm` untimed accesses, then time `reps` more; returns cycles
`record()` / `report()`	collect up to 256 rows and print one table at the end

cd ${TESTDIR}/open1
make
/home/ff/cs152/fa26/lab2/run-mystery probe.riscv

Open-ended 1

Report the four parameters — line size, capacity, associativity and the number of sets, and replacement policy — in a single table.

Then, for each parameter, show how your experiment supports the number you report:

the experiment you ran to measure it — what you varied, and what you held fixed;

the measured numbers themselves, not only the conclusion you drew from them;

the reasoning that takes you from the data to the parameter, including what the data rules out.

Design Your Own Hardware Prefetcher

In this problem you design a hardware prefetcher for the L1 data cache, implement it as a C++ model, and measure what it buys you on a suite of kernels with deliberately different access patterns.

The machine

The cache is 4 KiB, 2-way set associative, 32-byte lines (8 words), true LRU, write-back and write-allocate, in front of a fixed-latency memory.

For this problem we add a prefetch port to the cache, with its own fill context, so a prefetch can be in flight while the core keeps hitting in the cache. That is what lets prefetching win here at all: without it, a prefetch would block the core for as long as a miss would.

Interface

lab/open2/prefetcher.cc is your template. You are writing one prefetcher per kernel, so copy it once per kernel you tackle:

cp prefetcher.cc pf_stream1.cc

Each copy gives you a class with two methods:

class Prefetcher {
public:
  // Called once, at time 0, with the geometry this simulator was built with.
  void reset(unsigned line_bytes, unsigned sets, unsigned ways);

  // Called once per cycle.  Return {false, 0} for "no request".
  PrefetchReq tick(const Access &acc, const Status &status);
};

What you may observe is the core’s demand access this cycle, and nothing else:

`Access` field	Description
`valid`	false on a cycle with no demand access
`addr`	byte address of the access
`is_write`	true for a store
`is_miss`	whether this access missed — resolved in the same cycle, not delayed

`Status` field	Description
`busy`	a prefetch of yours is in flight — issued, not yet landed
`dropped`	the request you returned last cycle was looked at and refused

More details on the prefetcher

Prefetch degree is 1. One prefetch may be in flight. You cannot run four lines ahead.
A prefetch to a line already in the cache is dropped, free of charge.
A prefetch whose victim line is dirty is dropped. Prefetches never write back.
A prefetched line does not become most-recently-used; it inherits the age of the line it replaced.
A prefetch displaces a live line. There is no prefetch buffer unless you build one in your own state, so a wrong prefetch costs you a line you might have wanted.
A demand miss to a different line cancels your in-flight prefetch.
A demand access to the line you are prefetching merges with it, so a prefetch that is merely late still helps.

Measuring: a fast loop and a real one

You write one prefetcher per kernel, each in its own file, each measured on its own kernel. One script does everything — it takes your model, a kernel, and which of the two evaluators to use:

cd ${TESTDIR}/open2

./prefetcher-runner pf_stream1.cc stream1 eval   # fast loop
./prefetcher-runner pf_stream1.cc stream1        # real cycles (default)

eval replays a synthetic copy of that kernel’s access stream against your model. It needs no RTL and no kernel binary, so it answers “am I predicting the right lines?” in about a second.

rtl builds the kernel, builds the simulator with your model, runs it twice — once with prefetching off, once on — and prints both sets of cache counters side by side with the speedup:

model: pf_stream1.cc   kernel: stream1   mode: rtl

                    +prefetch=0    +prefetch=1
  cycles                  55881          41083
  loads                    4096           4096
  hits                     3584           4095
  misses                    514              3
  miss rate             12.54 %         0.07 %

  speedup   1.3602x
  answer    sink=25161728, identical in both runs

That last line matters: a prefetcher may change when data arrives, never what the program computes. If the two runs disagree, your prefetcher is corrupting data and the speedup means nothing — the script says so and fails.

The first rtl run builds an RTL simulation of the whole SoC and takes a few minutes. After that a prefetcher model change is a relink, and the whole build-and-measure cycle is well under a minute.

Work one kernel at a time: read its .c, decide what locality it offers, write pf_<kernel>.cc, and measure it on that kernel alone.

The individual tools, if you want to drive them yourself

prefetcher-runner is a wrapper. Underneath:

make -C kernels                                   # build the kernels
make -f Makefile.eval MODEL=pf_stream1.cc         # build pf-eval
./pf-eval stream1                                 # run pf-eval on that kernel
./build-prefetcher pf_stream1.cc                  # build the simulator
./run-suite stream1                               # run the +prefetch=0/1 pair
./run-suite                                       # every kernel, one build

pf-eval links your model against a host model of the same cache and replays a kernel’s access stream. Name a kernel to evaluate just that one. It reports:

column	meaning
`misses`	the misses the kernel takes with no prefetching — the denominator
`requests`	distinct lines you asked for
`covered`	misses that a request of yours preceded
`useless`	requests no later access ever consumed. Each one evicts a live line for nothing
`accuracy`	`(requests - useless) / requests`
`coverage`	`covered / misses` — the fraction of misses you would remove

A request counts as useful if it precedes the next use of that line, so a kernel that revisits data scores on the revisits too.

The kernels

A single kernel would let one mechanism win by overfitting, which inverts the lesson. No single prediction mechanism covers this suite. A stride detector alone scores zero on two of the six. Treat each kernel as its own design problem: read its .c file, work out what kind of locality it actually offers, and design for that.

Kernel	Pattern
`stream1`	one unit-stride stream
`spatial`	the same four field offsets, in regions visited in bit-reversed (scrambled, non-sequential) order
`temporal`	one shuffled pointer ring, walked four times
`stride_big`	64-byte stride, then the same walk backwards
`tile`	short unit-stride runs, then a jump
`chase`	one pass over a shuffled ring

Submission

You are designing a separate prefetcher for each of the six kernels, each in its own file. For every one, work through the same three questions: what locality the kernel offers, what mechanism captures it, and what that mechanism actually bought.

Note that prefetching may not help on every kernel, and explaining why is a valid answer.

Open-ended 2

Results. Report, in a single table, the baseline cycles, the cycles with your prefetcher, and the speedup for every kernel, together with the cache counters (miss rate especially) for both runs of each kernel — prefetcher-runner … rtl prints all of it.

Per kernel. For each of the six:

the locality the kernel offers, and how you established that — from its source, from pf-eval, or from the counters;

the mechanism you designed for it, the state it keeps, and the address it predicts;

why the measured speedup came out where it did. Tie it to the numbers: a mechanism that predicts well and still gains nothing is a result worth explaining, not a failure to hide.

Co-Designing a Cache and a Kernel

A cache and the code that runs on it are usually designed by different people, years apart, and each is tuned against assumptions about the other. In this problem you get both sides at once: a kernel you may rewrite and a cache you may re-specify, with one budget spanning the two. Your goal is to co-design the two: choose a cache and a kernel together that give the fewest misses without going over the area budget.

The kernel is an out-of-place transpose of a 64x64 matrix of 32-bit words:

for (i = 0; i < N; i++)
  for (j = 0; j < N; j++)
    B[j*N + i] = A[i*N + j];

In this loop, the reads from A go along a row, one word after another, so they use each cache line fully before moving to the next. The writes to B go down a column instead: each write is N words past the previous one, so it lands on a different cache line. The loop doesn’t come back to those lines until the next pass of the outer loop, and by then most of them have been evicted, so almost every write is a miss.

That is the behavior you are going to optimize with software, with hardware, or with both.

What you choose

For each of the three budgets, you will choose two things together:

The kernel. You may modify transpose_blocked in ${TESTDIR}/open3/kernels.c. The most common approach is loop tiling, and the tile size is already set up as the TILE build variable, but you are free to try other optimizations.
The cache. You choose the cache’s geometry: the number of sets, the number of ways, and the line size. The geometry is fixed when the design is built, so each geometry needs its own build. To define one, add a WithL1D config to ${LAB2ROOT}/generators/chipyard/src/main/scala/cs152/CS152SodorConfigs.scala.

Do not modify transpose_naive, since it is the baseline your results are compared against. Also do not modify transpose_oblivious; it is an untuned reference that you will compare your kernel against.

The area budget

If a bigger cache cost nothing, the best answer would always be the largest cache. However, to evaluate the tradeoff, both capacity and associativity cost area:

area = capacity in bytes + 256 x ways

The second term charges for associativity. More ways reduce conflict misses, but each way needs its own tag comparator and a wider mux to select the hit, and that hardware does not get smaller when the cache does. At 256 units per way, an 8-way 1 KiB cache costs 3,072 units, which is more than a direct-mapped 2 KiB cache (2,304). As a result, associativity is expensive for a small cache and relatively cheap for a large one.

Line size is not charged. You can choose 16, 32, or 64 bytes. A longer line helps some access patterns and hurts others, so try all three.

You will submit one solution for each of these three budgets:

Budget	Largest capacity you can afford	Associativity at that capacity
3072	2 KiB	up to 4-way (8-way requires dropping to 1 KiB)
5120	4 KiB	up to 4-way (8-way requires dropping to 2 KiB)
10240	8 KiB	any, including 8-way

The legal configurations

Every geometry below fits within its budget. Configurations that are strictly worse than another at the same budget (same associativity and line size, but less capacity) are left out.

Budget	capacity	ways	line	sets	area	`WithL1D`
3072	2 KiB	1	32 B	64	2304	`WithL1D(sets = 64, ways = 1, lineBytes = 32)`
3072	2 KiB	2	32 B	32	2560	`WithL1D(sets = 32, ways = 2, lineBytes = 32)`
3072	2 KiB	4	32 B	16	3072	`WithL1D(sets = 16, ways = 4, lineBytes = 32)`
3072	1 KiB	8	32 B	4	3072	`WithL1D(sets = 4, ways = 8, lineBytes = 32)`
5120	4 KiB	1	32 B	128	4352	`WithL1D(sets = 128, ways = 1, lineBytes = 32)`
5120	4 KiB	2	32 B	64	4608	`WithL1D(sets = 64, ways = 2, lineBytes = 32)`
5120	4 KiB	4	32 B	32	5120	`WithL1D(sets = 32, ways = 4, lineBytes = 32)`
5120	2 KiB	8	32 B	8	4096	`WithL1D(sets = 8, ways = 8, lineBytes = 32)`
10240	8 KiB	1	32 B	256	8448	`WithL1D(sets = 256, ways = 1, lineBytes = 32)`
10240	8 KiB	2	32 B	128	8704	`WithL1D(sets = 128, ways = 2, lineBytes = 32)`
10240	8 KiB	4	32 B	64	9216	`WithL1D(sets = 64, ways = 4, lineBytes = 32)`
10240	8 KiB	8	32 B	32	10240	`WithL1D(sets = 32, ways = 8, lineBytes = 32)`

The table uses 32 B lines only to keep it short. The 16 B and 64 B versions of every row are also legal: the capacity, ways, and area stay the same, and only the number of sets changes. You should try them too.

To use a geometry, add it to the bottom of CS152SodorConfigs.scala, below the four configs from the directed portion:

class CS152Lab2Area5120Cap4KiB4Way extends Config(
  new cs152.WithL1D(sets = 32, ways = 4, lineBytes = 32) ++ new CS152Lab2Config)

Do not use underscores in the class name. Chipyard treats underscores in a CONFIG name as separators between config fragments, so a name like CS152Lab2Area5120_4KiB4Way makes it look for a class called 4KiB4Way, and the build fails during elaboration with a ClassNotFoundException.

Leave dramLat and hitLat at their default values. They do not change the number of misses, and changing them makes your results hard to compare with everyone else’s.

Exploring with the cache model

Each RTL simulation of this kernel takes a few minutes, and you have three budgets, about a dozen geometries per budget, and several tile sizes to try. Running all of those in RTL would take many hours.

Instead, do most of your exploration with the cache model: a small native program that runs your kernel, records the addresses it accesses, and counts hits, misses, and writebacks for a given geometry. It does not model timing, which is why it is fast. For miss counts, it gives the same answer as the RTL: misses depend only on the sequence of addresses and the cache geometry, and the model uses the same replacement policy as the RTL.

To build and run it for one geometry:

cd ${TESTDIR}/open3
make model
./model --sets 64 --ways 2 --line 32

The model uses the same TILE and N settings as the RISC-V build. To try every geometry at once, use --sweep, which prints the results as CSV:

make model TILE=8
./model --sweep > sweep.csv

Keep two things in mind when using the model:

Your kernel must access the matrices through ld_A and st_B. This is how the model sees each access. If you access the matrices directly through pointers, the model will not see those accesses, it will report too few misses, and your RTL results will not match.
The model reports slightly fewer misses for transpose_oblivious than the RTL does. The recursive kernel also accesses the stack, and the model only tracks the matrices. The loop-based kernels are not affected.

Confirming on the RTL

Use the model to choose your design, and report the RTL results. Once you have picked a configuration and a kernel for a budget, build transpose.riscv with your tile size, build the configuration, and run it:

cd ${TESTDIR}/open3
make clean
make TILE=16
cd ${SIMDIR}
make CONFIG=CS152Lab2Area5120Cap4KiB4Way -j4
make CONFIG=CS152Lab2Area5120Cap4KiB4Way run-binary-fast \
     BINARY=${TESTDIR}/open3/transpose.riscv

Run make clean whenever you change TILE. Otherwise make sees that transpose.riscv already exists and does not rebuild it, so you would run the binary built with the old tile size. The program prints the TILE it was built with (transpose: N=64 TILE=...), so check that line.

The binary runs all three kernels one after another, each starting from a cold cache, and prints the counters for each kernel separately. You only need to run one confirmation per budget, three in total.

To check that everything is set up correctly: on the 4 KiB, 2-way, 32 B configuration, the naive kernel should miss on about 4,600 of its 8,192 accesses. If your result is very different, something is wrong with your setup.

The cache-oblivious kernel

The tiled kernel you write is cache-aware: you choose TILE so that a tile fits in the cache you picked, so the code works well only for caches close to that geometry. If you change the cache, you may need a different TILE.

A cache-oblivious algorithm gets good locality without knowing the cache geometry. The usual approach is recursion: keep splitting the problem in half until the pieces are small enough to fit in the cache. The algorithm never checks the cache size; the pieces eventually become small enough to fit, whatever that size is. Because the splitting does not depend on the capacity, line size, or associativity, the same binary works well on any cache, and on every level of a multi-level cache hierarchy at the same time.

transpose_oblivious works this way: it is a recursive transpose that splits the longer side of the matrix in half and stops at a small base case. Read through it (it is short) and notice that it has no cache parameters and nothing for you to tune.

Run it at all three budgets along with your own kernel. Part of this problem is finding out how much your tuning helps compared to an algorithm that was never tuned.

For further reading, the Wikipedia article on cache-oblivious algorithms is a good introduction, and Demaine’s survey Cache-Oblivious Algorithms and Data Structures covers the model and the standard results, including this transpose. Neither is required for this lab.

Open-ended 3

Report your results in one table with six rows: your co-designed solution for each of the three budgets, and transpose_oblivious for the same three budgets. For each row, give the cache configuration, the area it uses, the kernel and its parameters, and the miss count from the RTL. As a baseline, also include the naive kernel’s miss count on each configuration you chose.

Then answer the following questions:

For each budget, what did you choose, and why? In particular, how did you spend the extra area: on more capacity, more ways, or neither?

Your three solutions will probably differ. Explain what changed from one budget to the next, and give an example of a kernel that worked well at one budget but performed badly at another. What caused the difference?

How do your tuned kernels compare to transpose_oblivious? Does tuning help, and by how much? What does tuning cost you that the cache-oblivious kernel does not?

The area model charges for ways but not for line size. What real hardware cost does this leave out? Name one configuration whose actual hardware cost is higher than the model suggests.

Include kernels.c in an appendix. The appendix does not count toward the page limit.

Feel free to reach out to your GSI if you need help understanding the cache model, the config system, or anything else regarding this problem.