Cache Memory – GATE CSE Computer Organization ArchitecturePractice Questions & PYQs

To find the maximum bandwidth, we calculate the data transferred per cache miss and divide by the time taken.

• Data transferred: One cache block is 8 words, and each word is 4 bytes. So, $8 \times 4 = 32$ bytes are transferred.
• Time taken: The process takes $1$ (address) $+ 3$ (fetch) $+ 8$ (transmit) $= 12$ clock cycles.
• The clock frequency is 60 MHz, so the duration of one cycle is $1 / (60 \times 10^6)$ seconds.
• Total time for transfer = $12 \times (1 / (60 \times 10^6)) = 1 / (5 \times 10^6)$ seconds.
• Bandwidth = Data / Time = $32 \text{ bytes} / (1 / (5 \times 10^6) \text{ s}) = 160 \times 10^6$ bytes/sec.

The main memory address is 32 bits long. The block size is 16 bytes, so the number of bits required for the word offset is $\log_2(16) = 4$ bits. In a fully associative cache, the entire cache is treated as a single set. This means there are no index bits needed to select a set (Index bits = 0). The remaining bits of the address are used for the tag. Therefore, the number of tag bits is $32 - (\text{index bits}) - (\text{offset bits}) = 32 - 0 - 4 = 28$ bits.

Cache coherency protocols manage data consistency in multi-processor systems. The question describes a method where write notifications are sent selectively, not broadcasted.

1. Snoopy Bus Protocols (A): These rely on a shared bus. Every processor snoops on the bus, and write transactions are broadcast to all processors, regardless of whether they have a copy of the data. This is inefficient for large systems.

2. Directory-Based Protocols (C): These protocols maintain a central directory that keeps track of which processors have a copy of each cache line. When a write occurs, the directory is consulted, and invalidation or update messages are sent via point-to-point messages only to the processors listed in the directory for that specific line. This perfectly matches the selective forwarding described in the question.

3. Cache Coherency Protocol (B): This is a general category that includes both snoopy and directory-based protocols, making it too broad and not the specific answer.

The size of the tag field is determined by subtracting the bits used for the set index and byte offset from the total physical address bits.

1. Physical Address (PA) bits: The physical address space is $2^P$ bytes, so the PA has $P$ bits.
2. Byte Offset bits: The block size is $2^M$ words, and word length is $2^W$ bytes. So, block size is $2^M \times 2^W = 2^{M+W}$ bytes. The number of bits for byte offset is $M+W$.
3. Set Index bits:
   • Cache capacity = $2^N$ bytes.
   • Number of blocks in cache = (Cache Capacity) / (Block Size) = $2^N / 2^{M+W} = 2^{N-M-W}$.
   • Number of sets = (Number of blocks) / K = $2^{N-M-W} / K$.
   • Set index bits = $\log_2(\text{Number of sets}) = \log_2(2^{N-M-W}/K) = N-M-W-\log_2 K$.
4. Tag bits:
   • Tag bits = PA bits - Set bits - Byte offset bits
   • Tag bits = $P - (N-M-W-\log_2 K) - (M+W)$
   • Tag bits = $P - N + M + W + \log_2 K - M - W = P - N + \log_2 K$.

The cache has 256 blocks and is 2-way set associative, so it has $256 / 2 = 128$ sets. A memory block b maps to set b mod 128.
The blocks {0, 128, 256} all map to Set 0.
The blocks {1, 129, 257} all map to Set 1.
The access sequence is repeated 10 times.

In the first iteration:

• Accesses to 0, 128, 1, and 129 cause 4 compulsory misses.
• Subsequent accesses to blocks that map to the same set (e.g., 256 to Set 0, 257 to Set 1) will cause conflict misses. In the first iteration, there are 4 such conflict misses.

In the remaining 9 iterations:

• All blocks have been accessed before, so there are no more compulsory misses.
• Each iteration has 8 misses (4 for Set 0 accesses, 4 for Set 1 accesses), all of which are conflict misses.
  Total conflict misses = (Conflict misses in 1st iteration) + (Misses in 9 other iterations)
  Total = $4 + (8 \times 9) = 4 + 72 = 76$.

The overall average read access time is a weighted average of the access times for instruction fetches and data fetches. We first calculate the average access time for each type of read.

1. Average access time for instruction fetch ($T_{avg\_instr}$): This involves the I-cache, L2 cache, and main memory.
   $T_{avg\_instr} = T_{I-cache} + (1 - H_{I-cache}) \times (T_{L2} + (1 - H_{L2}) \times T_{MM})$
   $T_{avg\_instr} = 2 + (1 - 0.8) \times (8 + (1 - 0.9) \times 90) = 2 + 0.2 \times (17) = 5.4 \text{ ns}$

