Cache Mapping Techniques and Memory Units: Direct, Associative and Set-Associative Worked Example

The three mapping names are easy to memorise. Numericals become confusing when blocks, lines, sets, tag bits, index bits and offset bits appear together. Cache Memory: Mapping Techniques and Hit Ratio explains hierarchy, locality and AMAT. Keeping address 0x3A6F, 64 KiB memory, a 1 KiB cache and 16-byte blocks constant isolates how placement changes tag and index fields. GATE CS Exam Preparation places the calculation in the wider syllabus.

Memory units and address bits: convert to powers of two first

Keep capacity units separate from address counts. 1 byte = 8 bits, 1 KiB = 2^10 bytes, and 1 MiB = 2^20 bytes. If a question explicitly says decimal kB, use 10^3 bytes. If it says KiB, use 2^10 bytes. Never change the stated convention silently.

Our byte-addressable main memory is 64 KiB = 64 x 2^10 = 2^16 bytes. It therefore has 2^16 separately addressable byte locations, so each address needs 16 bits. The block size is 16 bytes = 2^4 bytes, which means the lowest 4 address bits select a byte within one block.

The reliable rule is simple: a byte-addressable memory containing 2^m bytes needs m address bits, while a block containing 2^b bytes needs b block-offset bits. Do not multiply the address width by eight merely because one byte contains eight bits.

Blocks, cache lines, sets and ways: build the system first

A main-memory block is the unit transferred to the cache. A cache line is one slot that can hold one complete block. With 2^16 bytes of main memory and 2^4 bytes per block, the number of memory blocks is 2^16 / 2^4 = 2^12 = 4096. A 1 KiB = 2^10 byte cache similarly contains 2^10 / 2^4 = 2^6 = 64 lines.

A set groups cache lines, and each line position inside a set is a way. Direct mapping is 1-way, so its 64 lines form 64 sets. A 4-way cache has 64 / 4 = 16 sets, each with four ways. A fully associative cache treats all 64 lines as one set, so a block can enter any line.

Direct mapping worked step by step for address 0x3A6F

Start by converting the address. 0x3A6F = 14959, and its 16-bit binary form is 0011 1010 0110 1111.

1. Find the block: floor(14959 / 16) = 934.

2. Find the byte offset: 14959 mod 16 = 15.

3. Map the block to one of 64 lines: 934 mod 64 = 38.

4. Find the tag: floor(934 / 64) = 14.

The block size fixes 4 offset bits. There are 64 = 2^6 lines, so the line index needs 6 bits. The tag receives the remaining 16 - 6 - 4 = 6 bits. The real split is therefore 001110 | 100110 | 1111: tag 001110 = 14, line 100110 = 38, offset 1111 = 15.

During lookup, the cache uses the index to open line 38, compares its stored tag with 14, and, on a hit, selects byte 15.

Direct mapping can create conflicts. Block 998 starts at 998 x 16 = 15968 = 0x3E60. Since 998 mod 64 = 38, blocks 934 and 998 compete for line 38 even when other cache lines are free.

For direct mapping, AMAT and conflict tracing, use Memory Organisation and Performance: Cache Mapping, AMAT and Worked GATE Examples. The constant 0x3A6F system instead tracks which address bits move as associativity changes.

Fully associative and 4-way set-associative mapping

Fully associative mapping retains the 4 offset bits but has no index field. Its tag therefore needs 16 - 4 = 12 bits. For 0x3A6F, the split is 001110100110 | 1111: tag 001110100110 = 934 and offset 1111 = 15. Block 934 may occupy any of the 64 lines, so a lookup compares the requested tag against all eligible lines.

For 4-way set-associative mapping, 64 lines form 64 / 4 = 16 sets. The set index needs log2(16) = 4 bits. For the same block, set = 934 mod 16 = 6, tag = floor(934 / 16) = 58, and tag width is 16 - 4 - 4 = 8 bits. The split becomes 00111010 | 0110 | 1111: tag 58, set 6, offset 15. The block can use any of four ways in set 6.

Victim choice begins after a set fills. Set Associative Mapping: Address Split, LRU Trace and a 4-Way Cache Worked Example traces eight accesses with true LRU and computes AMAT.

A repeatable method for cache-mapping numericals

Use the same order every time:

1. Normalise units into powers of two: 64 KiB = 2^16, 1 KiB = 2^10, and 16 bytes = 2^4.

2. Find the address width: 16 bits.

3. Find the block offset: 4 bits.

4. Divide cache capacity by block size: 2^10 / 2^4 = 64 lines.

5. Convert ways into sets: 64 sets for direct mapping or 16 sets for 4-way mapping.

6. Give every remaining high-order bit to the tag: 6, 12, or 8 bits for direct, fully associative, or 4-way mapping.

Check that each field split totals 16 bits. Also check 64 x 16 = 1024 bytes = 1 KiB; for 4-way, 16 sets x 4 ways x 16 bytes = 1024 bytes. Here, cache size means data capacity. Add tag, valid, dirty and replacement-state bits only when total hardware storage is explicitly requested. Recompute it as 2-way and 8-way; each doubling moves one index bit into the tag.

Common cache-mapping traps and their corrections

Do not assume every capacity is a power of two. If a prompt gives a non-power-of-two size or an explicit mapping rule, follow that rule instead of forcing a neat bit-field split.

Cache mapping questions: recognise the operation before calculating

Common tasks ask you to derive tag, index and offset widths; locate an address; identify conflicting blocks; recover data capacity from line count and block size; compare eligible placements; or calculate metadata when all constituent bits are supplied.

For direct mapping of 0x3A6F, report block 934, line 38, tag 14 and offset 15. To test whether block 998 conflicts, compare 998 mod 64 with 934 mod 64; both equal 38. For 4-way placement, calculate set 6, then compare tag 58 across that set's four ways.

Recognising the requested operation prevents unnecessary calculations. Once you can name it, use the GATE Test Series as a next practice option for applying the method under test conditions.

Cache mapping techniques: the short version and next step

Block size fixes the offset bits. The mapping technique decides the eligible line or set, and every remaining high-order address bit becomes the tag. For 0x3A6F, direct mapping gives tag 14, line 38, offset 15; fully associative gives tag 934, offset 15; 4-way mapping gives tag 58, set 6, offset 15.

Redraw all three splits, then explain why the offset stays fixed while index bits move into the tag. Use the GATE Test Series above for timed practice.