Laboratory Module: Cache Access Methods

Direct-Mapped • Fully Associative • Set-Associative

Course: Computer Architecture / Organization

1) Introductory Statement
Modern processors rely on caches to hide main-memory latency. This lab explores how memory addresses map to cache
lines under three access methods—Direct-Mapped (DM), Fully Associative (FA), and Set-Associative (SA)—and how
mapping, replacement, and write policies affect hits, misses, and Average Memory Access Time (AMAT). You will
compute bit fields (tag/index/offset), simulate hit/miss timelines on short traces with LRU, analyze miss types
(compulsory/capacity/conflict), and verify the VIPT (Virtually Indexed, Physically Tagged) page-offset rule.

2) Learning Objectives
 Partition an address into Tag / (Set) Index / Block Offset across DM/FA/SA designs.
 Map addresses to lines/sets; determine hit/miss sequences and evictions under LRU/FIFO/Random.
 Distinguish compulsory, capacity, and conflict misses; relate to associativity.
 Compute storage overhead (tag store + metadata) for various designs.
 Evaluate performance via AMAT and explain trade-offs between hit time and miss rate.
 Check VIPT page-offset rule to avoid synonyms in L1 caches.

3) Prerequisites
 Binary/hex conversion, powers of two, and bitwise shifting/masking.
 Understanding of byte-addressed vs word-addressed memory.
 Basic knowledge of LRU/FIFO/Random replacement and write-through vs write-back.

4) Materials & Tools

 Calculator (or Python/Excel/Google Sheets).
 This handout with data tables.
 Optional: simple trace simulator (spreadsheet or short script)
5) Background & Theory

5.1 Core Definitions

Miss taxonomy: Compulsory (first reference), Capacity (working set > cache), Conflict (mapping collisions within set).
Callout Box: Tag, Index, and Offset — Quick Guide
How a byte address is split in a cache lookup

[ Tag | Index / Set | Offset ]

(high bits) (middle) (low bits)

Intuition (a quick analogy)

 Offset = apartment room number inside a specific flat (the block).
 Index/Set = which building (set) to go to on the street.
 Tag = the neighborhood label so you know whether the building you’re at actually
contains the address you want.

What they mean:

• Offset: Selects the byte position inside a cache block (line).

• Index / Set: Selects which set (DM: the exact line) to probe.
• Tag: Identifies which memory block is currently stored in that set/line.

Field Selects # bits Formula (byte- Hardware use

addressed)
Offset Byte inside log2(B) offset = addr & Pick the exact
block (B-1) byte/word from
the fetched line
Index / Set Set (DM: line) log2(S) (DM: set = (addr >> Choose which
log2(L); FA: 0) log2(B)) & (S-1) set to read;
compare only
here
Tag Which block is AddrWidth - tag = addr >> Compare
here (Index/Set + (log2(B) + against stored
Offset) log2(S)) tag(s) for
hit/miss

Numeric mini-example (Direct-Mapped)

• Assume 32-bit addresses, C=8 KiB, B=32 B → L=256 lines.
• Bits: Offset=log2(32)=5; Index=log2(256)=8; Tag=32-(5+8)=19.
• Address format: [ Tag19 | Index8 | Offset5 ].
• Let X = 0x00401034.
• offset = X & 0x1F = 0x14 (20)
• index = (X >> 5) & 0xFF = 0x81 (129)
• tag = X >> 13 = 0x200 (512)
• On access, line=index=129 is probed; tag must match 0x200 (and valid=1) for a hit.

Common pitfalls
• Always compute Offset in BYTES (convert word-addressed problems to bytes first).
• Sizes should be powers of two for simple shift/mask formulas.
• DM collisions: addresses separated by 2^(Index+Offset) bytes map to the same line
(ping-pong conflicts).
• VIPT L1 rule: SetBits + Offset ≤ PageOffset (e.g., ≤12 for 4 KiB pages).

5.2 Bit-Field Diagrams

32-bit configurations used throughout the comprehensive examples:

Toy 16-bit examples (for board work / quick checks):

5.3 Direct-Mapped (DM)

