Set Associative Mapping: Address Split, LRU Trace and a 4-Way Cache Worked Example

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, 4 and 8 all map to set block 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:

1. Cache lines = 2^13 / 2^4 = 2^9 = 512.

2. Sets = 512 / 4 = 128 = 2^7.

3. Byte-offset bits = log2 16 = 4.

4. Set-index bits = log2 128 = 7.

5. 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.

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

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:

1. 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.

2. In the running cache, map 0x2B6D4 completely.

3. Evaluate the stated 4-way AMAT.

Answers

1. 512 lines, 64 sets, 6 offset bits, 6 set bits and 20 tag bits.

2. Block 11117, set 109, tag 86, offset 4.

3. 3.0 ns.

Set associative mapping: the short version and next step

Use this solve order every time:

1. Compute cache lines.

2. Divide lines by ways to get sets.

3. Take log2 for offset and set bits.

4. Subtract those fields from address width to get tag bits.

5. 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.