Direct-Mapped Cache Final Contents for a Given Access Sequence 8 Lines | AI Research

Direct-Mapped Cache Final Contents for a Given Access Sequence (8 Lines)

Verified Sources

Nov 4, 2026

We analyze a Direct-mapped cache with 8 cache blocks/lines numbered $0$ – $7$ . For each requested memory block number $m$ , the cache line index is determined by mapping via:

Index: $i = m \bmod 8$
Tag: $\text{tag} = \lfloor m/8 \rfloor$ Because it is direct-mapped, each access to memory block $m$ overwrites whatever was previously in line $i$ . This is the core Replacement behavior: conflicts always evict the existing cache line contents.

Below, we track which memory block ends up residing in each cache line after the full sequence: $3, 5, 2, 8, 0, 63, 9, 16, 20, 17, 25, 18, 30, 24, 2, 63, 5, 82, 17, 24.$

Key mapping terms: Cache line index; Conflict; Valid bit.3

Wikipedia: Cache (computing) — Mapping and replacement concepts - Background on cache lines, hits/misses, and mapping. ↩
Wikipedia: Direct-mapped cache - Direct-mapped mapping and how an address selects a cache line. ↩
Wikipedia: Cache replacement policies / eviction on conflict (conceptual) - Replacement behavior including eviction when lines conflict. ↩

Direct-Mapped Cache Mapping (Conceptual Walkthrough)

Compute final cache-line contents by modulo mapping

1
Step 1
Assume all 8 lines start invalid; after the first access to a line, it becomes valid with the accessed memory block.
2
Step 2
Direct-mapped rule: block $m$ resides in line $i=m\bmod 8$ and overwrites that line.
3
Step 3
Record that line $i$ now contains memory block $m$ (tag matches automatically after overwrite for final state).
4
Step 4
At the end, each cache line contains the last memory block in the sequence that mapped to that line.

Tracking the last write to each cache line

For each access $m$ , compute $i=m\\bmod 8$ :

Access #	Memory block $m$	Line $i=m\\bmod 8$	Line overwritten by
1	3	3	line 3 ← 3
2	5	5	line 5 ← 5
3	2	2	line 2 ← 2
4	8	0	line 0 ← 8
5	0	0	line 0 ← 0
6	63	7	line 7 ← 63
7	9	1	line 1 ← 9
8	16	0	line 0 ← 16
9	20	4	line 4 ← 20
10	17	1	line 1 ← 17
11	25	1	line 1 ← 25
12	18	2	line 2 ← 18
13	30	6	line 6 ← 30
14	24	0	line 0 ← 24
15	2	2	line 2 ← 2
16	63	7	line 7 ← 63 (no change in line 7’s resident value)
17	5	5	line 5 ← 5 (reaffirm)
18	82	2	line 2 ← 82
19	17	1	line 1 ← 17
20	24	0	line 0 ← 24 (reaffirm as last)

Thus, the final resident memory block number in each cache line is the last one written to that line.

Final cache contents by cache line (direct-mapped, 8 lines)

Each line i ends holding the last accessed memory block m such that m mod 8 = i.

How to do it quickly

You only need the last occurrence in the sequence for each residue class $m\bmod 8$ . Everything earlier to the same line is guaranteed evicted in a direct-mapped cache.

Avoid a common mistake

Do not treat the cache like it has 8-way capacity for 8 distinct blocks. Direct-mapped means one block per line; later conflicts overwrite earlier contents.

Key concepts used in the computation

Finalization process (end state) across the access sequence

Line 0 first filled

After Access 4 (8)

Line 0 becomes 8, but it can still be overwritten later."

Line 0 updated to 24

After Access 14 (24)

Line 0 is overwritten again at the end; keep tracking last writes."

Line 2 updated to 82

After Access 18 (82)

Since $82\bmod 8=2$ , this becomes the last line-2 update."

End state locked

Final Access (24)

Line 0 is reaffirmed by the final access; other lines retain their last mapped values."

Knowledge Check

Question 1 of 4

Q1Single choice

In a direct-mapped cache with 8 lines, a memory block m maps to which cache line index?

m mod 8

m mod 7

8 mod m

m / 8

Explore Related Topics

Page Faults for a Given Reference String Using LRU and FIFO (3 vs 4 Frames)

ROM Addressing for 4096 Bytes: Chip Count, Address Lines, and Common Addresses

Cache Memory Mapping Techniques: Merits and Demerits

Browse all research articles