Cache Memory Practice Questions

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

1. Calculate the total number of blocks in the cache: The cache size is 256 KBytes, and the block size is 32 Bytes.
   Total blocks = $\frac{\text{Cache Size}}{\text{Block Size}} = \frac{256 \text{ KBytes}}{32 \text{ Bytes}} = \frac{256 \times 1024 \text{ Bytes}}{32 \text{ Bytes}} = 8192$ blocks.

2. Determine the number of sets in the cache: The cache is 4-way set associative, meaning each set contains 4 blocks.
   Number of sets = $\frac{\text{Total blocks}}{\text{Associativity}} = \frac{8192}{4} = 2048$ sets.

3. Calculate bits for block offset: Block size is 32 Bytes, so $2^{\text{Block offset bits}} = 32$.
   Block offset bits = $\log_2(32) = 5$ bits.

4. Calculate bits for set index: Number of sets is 2048, so $2^{\text{Set index bits}} = 2048$.
   Set index bits = $\log_2(2048) = 11$ bits.

5. Calculate bits for tag field: The total address is 32 bits. The tag bits are the remaining bits after subtracting the set index and block offset bits.
   Tag bits = Total address bits - Set index bits - Block offset bits = $32 - 11 - 5 = 16$ bits.

A 32-bit address is divided into three fields: Tag, Index, and Block Offset.
First, calculate the Block Offset size:
$\text{Block Size} = 32 \text{ bytes} = 2^5 \text{ bytes}$
So, the Block Offset is 5 bits.

Next, calculate the number of cache blocks (Index size):
$\text{Cache Size} = 8 \text{ KB} = 2^{13} \text{ bytes}$
$\text{Number of Blocks} = \frac{\text{Cache Size}}{\text{Block Size}} = \frac{2^{13}}{2^5} = 2^8 \text{ blocks}$
So, the Index is 8 bits.

Now, determine the Tag size:
$\text{Tag Bits} = \text{Total Address Bits} - \text{Index Bits} - \text{Block Offset Bits} = 32 - 8 - 5 = 19 \text{ bits}$

Each cache block's metadata consists of:

1. Valid bit: 1 bit
2. Modified bit: 1 bit
3. Tag bits: 19 bits
   Total metadata per block = $1 + 1 + 19 = 21$ bits.

Finally, calculate the total memory needed for metadata:
$\text{Total Metadata Size} = \text{Number of Blocks} \times \text{Metadata per Block} = 2^8 \times 21 = 256 \times 21 = 5376 \text{ bits}$

The question asks for the time taken for the transfer that occurs when there is a miss in L1 cache and a hit in L2 cache. This is commonly interpreted as the total time to service the L1 miss from the L2 cache, measured from the moment the CPU makes a memory request.

The process unfolds sequentially:

1. The CPU requests data, and the system first checks the L1 cache. This access takes 2 nanoseconds. The result is a miss.
2. Following the L1 miss, the system proceeds to check the L2 cache. This access takes 20 nanoseconds. The result is a hit, and the data is found.

The total time elapsed from the initial request until the data is located is the sum of the L1 and L2 access times, as these actions happen one after the other.

Total Time = Time to access L1 (and miss) + Time to access L2 (and hit)
Total Time = 2 ns + 20 ns = 22 ns

Once the data is found in L2, it is sent to the CPU, and the block is simultaneously transferred to L1. The overall time for this entire service operation is 22 ns.

The cache has $16$ blocks and is $4$-way set associative, so there are $16 / 4 = 4$ sets. A memory block $M$ maps to set $M \pmod 4$.

Let's examine the memory blocks from the options:
$3 \pmod 4 = 3$ (Set 3)
$8 \pmod 4 = 0$ (Set 0)
$129 \pmod 4 = 1$ (Set 1)
$216 \pmod 4 = 0$ (Set 0)

We need to trace the requests impacting Set 0, as both $8$ and $216$ map to it. The relevant requests are: $0, 4, 8, 216, 8, 48, 32, 92$.
Tracking Set 0 with LRU (elements listed from LRU to MRU):

1. Initially empty.
2. After $0, 4, 8, 216$: Set 0 = $[0, 4, 8, 216]$ (Set is full; $0$ is LRU).
3. Access $8$ (Hit): Set 0 = $[0, 4, 216, 8]$ ($0$ is still LRU).
4. Access $48$ (Miss): Evict $0$. Set 0 = $[4, 216, 8, 48]$ ($4$ is LRU).
5. Access $32$ (Miss): Evict $4$. Set 0 = $[216, 8, 48, 32]$ ($216$ is LRU).
6. Access $92$ (Miss): Evict $216$. Set 0 = $[8, 48, 32, 92]$.

