H9.5 Cache Data-Integrity Campaign

HardFixIcarus · browser samples / server checksReview the topic

Fix a cache that loses a flush during a miss and the checker that misses a changing stalled offer.

Hardware context: Single-core cache with explicit geometry, write policy and replacement policy. Qualify cache data integrity through conflicts, partial writes, stalled refills and flushes.

This problem holds a write-back cache and the checker that tests it. Each half has one bug. The cache forgets a flush that arrives while it is busy with a miss. The checker misses one way a stalled memory offer can break.

submitted_cache is a blocking write-back cache with two direct-mapped sets. Memory sits behind a valid/ready handshake, and a flush writes back every dirty line. inspect_cache() checks a recorded run of 128 edges against a flat memory model. It returns 1 when any rule broke.

The tests run your cache through three scripts and check each run with your checker. They also give your checker recorded runs of seven faulty caches. The clean runs must pass, and every faulty run must be flagged. Find both bugs and fix them.

Signals in the Timeline

SignalWidthRole
fixture4input of each check
request_count4input of each check
Full specification
The cache ports (keep them)
module submitted_cache(
  input  logic        clk, reset,
  input  logic        cpu_valid, cpu_write,
  input  logic [5:0]  cpu_address,
  input  logic [31:0] cpu_wdata,
  input  logic [3:0]  cpu_strobe,
  input  logic        flush,
  input  logic        mem_ready,
  input  logic [31:0] mem_rdata,
  output wire         cpu_ready,
  output logic        response_valid,
  output logic [31:0] response_data,
  output logic        mem_valid, mem_write,
  output logic [5:0]  mem_address,
  output logic [31:0] mem_wdata,
  output logic        flush_done);
  // your cache
endmodule
The checker (keep its name and types)
function automatic logic [79:0] inspect_cache(input logic [16383:0] samples,
                                              input int required_requests, required_flushes);
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.
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.

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.

Cases with fixture 0 run your cache and your checker together. The other cases run only your checker, on a faulty cache. violation must be no for fixture 0 and yes for every other fixture.

Examples

Example 1

Fixture 0, Plan 1: A Flush While Idle
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 finds the cache idle. It writes 0x10bb30dd back to 0x00 on edge 9. Later, the write to 0x0c evicts the dirty line of 0x04, and 0x8921cd41 reaches memory on edge 39. Both halves must report a clean run.

Example 2

Fixture 0, Plan 2: A Flush During a Long Stall
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 on edge 6 also finds the cache idle. Its write-back of 0x13233304 to 0x0c waits unchanged while memory stalls, and memory takes it on edge 16. flush_done follows on edge 17.

Example 3

Fixture 0, Plan 3: A Flush During a Miss
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 on edge 6 arrives while the cache is busy with the miss for 0x10. The cache must remember it. It finishes that request first, then writes 0x14a5345a back and pulses flush_done.

Example 4

Faulty Cache 6: Data Changes While Stalled
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 flips bit 0 of mem_wdata only while mem_ready = 0. The word is right when memory takes it, but the offer changed during the stall. The checker must report 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.
  • Keep the module name, the ports, the function name and its argument types.

Hints

Hint 1

Fix one half at a time. The fixture 0 cases test both halves together. The other cases test only the checker.

Hint 2

For the cache, trace plan 3. Its flush comes on edge 6, during the miss for 0x10. Is flush_done ever pulsed? For the checker, list everything a stalled offer must keep.

Hint 3

In the cache, flush_pending is set only when state is 0. A flush must be remembered in every state. In the checker, the stall check must also compare the write data.

What the grader checks: Your cache runs three scripts of 128 edges with stalls and two flushes, checked by your checker. Your checker also sees seven faulty caches on the same scripts. This covers these scripts and faults, not every schedule.

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

Fixture 0, Plan 1: A Flush While Idle

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 finds the cache idle. It writes 0x10bb30dd back to 0x00 on edge 9. Later, the write to 0x0c evicts the dirty line of 0x04, and 0x8921cd41 reaches memory on edge 39. Both halves must report a clean run.

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

Icarus · browser samples / server checks