Suppose we have an 8-way set associative physically addressed cache of size…

Concept:

For an n-way set-associative cache, the physical address splits into three fields: tag, index, and block offset. The block offset needs log2(block size) bits, and the number of index bits equals log2(number of sets), where the number of sets = total cache size / (block size × associativity). Only the index bits identify which SET a block maps to; associativity does not change the offset.

Application:

1. Convert the cache size to bytes: 512 KB = 512 × 1024 = 524,288 B.

2. Find the total number of blocks the cache holds: 524,288 B ÷ 64 B = 8,192 blocks.

3. Divide the blocks into sets using the associativity (8-way, so 8 blocks per set): number of sets = 8,192 ÷ 8 = 1,024 sets.

4. The index field must be able to select any one of these 1,024 sets, so index bits = log2(1,024) = 10 bits, since 210 = 1,024.

Cross-check:

Derive it the other way, starting from a direct-mapped (1-way) cache of the same size and then folding in the associativity. For a direct-mapped 512 KB cache with 64 B blocks, the offset+index together need log2(524,288) = 19 bits, and the offset alone needs log2(64) = 6 bits, so the direct-mapped index would need 19 − 6 = 13 bits. Going from direct-mapped to 8-way associative merges every 8 lines into one set, which removes log2(8) = 3 index bits: 13 − 3 = 10 bits — the same result. The full 32-bit address then splits as tag (32 − 10 − 6 = 16 bits) + index (10 bits) + offset (6 bits) = 32 bits, which checks out.

Final answer: 10 bits are used for the index.

Reference derivation (handwritten):