Question

A certain processor uses a fully associative cache of size 16 kB. The cache block size is 16 bytes. Assume that the main memory is byte addressable and uses a 32-bit address. How many bits are required for the Tag and the Index fields respectively in the addresses generated by the processor?

• A. 24 bits and 0 bits
• B. 28 bits and 4 bits
• C. 24 bits and 4 bits
• D. 28 bits and 0 bits

Hint:

For a {fully associative cache}: Index bits are always {0}. Tag bits $=$ Address bits $-$ Offset bits.

Answer 1

The Correct Option is D

To determine how many bits are required for the Tag and the Index fields in the addresses generated by the processor, we need to analyze the cache structure and address format.

1. Main memory is byte-addressable, using a 32-bit address, meaning each address is 32 bits long.
2. The cache size is given as 16 kB (kilobytes). Since 1 kilobyte is 1024 bytes, the cache has a total of \(16 \times 1024 = 16384\) bytes.
3. The block size within the cache is 16 bytes. Therefore, the number of cache lines (or blocks) in the cache is calculated as: \(\frac{16384}{16} = 1024\) blocks.
4. In a fully associative cache, any block from main memory can be placed into any cache line. Therefore, there is no need for an Index field (i.e., 0 bits needed for the Index).
5. The memory address is divided into three parts: Tag, Index, and Block Offset.
   • The Block Offset is determined by the block size. Given a block size of 16 bytes, the Block Offset requires \(\log_2(16) = 4\) bits.
   • The total number of bits for the Index field in a fully associative cache is 0, as explained earlier.
   • Thus, the number of bits needed for the Tag is: \(32 \text{ bits (total address)} - 0 \text{ bits (Index)} - 4 \text{ bits (Block Offset)} = 28 \text{ bits}\).
6. Therefore, the processor address requires 28 bits for the Tag and 0 bits for the Index.

Conclusion: The correct option is 28 bits and 0 bits.

Answer 2

Step 1: Understand cache parameters.
Cache size $= 16$ kB $= 16 \times 1024 = 2^{14}$ bytes
Block size $= 16$ bytes $= 2^4$ bytes
Main memory address size $= 32$ bits
Step 2: Determine the number of cache blocks.
\[ \text{Number of cache blocks} = \frac{2^{14}}{2^4} = 2^{10} \] Step 3: Find the number of offset bits.
Since the memory is byte addressable and block size is $16$ bytes: \[ \text{Block offset bits} = \log_2 16 = 4 \text{ bits} \] Step 4: Determine index bits.
The cache is fully associative.
In a fully associative cache, there is no index field because any memory block can be placed in any cache block.
\[ \text{Index bits} = 0 \] Step 5: Calculate tag bits.
Address is divided as: \[ \text{Tag} + \text{Index} + \text{Offset} = 32 \text{ bits} \] Substitute known values: \[ \text{Tag} = 32 - 0 - 4 = 28 \text{ bits} \] Step 6: Conclusion.
The number of bits required for the Tag and Index fields are: \[ \boxed{28 \text{ bits and } 0 \text{ bits}} \]