H9.2 Direct-Mapped Cache Oracle

MediumFixIcarus · browser samples / server checksReview the topic

Fix a direct-mapped cache model that reports a hit for any valid line, without comparing the tag.

Hardware context: Single-core cache with explicit geometry, write policy and replacement policy. Predict hits and memory traffic for a direct-mapped write-through cache.

A cache model said that a read of address 0x08 hit, but the cache held address 0x00. Both addresses use set 0. The model returned the word of the wrong address.

The function cache_trace() models a tiny cache, one request at a time. It has two sets of one 4-byte word, in front of 64 bytes of memory. Here the cache is write-through: every write also goes to memory at once.

It returns a text report of every request, every memory transfer and the final memory. The tests replay 34 command lists with write_back = 0. They compare the whole report with an independent model. Find the bug and fix it.

Signals in the Timeline

SignalWidthRole
operation_count5input of each check
write_back1input of each check
Full specification
The functions (keep these names and types)
function automatic string cache_trace(input logic [1023:0] operations,
                                    input int count, input bit write_back);
function automatic logic [31:0] merge_bytes(input logic [31:0] old_word, new_word,
                                            input logic [3:0] strobes);  // given
Command bitsHolds
31:0data: the write data.
37:32address: a byte address from 0x00 to 0x3c, always a multiple of 4.
38write: 1 for a write, 0 for a read.
42:39strobes: one bit per byte of the word. Bit 39 enables byte 0 (bits 7:0), bit 42 enables byte 3 (bits 31:24).
43flush: 1 for a flush command. The other fields are then 0.
63:44Always 0.

Command t is operations[64*t +: 64], so the first command sits in the low bits. count is 1 to 16.

ItemValue
CacheTwo sets. Each set holds one line of one 4-byte word, with a valid bit, a dirty bit and a tag.
Set(address / 4) % 2. Direct-mapped means each address can live only in this one set.
Tagaddress / 8. It records which address the line holds.
Memory16 words (64 bytes). Word i starts at 0x10203040 + i * 0x01010101.
RuleWrite-through (write_back = 0)
HitThe set is valid and its tag equals address / 8.
MissRead the requested word from memory (event R). Install it with the new tag, valid and clean.
WriteAllocate on a miss first. Merge the enabled bytes with merge_bytes. Then write the whole merged word to memory (event W), even when all strobes are 0.
FlushVisit set 0, then set 1. Write back any dirty line, then invalidate both. In write-through mode no line is dirty, so the record is FLUSH:;
Report pieceFormat
Request recordhit:word:dirty:events; with hit and dirty as 0 or 1 after the request. word is the line's word in 8 hex digits.
Read eventR, the address in 2 hex digits, and a comma. Example: R08,
Write eventW, the address in 2 hex digits, =, the word in 8 hex digits, and a comma. Example: W00=10bb30dd,
Flush recordFLUSH:events; with one write event per dirty line written back.
EndMEM: and then all 16 memory words in order, each as 8 hex digits and a comma.

Hex digits are lower case. Events appear in the order they reach memory. A write returns the merged word.

write_back = 1 selects a write-back policy instead. The tests here always use 0.

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 Addresses in One Set
Input
read 0x00, write 0x00 = 0xaabbccdd with strobes 0101, read 0x00, read 0x08, read 0x00, flush
Output
report_length = 250, expected_length = 250, match = yes

The write changes bytes 0 and 2 only, giving 0x10bb30dd, and writes it to memory. The read of 0x08 uses set 0 with another tag, so it misses (0:12223242:0:R08,;). The last read of 0x00 misses again.

Example 2

A Write with No Strobes
Input
write 0x04 = 0xffffffff with strobes 0000, read 0x04, write 0x0c = 0x80000100 with strobes 1000, flush, read 0x04
Output
report_length = 249, expected_length = 249, match = yes

The first write still allocates the line and writes the unchanged word (0:11213141:0:R04,W04=11213141,;). The write to 0x0c changes only byte 3, giving 0x80233343. The flush has nothing to write.

Example 3

Three Addresses Fight for Set 0
Input
write 0x00 = 0x11111111, write 0x08 = 0x22222222, read 0x10, flush, read 0x00, read 0x08 (all strobes 1111)
Output
report_length = 271, expected_length = 271, match = yes

0x00, 0x08 and 0x10 all use set 0, so each request replaces the line. Each write reached memory at once, so nothing is lost. The final memory holds 0x11111111 at word 0 and 0x22222222 at word 2.

Constraints and Contract

  • Each command finishes before the next one starts. There is no timing, no stall and no second CPU.
  • Inputs are always known 0 and 1 values.
  • Use merge_bytes for every write. Keep the function names and argument types.

Hints

Hint 1

A hit needs two things: a valid line, and the right address in it. Which state tells you the address?

Hint 2

Trace example 1 by hand. After the read of 0x08, set 0 holds 0x08. The next read of 0x00 must miss again.

Hint 3

Look at how hit is computed. It must also check that tag[index] equals key.

What the grader checks: Four directed and 30 random command lists run in write-through mode. The whole report, with the final memory, must match an independent model. This checks the model on these lists, not a clocked cache.

34 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

Two Addresses in One Set

Input
read 0x00, write 0x00 = 0xaabbccdd with strobes 0101, read 0x00, read 0x08, read 0x00, flush
Expected output
report_length = 250, expected_length = 250, match = yes

The write changes bytes 0 and 2 only, giving 0x10bb30dd, and writes it to memory. The read of 0x08 uses set 0 with another tag, so it misses (0:12223242:0:R08,;). The last read of 0x00 misses again.

Run samples executes all 3 public checks. Check all tests runs 34 checks on the server.

Icarus · browser samples / server checks