H9.8 Flush with Outstanding Misses

MediumFixIcarus · browser samples / server checksReview the topic

Fix a cache checker that never closes a flush, so it raises false alarms after the first flush.

Hardware context: Single-core cache with explicit geometry, write policy and replacement policy. Delay flush completion until the required outstanding cache memory effects retire.

A cache checker flagged a correct cache on every run. The alarms began right after the first flush finished. The checker never noticed that the flush had ended.

The function inspect_cache() checks a recorded run of a write-back cache. Each of 128 samples holds the CPU and memory signals of one clock edge. The checker keeps its own flat memory model. It returns 1 when any rule broke and 0 for a clean run.

The tests record runs of a correct cache and seven faulty ones. Each cache runs three request scripts with two flushes. The checker must stay silent on the correct cache and flag every faulty run. Find the bug and fix it.

Signals in the Timeline

SignalWidthRole
fixture4input of each check
request_count4input of each check
Full specification
The function (keep its name and types)
function automatic logic [79:0] inspect_cache(input logic [16383:0] samples,
                                              input int required_requests, required_flushes);
Sample bitsSignalSeen
0cpu accepted (cpu_valid and cpu_ready)before the edge
1, 7:2, 39:8, 43:40cpu_write, cpu_address, cpu_wdata, cpu_strobebefore the edge
44response_validafter the edge
75:45 and 119response_data bits 30:0 and bit 31after the edge
76flush requestbefore the edge
77flush_doneafter the edge
78, 79, 80mem_valid, mem_ready, mem_writebefore the edge
86:81, 118:87mem_address, mem_wdatabefore the edge

Sample t is samples[128*t +: 128], one per clock edge, for 128 edges. Other bits are 0.

Checker ruleA violation when
ModelKeep two flat 16-word arrays: the expected memory after CPU writes, and the real memory after accepted memory writes. Both start at the initial memory.
StallAn offer had mem_valid = 1 and mem_ready = 0, and the next sample drops mem_valid or changes the address, direction or write data.
Memory writeAn accepted memory write carries a word that differs from the expected memory at that address.
CPU requestA request is accepted while a response is still due or a flush is open. An accepted write updates the expected memory, byte by byte, first.
Responseresponse_valid = 1 when no response is due, or the data differs from the expected word.
FlushA flush request opens a flush. flush_done with no open flush, with a response still due, or with any memory word different. flush_done closes the flush.
EndA response is still due or a flush is open. Or the counts differ from required_requests and required_flushes, or memory differs.

One accepted request expects exactly one response. A hit responds on the accepting edge, so check the request before the response in the same sample.

Cache ruleMeaning
ShapeTwo direct-mapped sets of one 4-byte word. The set is address bit 2 and the tag is address bits 5:3. Write-back, with allocation on a write miss.
RequestAccepted on an edge where cpu_valid = 1 and cpu_ready = 1. cpu_ready is 0 while the cache is busy, a flush is waiting or flush is 1. One request is handled at a time.
HitThe response comes on the accepting edge: response_valid = 1 for one cycle after it. A write merges the enabled bytes, marks the line dirty and returns the merged word.
Dirty missFirst offer the old line: mem_valid = 1, mem_write = 1, the old address and its word. Hold all of them until an edge with mem_ready = 1.
RefillThen offer a read of the requested address. On the edge with mem_ready = 1, take mem_rdata, merge any write, install the line and respond.
FlushA one-cycle pulse, remembered until the current request ends. Then write back each dirty line, set 0 first, and invalidate both. flush_done pulses for one cycle at the end.
ResetSynchronous and active high. It clears every line and state.
Test runDetails
MemoryWord i starts at 0x10203040 + i * 0x01010101. mem_rdata always shows the word at mem_address.
Plan 18 requests. Memory is ready on every fifth edge (edges 4, 9, 14 and so on).
Plan 27 requests. Memory is ready on edges not divisible by 3, but never on edges 8 to 15.
Plan 38 requests. Memory is ready on every edge.
FlushA flush pulse arrives on edges 6 and 100. Each run lasts 128 edges after reset, counting from 0.
Faulty cacheWhat is wrong
1A dirty miss skips the write-back.
2A hit response has bit 0 flipped.
3Writes ignore the strobes.
4flush_done pulses as soon as a flush arrives.
5The write-back goes to the requested address.
6The write-back data changes only while memory stalls. Its runs always use the plan 1 memory pattern.
7No CPU response ever comes.