Mapping & fields:

 line ¿block mod Lwhere block ¿ ⌊ addr /B ⌋ .

 Address = [ Tag | Index | Offset ]

o Offset ¿ log ⁡2 B

o Index ¿ log ⁡2 L

o Tag ¿ AddrWidth−(Index+ Offset)

Access path (hardware):

1. Decode Index → read one line’s tag & data.

2. One tag comparator.

3. If tag matches+valid → hit; else miss and the same line is the victim (no replacement policy needed).

Where it bites
  Conflict misses dominate: any two hot blocks that map to the same line ping-pong.

 At fixed C , increasing B reduces the number of lines L→ Index bits shrink → more conflicts.

Tiny mini-example (numbers)

Given:

Address width 32 bits

Cache capacity, C 8 KiB = 8 × 1024 = 8192 B
Block (line) size, B 32 B
Mapping Direct-Mapped (DM)

Derive Core Parameters:

a) Number of lines: L = C / B = 8192 / 32 = 256 lines.

b) Bit fields for Direct-Mapped:

Field Formula Value

Offset bits log2(B) log2(32) = 5
Index bits log2(L) log2(256) = 8
Tag bits AddrWidth − (Index + Offset) 32 − (8 + 5) = 19
Address format — [ Tag19 | Index8 | Offset5 ]

Same-Line Stride (Why 0x2000?)

In a direct-mapped cache, two addresses that differ by 2^(Index+Offset) bytes have the same index (and same offset).
Only the tag changes. Therefore they map to the same cache line and will collide (ping-pong) on alternating accesses.

Index bits Offset bits Same-line stride (bytes)

8 5 2^(8+5) = 2^13 = 8192 =
0x2000

Concrete Proof with an Actual Address:

Choose base address X and add the same-line stride:

Base address, X 0x00401034

Stride 0x2000 (8192)
Second address, X' = X + 0x2000 0x00403034
Masks & shifts (DM, L=256, B=32):

Offset mask = B − 1 = 0x1F; Index mask = L − 1 = 0xFF

Offset bits = 5 → shift >> 5; Tag shift = 5 + 8 = 13 → shift >> 13

Compute fields:

Address Offset (5b) Index (8b) Tag (19b) Comment

X = 0x00401034 X & 0x1F = 0x14 (X >> 5) & 0xFF = X >> 13 = 0x200 —
(20) 0x81 (129) (512)
X' = 0x00403034 X' & 0x1F = 0x14 (X' >> 5) & 0xFF X' >> 13 = 0x201 Tag increased by
(20) = 0x81 (129) (513) 1
Result: Same index (129) → same DM line; different tags → alternate accesses will evict each other (conflict ping-pong).
5) Generalizations (Useful to Remember)

Same-line stride (DM) 2^(IndexBits + OffsetBits) bytes

5.4 Fully Associative (FA)

Mapping & fields

 Any block → any line.

 Address = [ Tag | Offset ] (no index).

o Tag ¿ AddrWidth−Offset .

Access path (hardware):

 Parallel compare of the incoming Tag against all valid lines’ tags (CAM-like).

 On miss with no free line, choose a victim via replacement policy.

Why it’s great

 Minimizes conflict misses (placement is flexible).

 Perfect for very small structures where full parallel compare is affordable: TLBs, victim caches, tiny L0 buffers.

Where it hurts

 Parallel tag compares across many lines are area/energy expensive; hit time can grow with size.

 True LRU across many lines is metadata-heavy; large FA data caches are rare.

Replacement policies (typical for FA)

 LRU for very small FA (e.g., 4–32 entries).

 Random/NRU for simplicity at moderate sizes.

 Modern predictors (D(R)RIP, bimodal insertion) appear in LLCs/SA caches more often than large FA.

Write behavior

 Same as others, but fewer conflict-driven write-backs than DM since hot blocks can co-reside.

Tiny mini-example (numbers)

Given:

Address width 32 bits

Cache capacity, C 8 KiB = 8 × 1024 = 8192 bytes
Block (line) size, B 32 bytes
Mapping Fully Associative (FA) — no set/index; any
block can occupy any line

