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

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.

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.

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:
Identify the addressable unit.
Calculate total address bits and show the unit.
Divide block size by the addressable unit to calculate offset bits.
Set index bits to zero only for fully associative mapping.
Assign all remaining address bits to the tag.
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.
Keep learning
Set Associative Mapping: Address Split, LRU Trace and a 4-Way Cache Worked Example
Build set associative mapping from cache lines and sets, then decode 0x2B6D4, trace true LRU in one 4-way set, compare AMAT, and correct common numerical traps.
Cache Mapping Techniques and Memory Units: Direct, Associative and Set-Associative Worked Example
Use one address to learn memory-unit conversion, cache organisation and the exact tag, index and offset fields for all three mapping techniques.
Direct Mapping in Cache Memory: Address Bits, Cache-Line Mapping and a Hit-Ratio Worked Example
Learn how a direct-mapped cache chooses one line, splits a byte address into tag, index and offset, and creates conflict misses in a worked trace.
Set Associative Mapping MCQs: 12 Solved Cache Questions with Explanations
Solve 12 set associative cache MCQs step by step, from set mapping and address fields to tag hardware, hexadecimal slicing, and LRU conflicts.





