ECE 485/585 last-level cache simulation

A SystemVerilog model of the last-level cache (LLC) for a processor that can share memory with up to three other processors. The cache is 16 MB, 64-byte lines, 16-way set associative, write-allocate, and uses the MESI coherence protocol with a pseudo-LRU (PLRU) replacement policy. The model does not store data, only tags and MESI state, since cache behavior (hits, misses, evictions, state transitions) is independent of the data itself, per the project specification.

Repository structure

ECE585_LLC-Simulation/
├── docs/
│   ├── LLC.png                     # System architecture diagram
│   └── project_description.pdf     # Course project specification
├── src/
│   ├── llc_cache.sv                 # Top-level simulation module
│   └── llc_params.sv                # Cache parameters, MESI/bus/message codes
├── traces/
│   ├── t0.din ... t4.din            # Hand-written sanity traces
│   └── random_100_ops.din           # Randomly generated 100-operation trace
├── transcripts/
│   ├── t0_silent_run.txt
│   ├── t0_normal_run.txt
│   ├── random_100_ops_silent_run.txt
│   └── random_100_ops_normal_run.txt
└── README.md

Architecture

Processor 0 is the one modeled by this simulation. Its CPU issues requests to its L1 cache, which forwards misses to the LLC implemented here. The LLC connects to the shared system bus, the same bus that Processors 1 through 3 and main memory are connected to. Bus operations issued by this LLC and snooped bus operations from the other processors are both modeled, but the other processors' internal caches are not simulated, only their effect on this LLC via the snoop interface.

Cache parameters

Parameter	Value
Address width	32 bits
Cache line size	64 bytes
Total capacity	16 MB
Associativity	16-way
Number of sets	16384
Offset bits	6
Index bits	14
Tag bits	12
PLRU tree bits per set	15 (assoc - 1)

These are declared as parameter/localparam in llc_params.sv, so changing assoc, cache_line_size, or capacity automatically re-derives the address split and the PLRU tree width.

Trace file format

Each line of a trace file is n address, where address is hex without a leading 0x. The command codes are:

Code	Meaning
0	L1 data cache read request
1	L1 write request
2	L1 instruction cache read request
3	Snooped read request
4	Snooped write request
5	Snooped read with intent to modify (RWITM)
6	Snooped invalidate command
8	Clear the cache and reset all state
9	Print contents and state of each valid line

Codes 0 and 2 are both treated as L1 read requests by the LLC, since the distinction (data vs. instruction fetch) only matters to L1, not to LLC hit/miss/coherence behavior. Codes 0, 1, and 2 update the reported statistics; codes 3-6 update MESI state and PLRU but are not counted as cache reads, writes, hits, or misses, since those statistics describe the LLC servicing its own processor, not its response to other caches' bus traffic. Code 9 does not end the simulation and does not affect statistics.

Running the simulation

vlib work
vlog src/llc_params.sv src/llc_cache.sv
vsim -c llc_cache -do "run -all; quit" +Mode=NORMAL +FILE_NAME=traces/t0.din

Mode is SILENT (default) or NORMAL, and FILE_NAME selects the trace, both via $value$plusargs, so no recompilation is needed to change either. In SILENT mode only the cmd-9 tables and the final RESULTS block are printed. In NORMAL mode every bus operation, snoop result, L2-to-L1 message, and PLRU update is also printed.

How address mapping works

Addr_Mapping splits each 32-bit address into:

• Offset = A[5:0]
• Index = A[19:6]
• Tag = A[31:20]

The index selects one of the 16384 sets; the tag is compared against all 16 ways in that set to determine a hit or miss.

How Cache_op dispatches a command

For every trace line, Cache_op first handles the two non-MESI commands. cmd == 8 calls Reset_stat, which zeroes all four statistics counters, sets every way in every set to state I with tag 0, clears every PLRU tree to 0, and clears cache_copy, the snapshot array used by Print_stat. cmd == 9 calls Print_stat, which scans every set and way and prints a row for each way whose state is not I, using cache_copy for the stored address and the live cache array for state and tag.

For any other command, it scans the 16 ways of the indexed set for a way whose tag matches and whose state is not I. The result, way, an index 0-15 or -1, determines which of the two paths below runs.

L1 request path (commands 0, 1, 2)

A hit increments num_hit. A miss increments num_miss, calls victimWay to choose a way to replace, sends MessageToCache(EVICTLINE, A) to notify L1 that this line is being evicted from the LLC, and writes the new tag into that way.

Either way, MESI_Protocol is then called, L1RdReq for commands 0 and 2, L1WrReq for command 1, to compute the new MESI state. num_reads is incremented for commands 0 and 2, num_writes for command 1. PLRU_Update marks the accessed way as most recently used, and cache_copy is updated with the address, new state, and tag for Print_stat.

Snooped operation path (commands 3-6)

The current state cur is read from cache[Idx].Way[way].state if a matching way was found, or I if not, meaning this LLC does not have the line. MESI_Protocol dispatches to SnoopedRdReq, SnoopedWrReq, SnoopedRdWithIntent, or SnoopedInvalidate based on the command, which computes the snoop result, NOHIT, HIT, or HITM, from cur and the line's new state. PutSnoopResult reports that result. If the line was valid and the new state is I, MessageToCache(INVALIDATELINE, A) is sent to L1 so that L1 drops its copy too, maintaining inclusivity. Snooped operations do not change the statistics counters or the PLRU tree, since they don't represent this cache's own read or write traffic.

MESI protocol behavior

L1 Read (command 0 or 2), function L1RdReq

