Fix a two-way cache model that lets a request hit a line already chosen for replacement.
Hardware context: Single-core cache with explicit geometry, write policy and replacement policy. Model bounded misses and replacement under permitted hit-under-miss behavior.
A cache with outstanding misses keeps working while memory fetches a line. Here a read hit a line that was already chosen for replacement. The refill then overwrote that line.
The function associative_trace() models a cache with two sets. Each set has two ways, which are the two places a line can live. Each way holds one 4-byte word. The cache is write-through.
A miss reserves a way and waits for a memory response event. Each set can have one miss waiting, so two misses can wait at once. A reserved way must not hit until its refill arrives.
The tests replay 25 event lists of up to 16 events. They compare the whole report with an independent model. Find the bug and fix it.
Signals in the Timeline
| Signal | Width | Role |
|---|---|---|
operation_count | 5 | input of each check |
Full specification
function automatic string associative_trace(input logic [1023:0] commands, input int count);
// merge_bytes(old_word, new_word, strobes) is given. Strobe bit i replaces byte i.
| Event bits | Holds |
|---|---|
| 31:0 | data: the write data, or the refill word of a response. |
| 37:32 | address: a byte address from 0x00 to 0x3c, always a multiple of 4. For a response it only selects the set. |
| 38 | write: 1 for a write request. |
| 42:39 | strobes: bit 39 enables byte 0, bit 42 enables byte 3. |
| 44 | response: 1 when this event is a memory response, not a CPU request. |
| 63:45, 43 | Always 0. |
Event t is commands[64t +: 64]. count is 1 to 16. Memory word i starts at 0x10203040 + i 0x01010101.
| Rule | Meaning |
|---|---|
| Set and tag | The set is (address / 4) % 2 and the tag is address / 8. |
| Hit | A valid way with the right tag that the set's waiting miss has not reserved. It is accepted at once. A write merges the enabled bytes into the way and into memory. |
| Miss | Accepted only when the set has no waiting miss. Otherwise it is rejected. The miss reserves way 0 if it is invalid, else way 1 if invalid, else the least recently used way. |
| Snapshot | An accepted miss saves the request and the memory word at that moment. Nothing else changes yet. |
| Response | An error when the set has no waiting miss or the data differs from the snapshot. A correct response fills the reserved way, applies a waiting write to the way and memory, and frees the set. |
| LRU | Each set remembers its least recently used way, way 0 at the start. A hit or a fill makes that way the most recently used. |
| Report piece | Format |
|---|---|
| Record | One per event: flags:word:busy:ways; with the pieces below. |
| flags | Three digits: accepted, hit and error. |
| word | 8 hex digits. The word of a hit or a correct fill. 0 for a newly accepted miss, a rejected request or an error. |
| busy | Two digits, set 1 then set 0. A 1 means that set has a waiting miss. |
| ways | Set 0 way 0, set 0 way 1, set 1 way 0, set 1 way 1. Each is the valid digit, the tag in 2 hex digits, =, the word in 8 hex digits and a comma. |
A way that was never filled shows 000=00000000. Hex digits are lower case.
The whole report is compared with the expected text. The result shows report_length and expected_length in characters. match is yes only when the two strings are equal.
Examples
Example 1
Two Misses Wait at Once- Input
read 0x00, read 0x04, response set 1 = 0x11213141, response set 0 = 0x10203040, read 0x00, read 0x04
- Output
report_length = 414, expected_length = 414, match = yes
The two reads use different sets, so both wait at once and busy shows 11. Set 1 answers first and fills its way 0. The last two reads hit, with flags 110.
Example 2
A Busy Set Rejects a Miss but Allows a Hit- Input
read 0x00, read 0x08, response set 0 = 0x10203040, read 0x08, response set 0 = 0x12223242, read 0x00, read 0x10, read 0x00, response set 0 = 0x14243444, read 0x08
- Output
report_length = 690, expected_length = 690, match = yes
The first read of 0x08 is rejected (000), because set 0 already waits. Later 0x10 reserves way 1, the least recently used. The read of 0x00 still hits way 0, which is not reserved.
Example 3
Wrong Refill Data- Input
write 0x00 = 0xaabbccdd with strobes 0101, response set 0 = 0x00000000, response set 0 = 0x10203040, read 0x00, response set 1 = 0x00000001
- Output
report_length = 345, expected_length = 345, match = yes
The first response has the wrong data, so it is an error (001) and the miss keeps waiting. The correct response installs the merged word 0x10bb30dd. The last response is for set 1, which waits for nothing, so it is an error.
Example 4
The Reserved Way Must Not Hit- Input
read 0x00, response set 0 = 0x10203040, read 0x08, response set 0 = 0x12223242, read 0x10, read 0x00, response set 0 = 0x14243444, read 0x00
- Output
report_length = 552, expected_length = 552, match = yes
Set 0 is full, and the read of 0x10 reserves way 0, which holds 0x00. The next read of 0x00 must not hit it, so it is rejected (000). After the refill, 0x00 misses and waits again.
Constraints and Contract
- A rejected request or a bad response changes nothing: not the ways, memory, waiting misses or LRU.
- A response completes the waiting request. It is never a new CPU request.
- Responses for the two sets may arrive in any order. Keep the function name and argument types.
Hints
Hint 1
Keep each set's waiting miss apart from the tag lookup: the way it reserved and the request it holds.
Hint 2
Trace example 4. Once the read of 0x10 reserves way 0, the read of 0x00 must not hit. Its set is busy, so it is rejected.
Hint 3
Look at the hit search loop. A way with busy[set_id] && victim[set_id] == way must not count as a hit.
What the grader checks: The 25 event lists include responses in both orders, wrong data and responses for idle sets. An independent model checks every record. This is a transaction model, not a clocked cache.
25 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