The result is violation in bit 0. It must be no for the correct cache and yes for each faulty one.

Examples

Example 1

Correct Cache, Plan 1
Input
Plan 1: read 0x00, write 0x00 = 0xaabbccdd strobes 0101, read 0x00, write 0x08 = 0x11223344, read 0x00, write 0x04 = 0x89abcdef strobes 1010, write 0x0c = 0x55667788 strobes 0011, read 0x04. Memory ready every fifth edge.
Output
violation = no

The flush on edge 6 writes 0x10bb30dd to 0x00 and ends on edge 11. The request on edge 12 is legal because the flush is over. The run is clean.

Example 2

Correct Cache, Plan 2
Input
Plan 2: write 0x04 = 0x80000001 strobes 1000, read 0x04, write 0x0c = 0x01020304 strobes 0001, read 0x04, write 0x00 = 0xffffffff strobes 0000, read 0x08, read 0x00. Memory never ready on edges 8 to 15.
Output
violation = no

The flush write-back of 0x0c waits from edge 10 to edge 16 with the offer unchanged. That is legal. Every response matches the memory model.

Example 3

Correct Cache, Plan 3
Input
Plan 3: write 0x00 = 0x91827364, write 0x08 = 0x10203040, write 0x10 = 0xa5a55a5a strobes 0101, read 0x18, read 0x00, read 0x08, read 0x10, read 0x10. Memory always ready.
Output
violation = no

The flush arrives during the miss for 0x10. The cache finishes that request before it starts the flush, so no response is due at flush_done.

Example 4

Faulty Cache 4: flush_done Too Early
Input
Plan 1: read 0x00, write 0x00 = 0xaabbccdd strobes 0101, read 0x00, write 0x08 = 0x11223344, read 0x00, write 0x04 = 0x89abcdef strobes 1010, write 0x0c = 0x55667788 strobes 0011, read 0x04. Memory ready every fifth edge.
Output
violation = yes

This cache pulses flush_done on edge 6, as soon as the flush arrives. Memory still lacks the dirty word 0x10bb30dd at 0x00, so the run is a violation.

Constraints and Contract

  • There is no reset in the middle of a run. Inputs are always known 0 and 1 values.
  • The cache may stall, but it must finish every request and both flushes within the 128 edges.
  • Use only the samples and the two counts. Keep the function name and argument types.

Hints

Hint 1

List the checker's state: the response due, the open flush and the last memory offer. Each one must be set and also cleared.

Hint 2

Trace plan 1 on the correct cache. The first flush ends on edge 11, and a request is accepted on edge 12. What does the checker think on edge 12?

Hint 3

Look at the flush_done branch. It counts the flush but leaves flushing at 1. Clear it there.

What the grader checks: Each case records 128 edges of a real cache: one correct design and seven with one planted fault each, on three scripts. The verdict must be 0 for the correct cache and 1 for each faulty run. Passing shows the checker catches these faults on these runs.

24 checks on Icarus · browser samples / server checks. Run the examples first, then check the full regression. Full checks use the server judge. Downloads contain public samples only. A passing result establishes the tested cases, not a proof for all possible inputs.

See all 8 steps and the final capstone

Report a problem with this page

Your code SystemVerilogSaved locally
Ln 1, Col 1Tab indents · Ctrl/⌘ + Enter runs samples
Not run yet

Correct Cache, Plan 1

Input
Plan 1: read 0x00, write 0x00 = 0xaabbccdd strobes 0101, read 0x00, write 0x08 = 0x11223344, read 0x00, write 0x04 = 0x89abcdef strobes 1010, write 0x0c = 0x55667788 strobes 0011, read 0x04. Memory ready every fifth edge.
Expected output
violation = no

The flush on edge 6 writes 0x10bb30dd to 0x00 and ends on edge 11. The request on edge 12 is legal because the flush is over. The run is clean.

Run samples executes all 4 public checks. Check all tests runs 24 checks on the server.

Icarus · browser samples / server checks