After all requests, block $216$ has been evicted from Set 0. Blocks $3$ (Set 3), $8$ (Set 0), and $129$ (Set 1) are present in the cache.

The final answer is $\boxed{D}$

The cache parameters are:

• Block size (line size) = 64 bytes.
• Number of cache lines = 32.
• Main memory address bits: 16 ($2^{16}$ bytes).
• Offset bits: $\log_2(64) = 6$ bits.
• Index bits: $\log_2(32) = 5$ bits.
• Tag bits: $16 - 5 - 6 = 5$ bits.

The array is 50x50 bytes, so its total size is $50 \times 50 = 2500$ bytes.
The number of cache blocks required to store the array is $\lceil \frac{2500}{64} \rceil = 40$ blocks.

The array starts at memory location $1100H$. Let $B_k$ denote the $k$-th block of the array (for $k = 0, \dots, 39$).
The memory address of the start of $B_k$ is $Addr_k = 1100H + k \times 64$.
The block number in main memory for $B_k$ is $BlockNum_k = \frac{Addr_k}{64} = \frac{1100H}{64} + k = \frac{4352}{64} + k = 68 + k$.
For a direct-mapped cache, the cache index and tag for $B_k$ are:

• $Index_k = BlockNum_k \pmod{32} = (68 + k) \pmod{32}$
• $Tag_k = \lfloor \frac{BlockNum_k}{32} \rfloor = \lfloor \frac{68 + k}{32} \rfloor$

First Access (Array accessed for the first time):
Since the cache is initially empty, every access to a new block will be a compulsory miss.
There are 40 blocks in the array, so there will be 40 misses in the first access.
Total misses for first access = 40.

After the first access, the cache will contain the blocks that were loaded and not evicted by subsequent accesses during this pass. Let's determine the final state of the cache:

• For $k=0 \dots 27$: $Index_k = (68+k)\pmod{32}$ ranges from $4 \pmod{32} = 4$ to $95 \pmod{32} = 31$. $Tag_k = \lfloor (68+k)/32 \rfloor = \lfloor 68/32 \rfloor = 2$.
  • These 28 blocks ($B_0 \dots B_{27}$) occupy cache lines $4 \dots 31$ with Tag 2.
• For $k=28 \dots 39$: $Index_k = (68+k)\pmod{32}$ ranges from $96 \pmod{32} = 0$ to $107 \pmod{32} = 11$. $Tag_k = \lfloor (68+k)/32 \rfloor = \lfloor 96/32 \rfloor = 3$.
  • These 12 blocks ($B_{28} \dots B_{39}$) occupy cache lines $0 \dots 11$ with Tag 3.

Conflicts during the first pass:

• Blocks $B_0 \dots B_7$ (Tag 2) map to lines $4 \dots 11$.
• Blocks $B_{32} \dots B_{39}$ (Tag 3) also map to lines $4 \dots 11$. Since $B_{32} \dots B_{39}$ are accessed after $B_0 \dots B_7$, and their tags are different (3 vs 2), $B_{32} \dots B_{39}$ will evict $B_0 \dots B_7$ from lines $4 \dots 11$.

So, after the first access, the cache contains:

• Lines $0 \dots 3$: Contain blocks $B_{28} \dots B_{31}$ (Tag 3). (4 blocks)
• Lines $4 \dots 11$: Contain blocks $B_{32} \dots B_{39}$ (Tag 3), which evicted $B_0 \dots B_7$. (8 blocks)
• Lines $12 \dots 31$: Contain blocks $B_8 \dots B_{27}$ (Tag 2), as no later blocks map to these lines. (20 blocks)
  Total blocks in cache = $4+8+20 = 32$ blocks. The cache is full.

Second Access (Array accessed for the second time):
The array is accessed again in order $B_0, B_1, \dots, B_{39}$.

1. Access $B_0 \dots B_7$ (8 blocks):
   • These blocks map to lines $4 \dots 11$ with Tag 2.
   • Current cache lines $4 \dots 11$ hold $B_{32} \dots B_{39}$ (Tag 3).
   • The tags (2 vs 3) do not match. Each access will be a miss. These 8 blocks ($B_0 \dots B_7$) are loaded, evicting $B_{32} \dots B_{39}$.
   • Misses = 8.