A hit causes no bus operation; the line's state is returned unchanged. A miss issues BusOperation(READ, A). If the snoop result is HIT or HITM, the line enters S, since another cache has a copy; otherwise it enters E, since this is the only copy.

L1 Write (command 1), function L1WrReq

A miss issues BusOperation(RWIM, A), read with intent to modify, since the line isn't present yet and other copies must be invalidated; the new state is M. A hit on S is an upgrade from a shared, clean copy to exclusive, modified. No data needs to be fetched, only other caches need to drop their copies, so this issues BusOperation(INVALIDATE, A); the new state is M. A hit on E or M is already exclusive, so no bus operation is needed; the new state is M, a no-op if already M.

Snooped Read (command 3), function SnoopedRdReq

This cache reports its snoop result based on its current state and downgrades to S if it held the line, since another cache is now also reading it. M reports HITM and moves to S, since this cache had the only valid, modified copy. E reports HIT and moves to S. S reports HIT and stays S. I reports NOHIT and stays I.

Snooped Write, RWITM, and Invalidate (commands 4, 5, 6)

All three follow the same pattern. M reports HITM, E or S reports HIT, I reports NOHIT. If the line was valid, not I, it is invalidated and MessageToCache(INVALIDATELINE, A) is sent to L1. The resulting state is always I, since in each case another cache is taking ownership, write or RWITM, or explicitly asking this cache to drop the line, invalidate.

How PLRU replacement works

Each set has a 15-bit tree for its 16 ways, assoc - 1 bits. Each tree node corresponds to one binary decision in the path from the root to a way, and stores which side of that decision is currently the least-recently-used direction. A 0 means the victim search should go left at that node, a 1 means it should go right.

PLRU_Update(set, way) walks the tree from the root along the path to way, and at each node along that path, sets the bit to point away from the subtree that was just accessed. The tree always points toward the side that was not most recently touched.

victimWay(set) walks the tree from the root, following the 0/1 bits at each node, 0 meaning go left and 1 meaning go right, and returns the way at the resulting leaf. Because PLRU_Update always points the tree away from the most recently accessed way, victimWay never returns a way that was the most recent access, approximating LRU without tracking a full access history.

For an initially empty set, repeated misses produce victim ways in the order 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15, the bit-reversal permutation of 0-15. This is the expected behavior of a correct binary-tree PLRU under sequential misses and is visible in the t2, t3, and t4 transcripts.

Bus operations, snoop results, and L2-to-L1 messages

Three numeric code sets, defined in llc_params.sv, drive the printed output in NORMAL mode, matching the message text required by the project specification.

Bus operations, via BusOperation, print as BusOp: <code>, Address: <addr>, Snoop Result: <code>, where the operation code is READ=1, WRITE=2, INVALIDATE=3, or RWIM=4.

Snoop results, via GetSnoopResult and PutSnoopResult, are NOHIT=0, HIT=1, HITM=2. GetSnoopResult derives the result deterministically from Address[1:0], 00 maps to HIT, 01 maps to HITM, anything else maps to NOHIT, so any trace's snoop behavior is fully determined by the addresses in that trace and is easy to vary for testing all three outcomes.

L2-to-L1 messages, via MessageToCache, print as L2: <code> <addr>, where the message code is GETLINE=1, SENDLINE=2, INVALIDATELINE=3, or EVICTLINE=4. Only EVICTLINE, on every LLC miss-allocation, and INVALIDATELINE, on snooped operations that force a valid line to I, are used by this model.

Design decisions and assumptions

Codes 0 and 2 are both handled as L1 read requests; the LLC does not distinguish data from instruction fetches.

The S to M write-hit upgrade is modeled as BusOperation(INVALIDATE, A) rather than introducing a fifth bus operation type, since invalidating other sharers without transferring data is exactly what INVALIDATE represents and keeps the model within the specification's four bus operation types.

GetSnoopResult is address-bit-based rather than table- or counter-based, so the trace file itself fully determines and documents every test case.

Inclusivity between the LLC and L1 is maintained by sending EVICTLINE on every LLC-side eviction and INVALIDATELINE whenever a snooped operation invalidates a line that was previously valid in the LLC.

Verification

A Python re-implementation of the MESI dispatch, PLRU update and victim logic, and statistics counting was used as an independent reference model. All results below were confirmed to match between the SystemVerilog simulation and the reference model, and the full transcripts are in transcripts/.

Trace	Reads	Writes	Hits	Misses	Hit ratio	Notes
t0.din	2	0	1	1	0.50	second read hits the first line
t1.din	0	0	0	0	0.00	cmd 8 reset zeroes counters after the first print
t2.din	16	0	0	16	0.00	16 distinct tags into set 0; all-cold misses; states alternate S/E per GetSnoopResult
t3.din	16	0	0	16	0.00	same as t2 but using cmd 2; identical victim sequence into set 1
t4.din	0	16	0	16	0.00	16 writes into set 2, all RWIM misses, all end in M
random_100_ops.din	11	4	1	14	0.07	mixed cmd 0-6 with three cmd 8 resets across 4 sets

For t2, t3, and t4, the victim way sequence is 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15 in all three traces, confirming the PLRU tree behaves identically and correctly regardless of which command code drives the misses.

For random_100_ops.din, the NORMAL transcript additionally confirms the S to M upgrade issuing BusOp: 3 (INVALIDATE) on a write hit to a shared line, and a snooped RWITM to a modified line reporting SnoopResult: 2 (HITM) and sending L2: 3 (INVALIDATELINE) to L1 as the line drops to I.