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
| Signal | Width | Role |
|---|---|---|
fixture | 4 | input of each check |
request_count | 4 | input of each check |
Full specification
function automatic logic [79:0] inspect_cache(input logic [16383:0] samples,
input int required_requests, required_flushes);
| Sample bits | Signal | Seen |
|---|---|---|
| 0 | cpu accepted (cpu_valid and cpu_ready) | before the edge |
| 1, 7:2, 39:8, 43:40 | cpu_write, cpu_address, cpu_wdata, cpu_strobe | before the edge |
| 44 | response_valid | after the edge |
| 75:45 and 119 | response_data bits 30:0 and bit 31 | after the edge |
| 76 | flush request | before the edge |
| 77 | flush_done | after the edge |
| 78, 79, 80 | mem_valid, mem_ready, mem_write | before the edge |
| 86:81, 118:87 | mem_address, mem_wdata | before the edge |
Sample t is samples[128*t +: 128], one per clock edge, for 128 edges. Other bits are 0.
| Checker rule | A violation when |
|---|---|
| Model | Keep 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. |
| Stall | An 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 write | An accepted memory write carries a word that differs from the expected memory at that address. |
| CPU request | A 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. |
| Response | response_valid = 1 when no response is due, or the data differs from the expected word. |
| Flush | A 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. |
| End | A 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 rule | Meaning |
|---|---|
| Shape | Two 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. |
| Request | Accepted 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. |
| Hit | The 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 miss | First 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. |
| Refill | Then 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. |
| Flush | A 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. |
| Reset | Synchronous and active high. It clears every line and state. |
| Test run | Details |
|---|---|
| Memory | Word i starts at 0x10203040 + i * 0x01010101. mem_rdata always shows the word at mem_address. |
| Plan 1 | 8 requests. Memory is ready on every fifth edge (edges 4, 9, 14 and so on). |
| Plan 2 | 7 requests. Memory is ready on edges not divisible by 3, but never on edges 8 to 15. |
| Plan 3 | 8 requests. Memory is ready on every edge. |
| Flush | A flush pulse arrives on edges 6 and 100. Each run lasts 128 edges after reset, counting from 0. |
| Faulty cache | What is wrong |
|---|---|
| 1 | A dirty miss skips the write-back. |
| 2 | A hit response has bit 0 flipped. |
| 3 | Writes ignore the strobes. |
| 4 | flush_done pulses as soon as a flush arrives. |
| 5 | The write-back goes to the requested address. |
| 6 | The write-back data changes only while memory stalls. Its runs always use the plan 1 memory pattern. |
| 7 | No 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