2. Average access time for memory operand fetch ($T_{avg\_data}$): This involves the D-cache, L2 cache, and main memory.
   $T_{avg\_data} = T_{D-cache} + (1 - H_{D-cache}) \times (T_{L2} + (1 - H_{L2}) \times T_{MM})$
   $T_{avg\_data} = 2 + (1 - 0.9) \times (8 + (1 - 0.9) \times 90) = 2 + 0.1 \times (17) = 3.7 \text{ ns}$

3. Overall Average Read Access Time ($T_{avg\_read}$): This is a weighted sum based on the given percentages of instruction (60%) and data (40%) reads.
   $T_{avg\_read} = (0.60 \times T_{avg\_instr}) + (0.40 \times T_{avg\_data})$
   $T_{avg\_read} = (0.60 \times 5.4) + (0.40 \times 3.7) = 3.24 + 1.48 = 4.72 \text{ ns}$

The Average Memory Access Time (AMAT) for a two-level cache system is given by:
AMAT = $H_1 \times T_1 + (1-H_1) \times (H_2 \times (T_1+T_2) + (1-H_2) \times (T_1+T_2+T_M))$
A simpler formula is: AMAT = $T_{L1} + M_{L1} \times (\text{Miss Penalty}_{L1})$
Miss Penalty$_{L1}$ = $T_{L2} + M_{L2} \times (\text{Miss Penalty}_{L2})$
Given: $T_{L1}=1$, $T_{L2}=8$, Miss Penalty$_{L2}$ (from L2 to main memory) = 18. Let $M_{L2} = m$. Then $M_{L1} = 2m$. AMAT = 2.

AMAT = $T_{L1} + M_{L1} \times (T_{L2} + M_{L2} \times 18)$
$2 = 1 + (2m) \times (8 + m \times 18)$
$1 = 2m(8 + 18m)$
$1 = 16m + 36m^2$
$36m^2 + 16m - 1 = 0$
Solving this quadratic equation for $m$:
$m = \frac{-16 \pm \sqrt{16^2 - 4(36)(-1)}}{2(36)} = \frac{-16 \pm \sqrt{256 + 144}}{72} = \frac{-16 \pm \sqrt{400}}{72} = \frac{-16 \pm 20}{72}$
Since miss rate must be positive, $m = \frac{4}{72} = \frac{1}{18} \approx 0.0555$.
So, $M_{L2} = m \approx 0.056$.
And $M_{L1} = 2m \approx 0.111$.

The average memory access time ($T_{avg}$) is calculated using the access times of the cache and main memory, along with the hit ratio. The formula accounts for the time taken for a cache hit and the penalty incurred during a cache miss.

Given:
Cache Access Time ($T_c$) = $30$ ns
Main Memory Access Time ($T_m$) = $150$ ns
Hit Ratio ($H$) = $80\%$ = $0.8$
Miss Ratio ($1-H$) = $1 - 0.8 = 0.2$

The average access time is the cache access time plus the miss penalty:
$T_{avg} = T_c + (\text{Miss Ratio}) \times (\text{Miss Penalty})$
Assuming the miss penalty is the main memory access time:
$T_{avg} = T_c + (1 - H) \times T_m$
$T_{avg} = 30\ \text{ns} + (0.2) \times 150\ \text{ns} = 30\ \text{ns} + 30\ \text{ns} = 60\ \text{ns}$

Let the main memory address size be $M$ bits, cache capacity be $N$ words, and block size be $B$ words. The address is split into (Tag, Index, Offset). The number of offset bits is $\log_2(B)$.

Case 1: Direct Mapped

• Number of sets = Number of blocks = $N/B$.
• Index bits = $\log_2(N/B)$.
• Tag bits = $M - \text{Index} - \text{Offset} = M - \log_2(N/B) - \log_2(B) = M - \log_2(N)$.
• Given Tag = 10, so $10 = M - \log_2(N)$.

Case 2: 16-way Set-Associative

• Number of sets = (Number of blocks) / 16 = $(N/B)/16$.
• Index bits = $\log_2((N/B)/16) = \log_2(N/B) - 4$.
• Tag bits = $M - \text{Index} - \text{Offset} = M - (\log_2(N/B) - 4) - \log_2(B) = M - \log_2(N) + 4$.
• From Case 1, we know $M - \log_2(N) = 10$.
• Substituting this, Tag bits = $10 + 4 = 14$.

An application has 1.4 memory accesses per instruction. For 1000 instructions, the total number of memory accesses is $1.4 \times 1000 = 1400$.