Derive Core Cache Parameters

a) Number of lines: L = C / B = 8192 / 32 = 256 lines.

b) Bit fields for FA (no index/set):

Field Formula Value

Offset bits log2(B) log2(32) = 5
Index/Set bits FA → 0 0
 Tag bits AddrWidth − (Index/Set + 32 − (0 + 5) = 27
Offset)
Address format — [ Tag27 | Offset5 ]

Intuition: in FA, the tag is simply the block number (`addr >> 5`), because there’s no
set/index.

“300 Unique Blocks” Stream — Exact Miss Counts

We access 300 distinct blocks (no repeats), starting from a cold cache.

• At a cold start, the first reference to each block is a miss.

• The cache has 256 lines. After the first 256 distinct blocks, the cache is full.

• The remaining 44 distinct blocks (257…300) are also misses, each evicting an older line (e.g., by LRU).

Total references 300

Total misses 300
Compulsory misses min(300, 256) = 256
Capacity misses 300 − 256 = 44 (Conflict misses = 0 for FA)

Concrete Numeric Walk-Through (first/last steps)

Define A_i = Base + (i−1)×B with B=32. Example Base = 0x00400000 (aligned).

Then tag_i = A_i >> 5 = (Base >> 5) + (i−1); offset = 0 for the first byte.

Ref # Address A_i Tag (FA) = A_i >> 5 Classification

1 Base + 0×32 Base>>5 + 0 Miss (compulsory)
2 Base + 1×32 Base>>5 + 1 Miss (compulsory)
3 Base + 2×32 Base>>5 + 2 Miss (compulsory)
4 Base + 3×32 Base>>5 + 3 Miss (compulsory)
5 Base + 4×32 Base>>5 + 4 Miss (compulsory)
… … … …
256 Base + 255×32 Base>>5 + 255 Miss (compulsory;
cache becomes full)
257 Base + 256×32 Base>>5 + 256 Miss (capacity; evict
LRU #1)
… … … …
300 Base + 299×32 Base>>5 + 299 Miss (capacity; evict
current LRU)

Typical use

 TLB (FA or high-assoc), victim cache (4–16 entries, FA), sometimes tiny instruction buffers.

5.5 Set-Associative (SA)

Mapping & fields

 Middle ground: S sets × A ways per set.

 Address = [ Tag | SetIndex | Offset ]

 o SetIndex ¿ log ⁡2 S, A = associativity (ways).

 Mapping: set ¿(block) mod S ; placement within the set is flexible (choose one of A ways).

Access path (hardware):

 Read all A tags (and often all A data words/lines in parallel), compare tags, select hit way via mux.

 If miss and set full, pick victim via replacement policy within the set.

Why it’s the default

 Dramatically fewer conflict misses than DM, but with far fewer comparators than FA.

 L1D is often 2–8-way; L2/L3 typically 8–16-way.

Latency/energy tricks

 Parallel vs serial lookup:

o Parallel (tags+data together) = lower hit latency, higher power.

o Serial (tags first, then data) = saves power, adds a bubble if not carefully pipelined.

 Way prediction: predict likely way → speculatively read one way (saves energy/latency on correct predictions).

 Banking/sub-banking: reduce conflicts and support multiple accesses (I/D split, multi-port illusion).

Replacement policies (within a set)

 True LRU up to ~4-way; beyond that, Tree-PLRU ( A−1) bits/set or NRU/Random are common.

 Advanced: DIP/DRRIP family (useful in LLCs) to bias insertion for thrash-resistance.

VIPT constraint for L1

 With 4 KiB pages (page offset 12), require SetIndexBits + OffsetBits ≤ 12 so you can index in parallel with the
TLB.

o Common L1D: 32 KiB, 8-way, 64 B ⇒ Offset=6, SetIndex=6 → 6+6=12 ✓.

Skew & hashing

 To spread hot indices:

o Skewed associative: different hash per way (e.g., XOR with bits of tag).

o Simple index XOR: mix upper and lower bits to avoid power-of-two conflict patterns.

Writes

 Write-back + write-allocate is common in data caches; metadata per line: Valid/Dirty (+ ECC/parity).

 SA reduces conflict-induced dirty evictions versus DM.

Tiny mini-example (numbers)

Given

Address width 32 bits

Cache capacity, C 16 KiB = 16,384 bytes
Block (line) size, B 64 bytes
Associativity, A 2 (2-way Set-Associative)
Derive Core Cache Parameters

a) Number of lines: L = C / B = 16,384 / 64 = 256 lines.