2. Access $B_8 \dots B_{27}$ (20 blocks):
   • These blocks map to lines $12 \dots 31$ with Tag 2.
   • Current cache lines $12 \dots 31$ already hold $B_8 \dots B_{27}$ (Tag 2).
   • The tags match. Each access will be a hit.
   • Misses = 0.
3. Access $B_{28} \dots B_{31}$ (4 blocks):
   • These blocks map to lines $0 \dots 3$ with Tag 3.
   • Current cache lines $0 \dots 3$ already hold $B_{28} \dots B_{31}$ (Tag 3).
   • The tags match. Each access will be a hit.
   • Misses = 0.
4. Access $B_{32} \dots B_{39}$ (8 blocks):
   • These blocks map to lines $4 \dots 11$ with Tag 3.
   • During the access of $B_0 \dots B_7$ in this second pass, lines $4 \dots 11$ were updated to hold $B_0 \dots B_7$ (Tag 2).
   • The tags (3 vs 2) do not match. Each access will be a miss. These 8 blocks ($B_{32} \dots B_{39}$) are loaded, evicting $B_0 \dots B_7$.
   • Misses = 8.

Total misses for second access = $8 + 0 + 0 + 8 = 16$.

Total data cache misses = (Misses in first access) + (Misses in second access)
Total data cache misses = $40 + 16 = 56$.

The final answer is $\boxed{\text{56}}$.

The memory address is 16 bits.

1. Cache Parameters:

   • Block size: $B = 64$ bytes $\implies \text{Offset bits} = \log_2(64) = 6$.
   • Number of lines: $L = 32 \implies \text{Index bits} = \log_2(32) = 5$.
   • Tag bits: $16 - 5 - 6 = 5$.
   • Address format: [Tag (5 bits) | Index (5 bits) | Offset (6 bits)].

2. Array Memory Range:

   • Array size: $50 \times 50 = 2500$ bytes.
   • Starts at 1100H. Ends at 1100H + 2500 - 1 = 1AA3H.
   • The array spans memory addresses from 1100H to 1AA3H.

3. Identify Tags and Indices for Array Blocks:

   • Addresses 1100H to 17FFH: These addresses share Tag 00010 (decimal 2).
     • 1100H (00010 00100 000000) maps to (Tag 2, Index 4).
     • 17C0H (00010 11111 000000) maps to (Tag 2, Index 31).
   • Addresses 1800H to 1AA3H: These addresses share Tag 00011 (decimal 3).
     • 1800H (00011 00000 000000) maps to (Tag 3, Index 0).
     • 1A80H (00011 01010 000000) maps to (Tag 3, Index 10) (this block contains 1AA3H).

4. Cache State After First Pass:

   • During the first pass, blocks from 1100H to 17FFH (Tag 2) are loaded into lines 4 to 31.
   • Then, blocks from 1800H to 1AA3H (Tag 3) are loaded into lines 0 to 10.
   • For lines 4 to 10, the Tag 3 blocks overwrite the Tag 2 blocks.
   • For lines 0 to 3, Tag 3 blocks are loaded.
   • For lines 11 to 31, Tag 2 blocks remain.
   • Result: Lines 0-3 hold Tag 3; Lines 4-10 hold Tag 3; Lines 11-31 hold Tag 2.

5. Replacements in Second Pass:

   • The array is accessed again (1100H to 1AA3H).
   • Accessing Tag 2 blocks (1100H to 17FFH):
     • Lines 4 to 10 currently hold Tag 3. Accessing Tag 2 blocks for these lines results in a miss, and Tag 3 blocks are replaced by Tag 2 blocks.
     • Lines 11 to 31 currently hold Tag 2. Accessing Tag 2 blocks results in a hit. No replacement.
   • Accessing Tag 3 blocks (1800H to 1AA3H):
     • Lines 0 to 3 currently hold Tag 3. Accessing Tag 3 blocks results in a hit. No replacement.
     • Lines 4 to 10 now hold Tag 2 (from previous step in second pass). Accessing Tag 3 blocks for these lines results in a miss, and Tag 2 blocks are replaced by Tag 3 blocks.

6. Conclusion: The lines replaced during the second access are 4, 5, 6, 7, 8, 9, 10. This is "line 4 to line 10". Since this exact range is not an option, and option A ("line 4 to line 11") is the smallest provided range that includes all replaced lines, we select A. Line 11 is not replaced as it always holds Tag 2 and is only accessed by Tag 2 blocks within the array's range.

The final answer is $\boxed{A}$