The L1 miss rate is 0.1. The number of L1 misses (which become accesses to L2) is $1400 \times 0.1 = 140$.

The L2 cache experiences 7 misses per 1000 instructions. The L2 miss rate is the ratio of L2 misses to L2 accesses.

L2 Miss Rate = $\frac{\text{Number of L2 misses}}{\text{Number of L2 accesses}} = \frac{7}{140} = \frac{1}{20} = 0.05$.

The physical address size is 32 bits, as the main memory is $2^{32}$ bytes. The address is divided into tag, index (line number), and block offset fields.

1. Block Offset: The block size is 32 bytes ($2^5$ bytes). So, the block offset field requires 5 bits.
2. Index: The cache has 512 cache lines ($2^9$ lines). For a direct-mapped cache, the index field requires 9 bits to identify the line.
3. Tag: The remaining bits form the tag.
   Tag size = Total address bits - Index bits - Block offset bits
   Tag size = $32 - 9 - 5 = 18$ bits.

The average read latency is calculated as:
Avg Latency = (Hit Rate × Cache Latency) + (Miss Rate × Disk Latency)

Given: Cache Latency = 1 ms, Disk Latency = 10 ms. We need Avg Latency < 6 ms.

Let's test the cache sizes from the graph:

• For 20 MB cache: Miss Rate ≈ 60% (0.6). Hit Rate = 40% (0.4).
  Avg Latency = (0.4 × 1) + (0.6 × 10) = 0.4 + 6 = 6.4 ms. (Too high)
• For 30 MB cache: Miss Rate ≈ 40% (0.4). Hit Rate = 60% (0.6).
  Avg Latency = (0.6 × 1) + (0.4 × 10) = 0.6 + 4 = 4.6 ms. (Less than 6 ms)

Therefore, 30 MB is the smallest cache size that meets the requirement.

The physical address is composed of Tag, Set, and Offset bits. The total width is 40 bits.
The number of bits for the Set and Offset fields combined depends on the cache size, not the block size.
Total Cache Size = (Number of Sets) $\times$ (Associativity) $\times$ (Block Size)
In terms of bits:
$\log_2(\text{Cache Size}) = \log_2(\text{Num Sets}) + \log_2(\text{Associativity}) + \log_2(\text{Block Size})$
$19 = \text{Set bits} + 3 + \text{Offset bits}$
This gives: Set bits + Offset bits = $19 - 3 = 16$ bits.
The Tag bits are the remaining bits of the physical address:
Tag bits = Physical Address bits - (Set bits + Offset bits) = $40 - 16 = 24$ bits.

The average read access time is a weighted average of the cache hit time and the cache miss time. The formula is:
Average Access Time = (Hit Rate $\times$ Hit Time) + (Miss Rate $\times$ Miss Time)
Given a hit rate of 80% (0.8) and a hit time of 5 ns, the miss rate is $1 - 0.8 = 0.2$ (20%), and the miss time is 50 ns.
Substituting the values:
Average Access Time = $(0.8 \times 5 \text{ ns}) + (0.2 \times 50 \text{ ns}) = 4 \text{ ns} + 10 \text{ ns} = 14$ ns.

The main memory address is 20 bits long since the memory size is $2^{20}$ bytes. The block size is 16 bytes ($2^4$ bytes), so the block offset requires 4 bits. The cache has $2^{12}$ lines, so the cache line address (index) requires 12 bits. For a direct mapped cache, the remaining bits are for the tag.

Tag bits = Total address bits - Line bits - Offset bits = $20 - 12 - 4 = 4$ bits.
The 20-bit physical address is structured as: [Tag (4 bits) | Line (12 bits) | Offset (4 bits)].

The given main memory address is $(E201F)_{16}$. Let's convert this to a 20-bit binary number:
$(E201F)_{16} = (1110 \ 0010 \ 0000 \ 0001 \ 1111)_2$.

Now, we partition the binary address according to the structure:
Tag = First 4 bits = $(1110)_2 = (E)_{16}$.
Cache Line Address = Next 12 bits = $(0010 \ 0000 \ 0001)_2 = (201)_{16}$.
Offset = Last 4 bits = $(1111)_2 = (F)_{16}$.

Thus, the tag is $(E)_{16}$ and the cache line address is $(201)_{16}$.

Let $C$ be the cache capacity, $B$ be the block size, and $A$ be the associativity.
The number of sets in the cache is given by $S = \frac{C}{B \times A}$.
If associativity $A$ is doubled while $C$ and $B$ remain unchanged, the number of sets $S$ will be halved.
The width of the set index decoder is $\log_2(S)$. Halving $S$ means decreasing this width.
The tag size is determined by the main memory address width minus the block offset width and the set index width. Since the set index width changes, the tag size and thus the width of the tag comparator will also change.
The way selection multiplexor selects one out of $A$ ways, so its width depends on $A$. Doubling $A$ changes this width.
The width of the processor to main memory data bus is determined by the system architecture and is independent of cache organization parameters like associativity, capacity, or block size.