b) Number of sets: S = L / A = 256 / 2 = 128 sets.

c) Bit fields for FA (no index/set):

Field Formula Value

Offset bits log2(B) log2(64) = 6
Index/Set bits log2(S) log2(128) = 7
Tag bits AddrWidth − (Index/Set + 32 − (7 + 6) = 19
Offset)
Address format — [ Tag19 | SetIndex7 | Offset6 ]

Same-Set Stride — Why 2^(Offset+SetIndex) = 2^(6+7) = 0x2000

SetIndex occupies bits [6..12] (LSB=bit0) and Offset occupies bits [0..5]. Adding 2^(6+7)=2^13=0x2000 flips bit 13 while
keeping bits 0..12 unchanged, so Offset and SetIndex remain the same; only Tag changes.

Offset bits SetIndex bits Same-set stride (bytes)

6 7 2^(6+7) = 2^13 = 8192 =
0x2000

Concrete Verification with Actual Addresses

Choose a 64-byte aligned base: X = 0x00401000.

Compute (byte-addressed):

offset = addr & (B-1) with B=64 → B-1 = 0x3F

set = (addr >> 6) & (S-1) with S=128 → S-1 = 0x7F

tag = addr >> (6 + 7) = addr >> 13

Address Offset (6b) SetIndex (7b) Tag (19b) Observation

X = 0x00401000 0 (0x00401000 >> 0x00401000 >> base
6) & 0x7F = 64 13 = 512
X + 0x2000 = 0 (0x00403000 >> 0x00403000 >> same set, tag+1
0x00403000 6) & 0x7F = 64 13 = 513
X + 0x4000 = 0 (0x00405000 >> 0x00405000 >> same set, tag+2
0x00405000 6) & 0x7F = 64 13 = 514
Result: All three addresses map to Set 64; tags {512, 513, 514}. Three contenders for a
2-way set.

2-Way Set Behavior with LRU (Thrash Demo)

Sequence: < X, X+0x2000, X, X+0x4000, X+0x2000, X > (cache cold; set=64).

Step Access Tag Hit/Miss Set 64 Action Set 64

(Before) (After,
MRU→LRU)
1 X 512 Miss [ –, – ] Fill empty [512, –]
way
2 X+0x2000 513 Miss [512, –] Fill other [513, 512]
 empty way
3 X 512 Hit [513, 512] Touch 512 [512, 513]
→ MRU
4 X+0x4000 514 Miss [512, 513] Evict [514, 512]
LRU=513,
insert 514
5 X+0x2000 513 Miss [514, 512] Evict [513, 514]
LRU=512,
insert 513
6 X 512 Miss [513, 514] Evict [512, 513]
LRU=514,
insert 512
Observation: With three contenders {512, 513, 514} in a 2-way set, the third arrival
always forces an eviction; the set thrashes whenever contenders per set > A.

5.6 Replacement & Writes

Replacement: LRU (accurate but costlier for high A), Tree-PLRU (~LRU, (A−1) bits/set), NRU, Random. Writes:
Write-through (+write buffer) vs Write-back (+Dirty). Write-allocate vs No-write-allocate.
6) Worked Examples (Comprehensive)
Shared base parameters: C=16 KiB, B=64 B ⇒ L=256 lines. DM: A=1 ⇒ S=256; Offset=6, Index=8, Tag=18. 2 -Way SA: A=2
⇒ S=128; Offset=6, SetIndex=7, Tag=19. FA: A=256 ⇒ S=1; Offset=6, Tag=26.

Conflict stride for DM = 2^(Index+Offset) = 2^(8+6) = 0x4000.

6.1 Address Set and Trace

