Associative Mapping in Cache Memory: Address Fields, Worked Example and Exam Traps

Learn why fully associative cache addresses have no index field. Derive the tag, follow an exact LRU trace, compare mapping methods and avoid common exam mistakes.

KnowledgeGate Team

Exam prep & CS education

Updated 8 Nov 20265 min read
Associative Mapping in Cache Memory: Address Fields, Worked Example and Exam Traps

Learners remember that a block can go "anywhere" in a fully associative cache, then still allocate line bits. Others split the address correctly but lose track of LRU after a hit. Fully associative placement allows a block to use any cache line, while an LRU trace shows how a hit changes recency. The GATE CS Exam Preparation Courses & Test Series page places cache within the wider COA syllabus.

Associative Mapping in Cache Memory: The Placement Rule

A memory block is a fixed-size group of consecutive memory locations. A cache line holds one block. Its tag identifies that block, while the byte offset identifies a byte inside it.

In fully associative mapping, any main-memory block may occupy any cache line, so the address selects no predetermined line. Lookup is associative because the requested tag is compared with every valid line tag in parallel in the textbook model. Keep this cache method distinct from the broader hardware term content-addressable memory.

Mapping method

Eligible location for a memory block

Direct mapping

Exactly one cache line

Fully associative mapping

Any cache line

k-way set-associative mapping

One selected set, then any of its k lines

Associative Mapping Address Format: Derive Tag and Offset

Use one fixed system throughout:

  • Byte-addressable main memory = 1 MiB = 2^20 bytes, giving 20 address bits.

  • Cache = 4 KiB = 2^12 bytes.

  • Block size = 16 bytes = 2^4 bytes, giving 4 offset bits.

  • Main-memory blocks = 2^20 / 2^4 = 2^16.

  • Cache lines = 2^12 / 2^4 = 2^8 = 256.

Fully associative mapping has zero index bits. Therefore Tag = 20 - 4 = 16 bits and Byte offset = 4 bits. The 256 lines determine stored entries and parallel tag comparisons, not an 8-bit address index.

For byte address 0x3A7C5:

  • Decimal address = 239,557.

  • Block number = floor(239,557 / 16) = 14,972 = 0x3A7C.

  • Byte offset = 239,557 mod 16 = 5 = 0x5.

The tag is 0x3A7C. A matching valid line means a hit, regardless of its physical number.

Diagram of address 0x3A7C5 split into a 16-bit tag and 4-bit offset, with tag comparison across 256 cache lines.

Associative Mapping Worked Example: Trace Hits, Misses and LRU

Use four fully associative lines L0 to L3, 4-byte blocks, an empty cache and LRU. Convert using block = floor(address / 4) and offset = address mod 4.

Step

Byte address

(Block, offset)

Result and action

LRU order, oldest to newest

1

12

(3, 0)

Miss, put B3 in L0

B3

2

28

(7, 0)

Miss, put B7 in L1

B3, B7

3

44

(11, 0)

Miss, put B11 in L2

B3, B7, B11

4

60

(15, 0)

Miss, put B15 in L3

B3, B7, B11, B15

5

13

(3, 1)

Hit B3 in L0, read offset 1

B7, B11, B15, B3

6

76

(19, 0)

Miss, evict B7 from L1

B11, B15, B3, B19

7

29

(7, 1)

Miss, evict B11 from L2

B15, B3, B19, B7

There is 1 hit and 6 misses. Hit ratio = 1/7 = 14.29% and miss ratio = 6/7 = 85.71%. Full associativity avoids fixed-line conflicts, not compulsory misses such as each block's first reference. After four lines fill, replacement also makes the final B7 reference a capacity miss.

Seven-access LRU trace showing one hit, six misses, evictions of B7 and B11, final line contents, and recency order.

Associative Lookup Hardware: What the Flexibility Costs

In the 256-line system, lookup broadcasts the 16-bit tag to every valid tag entry. Parallel comparators produce match signals, selection logic chooses the matching 16-byte block, and the 4-bit offset chooses one byte. A correctly managed cache has at most one valid match.

Comparing many entries costs comparator hardware, wiring, energy and selection logic. Full associativity removes index-based conflict misses, but its lookup machinery is more involved.

Keep three decisions separate. Mapping defines eligible locations. Replacement chooses a victim on a full-cache miss. Write policy controls stores, covered in Cache Write Policies & AMAT Numericals for GATE.

Associative vs Direct and Set-Associative Mapping: One Numeric Comparison

Reuse the same memory, cache and block sizes so only mapping changes.

Mapping

Index or set bits

Offset bits

Tag bits

Direct, 256 lines

8

4

20 - 8 - 4 = 8

Fully associative

0

4

20 - 0 - 4 = 16

Four-way set-associative, 64 sets

6

4

20 - 6 - 4 = 10

For blocks B5, B261 and B517, direct mapping gives block mod 256 = 5, so all compete for line 5. Four-way mapping gives block mod 64 = 5, but they fit in three of set 5’s four ways. Fully associative mapping allows any three lines. Cache Memory Mapping and Hit Ratio: Solved Examples compares all three mapping methods and extends the arithmetic to AMAT; the fully associative address fields, parallel lookup and LRU trace above isolate the no-index case.

Associative Mapping Exam Traps and Fast Checks

  • Adding index bits: a fully associative address uses zero index bits.

  • Deleting the offset too: the block offset remains because a line holds multiple bytes.

  • Using modulo to choose a line: no fixed line is selected.

  • Using the whole byte address as the tag: remove the offset first.

  • Ignoring replacement: free placement still needs a victim rule when the cache is full.

  • Confusing fully associative and set-associative mapping: the latter selects one set.

Run three checks: 1 MiB byte-addressable memory needs 20 address bits; a 16-byte block needs 4 offset bits; and 4 KiB / 16 B = 256 lines, yet contributes zero index bits here. For word-addressable memory, rebuild the offset in addressable words.

Full associativity eliminates fixed-index conflict misses. It does not eliminate compulsory or capacity misses, as the trace demonstrates.

How Exams Test Associative Mapping

Questions ask you to derive fields, infer comparator or tag-store requirements, trace LRU or FIFO, compare conflicts, and separate mapping, replacement and write policy.

Use a fixed solving order:

  1. Identify the addressable unit.

  2. Calculate total address bits and show the unit.

  3. Divide block size by the addressable unit to calculate offset bits.

  4. Set index bits to zero only for fully associative mapping.

  5. Assign all remaining address bits to the tag.

  6. Trace replacement state separately from the address split.

Keeping units beside every division prevents most silent mistakes.

Associative Mapping: The Short Version and Next Step

Remember four facts: any block may use any line; the address has a tag and offset but no index; every valid tag is searched in parallel in the textbook model; replacement still matters when full.

Redo the 0x3A7C5 split without notes. Then reproduce the seven-access LRU table and explain both evictions aloud. If you want the wider COA and GATE study sequence organised for you, GATE Guidance by Sanchit Sir is the structured next step.