GATE CS 2006 Q75 — Memory Hierarchy: Cache, Main Memory and Secondary Storage

To find the hit latency $h_2$ of the direct-mapped cache, we first need to determine the number of tag bits used in its address translation.

1. Address Division for the Direct-Mapped Cache

• Total Cache Size: $32 \text{ kB} = 2^{15} \text{ bytes}$
• Block Size: $32 \text{ bytes} = 2^5 \text{ bytes}$
• Number of Cache Blocks (Lines): $$\text{Number of Blocks} = \frac{\text{Cache Size}}{\text{Block Size}} = \frac{2^{15}}{2^5} = 2^{10} = 1024$$

For a $32$-bit physical address, the division of bits is as follows:

• Block Offset: $\log_2(32) = 5 \text{ bits}$
• Index Bits: $\log_2(1024) = 10 \text{ bits}$
• Tag Bits: $32 - (\text{Index Bits} + \text{Offset Bits}) = 32 - (10 + 5) = 17 \text{ bits}$

2. Calculating Hit Latency $h_2$

In a direct-mapped cache:

• A single tag comparison is performed to determine a hit.
• The size of the comparator required is equal to the number of tag bits ($k = 17$).
• The latency of a $k$-bit comparator is given as $\frac{k}{10} \text{ ns}$.
• Since there is only one way (direct-mapped), no multiplexer is needed to select between multiple ways.

Note: Calculating $h_1$ (for 2-way Set Associative Cache)

For completeness, let's calculate $h_1$:

• Number of sets = $\frac{32 \text{ kB}}{2 \times 32 \text{ B}} = 512 = 2^9 \implies 9 \text{ index bits}$.
• Tag bits = $32 - 9 - 5 = 18 \text{ bits}$.
• Comparator latency = $\frac{18}{10} = 1.8 \text{ ns}$.
• A 2-to-1 multiplexer ($0.6 \text{ ns}$) is required to select the correct way.
• $h_1 = 1.8 \text{ ns} + 0.6 \text{ ns} = 2.4 \text{ ns}$.