Addresses (hex): A1=0x004030C0; A2=A1+0x4000=0x004070C0; A3=A1+0x8000=0x0040B0C0;
A4=A1+0xC000=0x0040F0C0; and in-block neighbors A1+0x18, A2+0x20, A3+0x38.

12-access trace T: <A1, A1+0x18, A2, A2+0x20, A1, A3, A3+0x38, A1, A2, A3, A4, A1>.

6.2 Direct-Mapped (DM) Bit-Accurate Walk-Through

Address format: [Tag18 | Index8 | Offset6]. Example A1 (0x004030C0): Tag=0x100, Index=0xC3, Offset=0.

Step Access Index Tag Hit/Miss Eviction/Action

1 A1 C3 100 Miss Load
line([Link]=100)
2 A1+18 C3 100 Hit Same block
3 A2 C3 101 Miss Evict 100 →
Load 101
4 A2+20 C3 101 Hit —
5 A1 C3 100 Miss Evict 101 →
Load 100
6 A3 C3 102 Miss Evict 100 →
Load 102
7 A3+38 C3 102 Hit —
8 A1 C3 100 Miss Evict 102 →
Load 100
9 A2 C3 101 Miss Evict 100 →
Load 101
10 A3 C3 102 Miss Evict 101 →
Load 102
11 A4 C3 103 Miss Evict 102 →
Load 103
12 A1 C3 100 Miss Evict 103 →
Load 100
Totals (DM): Hits=3, Misses=9. Example AMAT (Hit=1 cyc, Penalty=80): 61.0 cycles.

6.3 2-Way Set-Associative (SA) with LRU

Address format: [Tag19 | Set7 | Offset6]. All A1–A4 map to Set=0x43 but can occupy two ways.

Step Access Set Tag Hit/Miss Before After

(ways) (ways) /
Eviction
1 A1 43 513 Miss [–, –] [513, –]
2 A1+18 43 513 Hit [513, –] [513, –]
3 A2 43 515 Miss [513, –] [515, 513]
4 A2+20 43 515 Hit [515, 513] [515, 513]
5 A1 43 513 Hit [515, 513] [513, 515]
6 A3 43 517 Miss [513, 515] Evict 515
→ [517,
513]
7 A3+38 43 517 Hit [517, 513] [517, 513]
8 A1 43 513 Hit [517, 513] [513, 517]
9 A2 43 515 Miss [513, 517] Evict 517
→ [515,
513]
10 A3 43 517 Miss [515, 513] Evict 513
→ [517,
 515]
11 A4 43 519 Miss [517, 515] Evict 515
→ [519,
517]
12 A1 43 513 Miss [519, 517] Evict 517
→ [513,
519]
Totals (2-way SA): Hits=5, Misses=7. Example AMAT (Hit=2 cyc, Penalty=80): 48.67 cycles.

6.4 Fully Associative (FA) with LRU

Address format: [Tag26 | Offset6]. 4 unique blocks; cache has 256 lines → all co-exist after first touches.

Step Access Hit/Miss Notes

1 A1 Miss First touch of A1
block
2 A1+18 Hit Same block as A1
3 A2 Miss First touch of A2
block
4 A2+20 Hit Same block as A2
5 A1 Hit Already resident
6 A3 Miss First touch of A3
block
7 A3+38 Hit Already resident
8 A1 Hit Already resident
9 A2 Hit Already resident
10 A3 Hit Already resident
11 A4 Miss First touch of A4
block
12 A1 Hit Already resident
Totals (FA): Hits=8, Misses=4. Example AMAT (Hit=3 cyc, Penalty=80): 29.67 cycles.

6.5 Write-Policy Mini-Example

Assume Write-Back + Write-Allocate on DM. Read A1 (miss, fill); Write A1+4 (hit, mark dirty); Read A2 (conflict miss,
evict A1 → write-back); Write A1 (miss, evict A2 if clean, then fill A1 dirty). DM thrash increases write-backs; SA often
reduces these evictions.
7) Lab Activities (In-Lab Procedure)
Activity A — Address Partitioning Warm-up (compute Offset/Index/Tag; sketch bit partitions).

Data Table A (sample results):

