A cache is 16KB (16384 bytes) in size and stores 64 byte blocks. Physical memory addresses are 32 bits (a) How many address bits are used for the byte offset? (b) Determine the number of sets and the number of tag bits for the following configurations (show how you arrived at your answers): (G) Direct mapped. (i) 4-way set associative (iii) Fully associative
The Correct Answer and Explanation is :
Solution:
(a) Byte Offset Calculation:
Each block in the cache is 64 bytes. Since the byte offset determines which byte within a block is being addressed, we need log₂(block size) = log₂(64) = 6 bits.
Thus, 6 address bits are used for the byte offset.
(b) Cache Configurations:
The cache size is 16 KB = 16 × 1024 = 16384 bytes
Each block is 64 bytes, so the number of blocks in the cache is: 16384 bytes64 bytes/block=256 blocks\frac{16384 \text{ bytes}}{64 \text{ bytes/block}} = 256 \text{ blocks}
The physical memory address is 32 bits long, and we will determine the number of sets and tag bits for each configuration.
(G) Direct Mapped Cache:
- Each memory block maps to exactly one set.
- The number of sets is equal to the number of blocks: 256 sets.
- Index bits: Since there are 256 sets, we need log₂(256) = 8 bits for indexing.
- Tag bits: The remaining bits in the address after accounting for the byte offset (6 bits) and the index (8 bits) are: 32−(6+8)=18 tag bits32 – (6 + 8) = 18 \text{ tag bits}
Final Values for Direct Mapped:
- Number of sets: 256
- Tag bits: 18
(i) 4-Way Set Associative Cache:
- In a 4-way set associative cache, each set contains 4 blocks.
- The total number of sets is: 256 blocks4 blocks/set=64 sets\frac{256 \text{ blocks}}{4 \text{ blocks/set}} = 64 \text{ sets}
- Index bits: Since we have 64 sets, we need log₂(64) = 6 bits.
- Tag bits: The remaining address bits are: 32−(6+6)=20 tag bits32 – (6 + 6) = 20 \text{ tag bits}
Final Values for 4-Way Set Associative:
- Number of sets: 64
- Tag bits: 20
(iii) Fully Associative Cache:
- In a fully associative cache, there is only one set, and all blocks can be placed anywhere.
- The number of sets = 1.
- Index bits: Since there is only one set, no index bits are needed.
- Tag bits: The remaining address bits are: 32−6=26 tag bits32 – 6 = 26 \text{ tag bits}
Final Values for Fully Associative:
- Number of sets: 1
- Tag bits: 26
Summary of Results:
| Cache Type | Number of Sets | Index Bits | Tag Bits |
|---|---|---|---|
| Direct Mapped (1-way) | 256 | 8 | 18 |
| 4-Way Set Associative | 64 | 6 | 20 |
| Fully Associative | 1 | 0 | 26 |
Explanation:
The key to solving cache mapping problems is understanding how an address is divided into tag, index, and offset. The byte offset comes from the block size (log₂(block size)), the index bits depend on the number of sets (log₂(number of sets)), and the tag bits are whatever remains.
- Direct Mapped caches have one block per set, meaning the number of sets equals the number of blocks.
- Set Associative caches group multiple blocks into a set, reducing the number of sets but increasing the tag bits.
- Fully Associative caches have only one set, meaning there are no index bits, and most of the address is used for the tag.
This structured approach ensures an efficient mapping of memory addresses to cache locations while balancing performance and complexity.