Cache Memory Practice Questions

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 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$.

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.

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.