Case C B A L=C/B S=L/A Offset SetIdx Tag

A1 8KiB 32B 1 256 256 5 8 19
A2 16KiB 64B 2 256 128 6 7 19
A3 4KiB 32B FA 128 1 5 0 27
Activity B — DM Hit/Miss Timeline (use Table B above).

Activity C — 2-Way SA with LRU (use per-set table above).

Activity D — FA with LRU (unique-stream analysis).

Activity E — Engineering Conflicts (DM vs SA stride analysis).

Activity F — AMAT Comparison (compute and compare).

Activity G — VIPT Constraint Check (SetIndex+Offset ≤ PageOffset).

Activity H — Tag Store Overhead (compute tag/meta and PLRU bits).

8) Post-Lab Questions
1. Identify conflict misses in your DM timeline and explain how SA reduces them.
2. Under what miss-rate improvement does a slower SA hit time break even with DM?
3. Trade-offs among LRU, PLRU, and Random at higher associativities.
4. When is write-back with write-allocate preferable over write-through?

9) Deliverables & Grading Rubric

Deliverables: Pre-lab answers; Activities A–H tables; brief discussion (≤1 page); Post-lab answers.

Rubric (100 pts):

 Pre-lab (10) • Activities A–D (32) • Activities E–H (32) • Discussion (16) • Post-lab (10)
10) Review & Exercise Problems (with Solutions)
5. Q1 (Bits — DM)

C=32 KiB, B=64 B, Direct-Mapped. Compute offset/index/tag bits.

Solution: L=32768/64=512; Offset=log2(64)=6; Index=log2(512)=9; Tag=32−(6+9)=17. Format [17|9|6].

6. Q2 (Bits — 2-way SA)

C=16 KiB, B=32 B, A=2. Compute Offset/SetIndex/Tag.

Solution: L=16384/32=512; S=512/2=256; Offset=5; SetIndex=8; Tag=32−(8+5)=19. [19|8|5].

7. Q3 (Mapping)

Use Q2. For address 0x12345678, compute block, set, tag.

Solution: block=addr>>5; set=(addr>>5) & 0xFF; tag=addr>>(5+8)=addr>>13.

8. Q4 (DM Conflict Crafting)

Using Q1 parameters, show two addresses that collide in DM.

Solution: Add 2^(Index+Offset)=2^15=0x8000. X=0x00401000 and X’=0x00481000 collide.

9. Q5 (DM Trace Miss Count)

DM, C=8 KiB, B=32 B. Trace: X, X+0x2000, X, X+0x4000, X+0x2000, X (cold). Count misses.

Solution: 0x2000 keeps same index. Sequence yields 6 misses (ping-pong + cold).

10. Q6 (2-way SA Trace)

Same addresses as Q5 but 2-way SA, LRU. Count misses.

Solution: Misses on first appearances only when ≤2 contenders per set → 3 misses total.

11. Q7 (FA Unique Stream)

FA, C=4 KiB, B=32 B. Unique stream of 130 blocks. How many misses?

Solution: L=4096/32=128; 128 compulsory + 2 capacity = 130 misses.

12. Q8 (AMAT)

HitTime=1.5 cyc, MissPenalty=100 cyc. A: MissRate=4%. B: MissRate=2.7% but HitTime=2.1

cyc. Which is better?

Solution: A=1.5+0.04×100=5.5 cyc; B=2.1+0.027×100=4.8 cyc → B is better.

13. Q9 (Tag Store Overhead)

32-bit, C=64 KiB, B=64 B, 4-way. Per line: Tag(18)+Valid(1)+Dirty(1). Compute tag/meta
bits.

Solution: L=65536/64=1024; bits=1024×(18+2)=20,480 ≈ 2.5 KiB; PLRU per set: (A−1)=3 bits × S=256 ⇒ 768 bits.

14. Q10 (VIPT Check)

4 KiB pages (12-bit offset), B=64 B (Offset=6), A=8. Largest legal L1D under VIPT?

Solution: SetIndex ≤ 12−6=6 ⇒ S≤64 ⇒ C=A×S×B=8×64×64=32 KiB.