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.
KnowledgeGate Team
Exam prep & CS education

Set associative mapping questions look like one formula, but students often mix up lines, sets, ways, block numbers and byte offsets. One wrong quantity corrupts every later step. For the 18-bit, 8 KiB, 16-byte-block, 4-way cache, the address determines the set, tag and offset, while the trace determines the result and LRU victim. The GATE CS Exam Preparation page gives wider study context.
Set associative mapping from zero: blocks, sets and ways
Main memory is divided into equal-sized blocks. Cache data is divided into equal-sized lines, each holding one block. A set groups cache lines. Lines per set are the associativity or number of ways.
In a k-way cache, a block maps to one set but may occupy any of its k lines. An eight-line, 2-way cache has:
Number of sets
= 8 / 2 = 4.Each set contains two lines.
Blocks
0,4and8all map to setblock number mod 4 = 0.
Only two can coexist in set 0, even if another set is empty. Direct mapping is 1-way. Fully associative mapping places every line in one set. Set associative mapping lies between them. More ways can reduce conflict misses, but need parallel tag checks and an in-set victim choice.
Cache geometry and the address-field equations
The running machine has byte-addressable memory of 256 KiB = 2^18 bytes, so addresses are 18 bits. Cache data capacity is 8 KiB = 2^13 bytes, excluding tag and status metadata. Blocks are 16 bytes = 2^4 bytes, with 4-way associativity.
Compute the geometry in this order:
Cache lines
= 2^13 / 2^4 = 2^9 = 512.Sets
= 512 / 4 = 128 = 2^7.Byte-offset bits
= log2 16 = 4.Set-index bits
= log2 128 = 7.Tag bits
= 18 - 7 - 4 = 7.
The address field order is therefore tag[17:11] | set[10:4] | byte offset[3:0].
Two methods are equivalent. Calculate block = floor(byte address / 16), set = block mod 128, and tag = floor(block / 128). Or write exactly 18 binary bits and split them 7 | 7 | 4. This is physical byte-address interpretation, not instruction addressing-mode calculation. For hierarchy, a direct-mapped address trace and a one-cache AMAT baseline, see Memory Organisation and Performance: Cache Mapping, AMAT and Worked GATE Examples. The narrower task here is 4-way set selection and true LRU within one set.
Fully worked address decode: where does 0x2B6D4 go?

First check the range. 0x2B6D4 = 177876, which fits because the largest 18-bit address is 0x3FFFF. Its exact 18-bit representation is:
101011011011010100 = 1010110 | 1101101 | 0100
Now decode each field:
Tag
1010110₂ = 86 = 0x56.Set
1101101₂ = 109 = 0x6D.Byte offset
0100₂ = 4.
The arithmetic method gives the same answer. Block number = floor(177876 / 16) = 11117 = 0x2B6D. Then 11117 mod 128 = 109, while floor(11117 / 128) = 86.
The controller selects set 109 and compares tag 86 with four valid tag entries in parallel. A hit uses byte 4 of the matching line. Otherwise, a free way or the set's replacement victim receives block 11117.

Worked LRU access trace inside set 109
Start with set 109 empty. Use A=0x296D4, B=0x29ED4, C=0x2A6D4, D=0x2AED4, A=0x296D4, C=0x2A6D4, E=0x2B6D4, B=0x29ED4. Every address has offset 4 and set 109. Their tags are 82, 83, 84, 85, 82, 84, 86, 83. In the table, order runs from least recently used to most recently used.
Step | Address | Tag | Hit/Miss | Victim | LRU -> MRU after access |
|---|---|---|---|---|---|
1, A |
| 82 | Miss | None |
|
2, B |
| 83 | Miss | None |
|
3, C |
| 84 | Miss | None |
|
4, D |
| 85 | Miss | None |
|
5, A |
| 82 | Hit | None |
|
6, C |
| 84 | Hit | None |
|
7, E |
| 86 | Miss | 83 |
|
8, B |
| 83 | Miss | 85 |
|
The result is 2 hits and 6 misses over 8 accesses. Hit rate = 2/8 = 25%; miss rate = 6/8 = 75%. If ways fill in order, final physical contents are Way 0=82, Way 1=86, Way 2=84, Way 3=83. Recency order is 82,84,86,83. Hits change recency without changing physical way number.
What associativity changes: conflicts, lookup cost and AMAT
In an eight-line cache, repeat blocks 0,8,16,24,0,8,16,24. Direct mapping sends all four to line 0, producing eight misses. A 2-way cache sends them to two lines in set 0, so LRU again gives eight misses. A 4-way cache retains all four in set 0, giving four compulsory misses then four hits. A fully associative cache gives the same result.
Higher associativity is not automatically faster. Extra ways need more comparators, a wider data choice and replacement state. Hit time, power and policy matter with miss rate.
For teaching values, use AMAT = hit time + miss rate x miss penalty. A 4-way cache with 1.2 ns, 4% and 45 ns gives 1.2 + 0.04 x 45 = 3.0 ns. An illustrative direct-mapped cache with 1.0 ns, 6% and 45 ns gives 1.0 + 0.06 x 45 = 3.7 ns. These inputs show why the lower miss rate can offset the 4-way cache's 0.2 ns slower hit time.
Common set associative mapping traps and corrections
Trap | What goes wrong | Correction |
|---|---|---|
Treating 4-way as four sets | Ways and sets are confused | Divide total lines by four to get sets |
Dividing capacity by ways first | A factor is easily lost while finding lines | Find |
Using | The byte offset contaminates the mapping | Use |
Counting offset in words | Byte-addressable memory is ignored | Use |
Taking | Four-way grouping is ignored | Use |
Subtracting block size twice | A false 3-bit tag appears | Use |
The first access to block 11117 is compulsory. Eviction when more than four competing blocks map to set 109 is a conflict in this organisation. A capacity miss is established only when the active working set cannot fit in the entire 512-line cache, not merely when one set overflows. Also use true LRU only when the question states it. Real caches may use pseudo-LRU or another policy.
How exams test set associative mapping
Exam-style prompts ask you to derive geometry and address bits, decode hexadecimal addresses, trace replacement, or compare tag overhead or AMAT. Check the answer format too. Single correct, multiple correct and numerical questions need different handling, as explained in MCQ, MSQ or NAT? GATE Question Types Explained.
Try these three checks before reading the answers:
A 32-bit byte-addressable system has a 32 KiB cache, 64-byte blocks and 8 ways. Find lines, sets, offset bits, set bits and tag bits.
In the running cache, map
0x2B6D4completely.Evaluate the stated 4-way AMAT.
Answers
512lines,64sets,6offset bits,6set bits and20tag bits.Block
11117, set109, tag86, offset4.3.0 ns.
Set associative mapping: the short version and next step
Use this solve order every time:
Compute cache lines.
Divide lines by ways to get sets.
Take
log2for offset and set bits.Subtract those fields from address width to get tag bits.
Map the block, then apply the stated replacement policy.
For the running example, 0x2B6D4 -> block 11117 -> set 109, tag 86, offset 4.
Now redraw the 7 | 7 | 4 split and reproduce the eight-access LRU table without looking. Explain why C hits at step 6 but B misses at step 8. If you cannot name evicted tags 83 and 85, repeat the trace instead of memorising 25%.
For structured wider GATE CS study, continue with GATE Guidance by Sanchit Sir. For broader computer science fundamentals, use Zero to Hero Complete CS Course.
Keep learning
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.
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.
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.
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.