Here's a step-by-step explanation to determine the number of bits for the TAG field:

1. Determine Physical Address Bits: A physical address space of 4 GB (Gigabytes) is $2^2 \times 2^{30} = 2^{32}$ bytes. So, the physical address requires 32 bits.

2. Determine Block Size in Bytes: The block size is 8 words, and each word is 32 bits. Since 1 byte = 8 bits, 32 bits = 4 bytes. Therefore, the block size is $8 \text{ words} \times 4 \text{ bytes/word} = 32 \text{ bytes}$.

3. Calculate Block Offset Bits: The block size is 32 bytes, which is $2^5$ bytes. Thus, 5 bits are required for the block offset.

4. Calculate Number of Sets: The cache capacity is 16 KB ($16 \times 2^{10}$ bytes), and it is 4-way set-associative. The size of each set is $4 \times \text{block size} = 4 \times 32 \text{ bytes} = 128 \text{ bytes}$. The total number of sets is $\frac{\text{Cache Capacity}}{\text{Set Size}} = \frac{16 \times 1024 \text{ bytes}}{128 \text{ bytes}} = \frac{2^4 \times 2^{10}}{2^7} = 2^7 = 128 \text{ sets}$.

5. Calculate Set Offset Bits: Since there are 128 sets, which is $2^7$ sets, 7 bits are needed for the set offset.

6. Calculate TAG Bits: The physical address is divided into TAG, Set Offset, and Block Offset.
   $\text{TAG bits} = \text{Physical Address bits} - \text{Set Offset bits} - \text{Block Offset bits}$
   $\text{TAG bits} = 32 - 7 - 5 = 20 \text{ bits}$

[CORRECT_OPTION: 20]

A smaller cache block size means more cache blocks can fit into the cache for a given total cache capacity. While this might seem counter-intuitive, it's generally true that smaller blocks lead to a higher number of cache lines. A higher number of cache lines can potentially reduce the frequency of cache misses, especially when temporal locality is strong but spatial locality is weak or moderate. Reducing the number of misses directly leads to a lower cache miss penalty, as the system doesn't have to retrieve data from slower main memory as often.

Let's break down the memory access time for each type of operation.

Given:

• Cache hit ratio = 0.9 (meaning 90% hits, 10% misses)

1. Instruction Fetch (100 operations - Read):

   • Hit time: 1 ns (read hit)
   • Miss time: 5 ns (read miss)
   • Average access time for read = $(0.9 \times 1 \text{ ns}) + (0.1 \times 5 \text{ ns}) = 0.9 + 0.5 = 1.4 \text{ ns}$
   • Total time for instruction fetch = $100 \times 1.4 \text{ ns} = 140 \text{ ns}$

2. Memory Operand Read (60 operations - Read):

   • This is also a read operation, so the average access time is $1.4 \text{ ns}$.
   • Total time for operand read = $60 \times 1.4 \text{ ns} = 84 \text{ ns}$

3. Memory Operand Write (40 operations - Write):

   • Hit time: 2 ns (write hit)
   • Miss time: 10 ns (write miss)
   • Average access time for write = $(0.9 \times 2 \text{ ns}) + (0.1 \times 10 \text{ ns}) = 1.8 + 1.0 = 2.8 \text{ ns}$
   • Total time for operand write = $40 \times 2.8 \text{ ns} = 112 \text{ ns}$

Total time for all operations = $140 \text{ ns} + 84 \text{ ns} + 112 \text{ ns} = 336 \text{ ns}$
Total number of operations = $100 + 60 + 40 = 200$
Average memory access time = $\frac{336 \text{ ns}}{200} = 1.68 \text{ ns}$

[CORRECT_OPTION: 1.68]

Let N be the total length of the access sequence and n be the number of unique block addresses.
The number of unique block addresses between two consecutive accesses to the same block address is at most K.
With a cache associativity of A $\geq$ K, and using an LRU replacement policy, once a block is brought into the cache, it will remain there if it is re-accessed within K unique block accesses.
Since the cache associativity A is greater than or equal to K, the LRU policy guarantees that an already cached block will not be evicted if it's accessed again within K distinct block references. Therefore, each unique block address will incur a miss only on its first access.
Thus, the total number of misses will be equal to the number of unique block addresses, which is n.
The miss ratio is calculated as the total number of misses divided by the total length of the access sequence.
Miss Ratio = n / N.