Interview Question · Code Writing
Splitting an Address into Tag, Index and Offset
The Question
The interviewer asks
A 4 KB direct-mapped cache has 16-byte lines and 32-bit addresses. Split address 0x1234_5678 into tag, index and offset.
You have two and a half minutes. Speak or type, then press Get Feedback under your answer. No credits needed.
Speech-to-text runs in your browser. Chrome and Edge may send audio to their own speech service.
You can edit your answer before you send it. Feedback uses AI and checks your answer only against our written answer. No credits are used and your answer is not saved.
Reveal the Model Answer
A 16-byte line needs 4 offset bits. 4 KB divided by 16 bytes is 256 lines, so 8 index bits. The other 20 bits are the tag. For 0x1234_5678: offset 8, index 0x67, tag 0x12345.
- Offset
A 16-byte line needs 4 bits to pick a byte: the low hex digit, 8.
- Index
4 KB / 16 B = 256 lines, so 8 bits pick the line: the next two hex digits, 0x67.
- Tag
The other 20 bits, 0x12345, are stored with the line and compared on every lookup.
Read the diagram as text
- 0x1234_5678: the 32-bit address
- Tag [31:12]: 20 bits: 0x12345
- Index [11:4]: 8 bits: 0x67
- Offset [3:0]: 4 bits: 0x8
- Line array: 256 lines of 16 bytes
- Tag compare: hit if equal and valid
- Byte select: byte 8 of the line
- 0x1234_5678 → Tag [31:12]
- 0x1234_5678 → Index [11:4]
- 0x1234_5678 → Offset [3:0]
- Index [11:4] → Line array: selects line 0x67
- Tag [31:12] → Tag compare: address tag
- Line array → Tag compare: stored tag, valid
- Line array → Byte select: line data
- Offset [3:0] → Byte select: offset
Offset and index come straight from the line size and line count. The tag is whatever is left.
The split computed from the cache parameters with $clog2.
offset 4 bits, index 8 bits, tag 20 bits address 12345678: tag 00012345, index 00000067, offset 00000008Self-Check
Tick each key point you covered in your answer.
What Interviewers Listen For (Junior)
A good junior answer works out the bit counts from the line size and line count first. Only then does it read the fields off the hex digits.
What Interviewers Listen For (Mid-Level)
A good mid-level answer asks about associativity first. It shows how the index shrinks and the tag grows as the number of ways goes up.
Cross-Questions
Where the interviewer goes next. Open a node to practise that follow-up.
What IfBreak ItCompareScale It
- Splitting an Address into Tag, Index and Offset
-
What IfThe Same Cache, Two WaysL1 JuniorL2 Mid-Level
What changes if the same 4 KB cache is 2-way set associative?
2:30You have two and a half minutes. Speak or type, then press Get Feedback under your answer. No credits needed.
Speech-to-text runs in your browser. Chrome and Edge may send audio to their own speech service.
You can edit your answer before you send it. Feedback uses AI and checks your answer only against our written answer. No credits are used and your answer is not saved.
Reveal the Model Answer
There are now 128 sets of two lines, so the index drops to 7 bits and the tag grows to 21. A lookup compares two tags in parallel and picks the matching way. On a miss, a replacement rule such as LRU (least recently used) chooses the victim. More ways cut conflict misses, but add comparators and a slower hit path.
Self-Check
Tick each key point you covered in your answer.
Misconception
"Associativity changes the cache size."
The total stays 4 KB. Only the grouping changes: fewer sets, more lines in each.
Source Measured: the twin on design.arch.cache-address-split (the 2-way fixed model), Icarus Verilog 12
-
CompareCompulsory, Capacity and Conflict MissesL1 JuniorL2 Mid-Level
Compare the three kinds of cache miss. Which one does more associativity fix?
2:30You have two and a half minutes. Speak or type, then press Get Feedback under your answer. No credits needed.
Speech-to-text runs in your browser. Chrome and Edge may send audio to their own speech service.
You can edit your answer before you send it. Feedback uses AI and checks your answer only against our written answer. No credits are used and your answer is not saved.
Reveal the Model Answer
A compulsory miss is the first touch of a line, which no cache avoids. A capacity miss happens when the working set is bigger than the cache. A conflict miss happens when lines that would fit compete for one set. More ways fix conflict misses; only a bigger cache fixes capacity misses.
Self-Check
Tick each key point you covered in your answer.
Half-Truth
"More ways reduce every kind of miss."
They only spread lines over more slots in a set. The first touch still misses, and a working set bigger than the cache still does not fit.
Source Hennessy and Patterson, Computer Architecture: A Quantitative Approach (5th ed.), App. B, Review of Memory Hierarchy
-
Break ItThe Cache That Hit Before Anything Was LoadedL1 Junior
Break it: this cache has no valid bits, and its tag RAM clears to zero at reset. What happens on the first access?
systemverilog hit = (tag_q[index] == addr_tag); // no valid bit2:30You have two and a half minutes. Speak or type, then press Get Feedback under your answer. No credits needed.
Speech-to-text runs in your browser. Chrome and Edge may send audio to their own speech service.
You can edit your answer before you send it. Feedback uses AI and checks your answer only against our written answer. No credits are used and your answer is not saved.
Reveal the Model Answer
Any address whose tag is 0 hits on an empty cache and returns garbage data. Each line needs a valid bit, cleared at reset and set when the line is filled. Clearing only the valid bits is cheaper than clearing a whole tag RAM.
Self-Check
Tick each key point you covered in your answer.
Missed Corner
"Reset clears the tags, so an empty cache cannot hit."
A cleared tag is 0, which is a real tag. The twin hits on address 0x40 in an empty cache.
Run It
The first access after reset, with and without a valid bit.
RUNIcarus Verilog · in your browserExpected:first access to 00000040: HITFAIL: with no valid bit, a reset tag of 0 matched address 00000040 in an empty cacheSee the Fix
module tb; // Direct-mapped, 256 lines of 16 bytes. After reset the tag RAM holds zeros. logic [19:0] tag_q [256]; bit valid [256]; initial begin foreach (tag_q[i]) begin tag_q[i] = 0; valid[i] = 0; end // First access after reset: address 0x0000_0040 has tag 0, index 4. if (valid[4] && tag_q[4] == 20'h0) $display("first access to 00000040: HIT"); else $display("first access to 00000040: miss"); $display("PASS: the valid bit makes an empty cache miss"); end endmodulePrints:
first access to 00000040: missPASS: the valid bit makes an empty cache miss -
Scale ItVerifying a CacheL2 Mid-LevelL3 Senior
Scale it: how would you verify a cache like this?
2:30You have two and a half minutes. Speak or type, then press Get Feedback under your answer. No credits needed.
Speech-to-text runs in your browser. Chrome and Edge may send audio to their own speech service.
You can edit your answer before you send it. Feedback uses AI and checks your answer only against our written answer. No credits are used and your answer is not saved.
Reveal the Model Answer
Treat the cache as invisible: a reference model is just a flat memory, and every read must match it. At the end, flush the cache and compare the final memory images. Aim stimulus at aliasing addresses, evictions of dirty lines, and reads right after writes. Add assertions on internal rules, because a final-image mismatch is hard to trace back.
Self-Check
Tick each key point you covered in your answer.
Missed Corner
"Random addresses over the whole space will find the bugs."
Random 32-bit addresses rarely collide in one set, so evictions and conflicts are rare. Aim addresses at a few sets.
Source Mehta, ASIC/SoC Functional Design Verification (2018) ch. 17.3 Determine subsystem stimulus and response methodology
What People Get Wrong
Common wrong answers and why they fail. Run It shows the wrong belief failing on a real simulator.
Misconception
"A 4 KB cache holds any 4 KB of data."
In a direct-mapped cache each address has exactly one line. Two addresses 4 KB apart share it and evict each other, as the twin shows.
Run It
Alternating reads of 0x1000 and 0x2000, 50 times each.
direct-mapped: 0 hits, 100 misses in 100 accesses to two addresses 4 KB apart FAIL: a 4 KB cache does not hold any 4 KB; two addresses 4 KB apart share one line and evict each otherSee the Fix
module tb;
// A 4 KB cache with 16-byte lines: 2-way set associative, 128 sets, LRU.
localparam int WAYS = 2, SETS = 256 / WAYS;
logic [31:0] tag_q [SETS][WAYS];
bit valid [SETS][WAYS];
bit lru [SETS]; // the way to replace next (2-way only)
int hits = 0, misses = 0;
task automatic access(input logic [31:0] addr);
int set, victim; logic [31:0] tag; bit hit;
set = (addr >> 4) % SETS;
tag = addr >> 4; // keep the whole line number as the tag
hit = 0;
for (int w = 0; w < WAYS; w++)
if (valid[set][w] && tag_q[set][w] == tag) begin hit = 1; lru[set] = (w == 0); end
if (hit) hits++;
else begin
misses++;
victim = (WAYS == 1) ? 0 : lru[set];
tag_q[set][victim] = tag; valid[set][victim] = 1;
lru[set] = !victim;
end
endtask
initial begin
for (int i = 0; i < 50; i++) begin access(32'h0000_1000); access(32'h0000_2000); end
$display("2-way: %0d hits, %0d misses in 100 accesses to two addresses 4 KB apart", hits, misses);
if (hits == 98) $display("PASS: two ways in the set keep both lines");
end
endmodule
Prints: 2-way: 98 hits, 2 misses in 100 accesses to two addresses 4 KB apart PASS: two ways in the set keep both lines
Missed Corner
Computes the index from the byte address without dropping the offset bits.
The index starts above the offset. Using the low bits puts the bytes of one line into different sets.
Source Measured: the run on design.arch.cache-address-split, Icarus Verilog 12