Skip to content
GATETECH
Official PYQ · 2008Q71Memory Hierarchy: Cache, Main Memory and Secondary StorageMCQ1 mark

GATE CS 2008 Q71 — Memory Hierarchy: Cache, Main Memory and Secondary Storage

Explain with AI

Consider a machine with a 22-way set associative data cache of size 64Kbytes64\text{Kbytes} and block size 16bytes16\text{bytes}. The cache is managed using 32  bit32\;\text{bit} virtual addresses and the page size is 4Kbytes4\text{Kbytes}. A program to be run on this machine begins as follows:

double ARR[1024][1024];
int i, j;
/*Initialize array ARR to 0.0 */
for(i = 0; i < 1024; i++)
    for(j = 0; j < 1024; j++)
        ARR[i][j] = 0.0;

The size of double is 8Bytes8\text{Bytes}. Array ARR\text{ARR} is located in memory starting at the beginning of virtual page 0xFF000\textsf{0xFF000} and stored in row major order. The cache is initially empty and no pre-fetching is done. The only data memory references made by the program are those to array ARR\text{ARR}.

The total size of the tags in the cache directory is:

Choose one option
View worked solution

Answer: D

To find the total size of the tags in the cache directory, we first determine the cache parameters and the division of the 32-bit virtual address.

1. Cache Parameters

  • Cache Size: 64 KB=64×1024 bytes=216 bytes64\text{ KB} = 64 \times 1024\text{ bytes} = 2^{16}\text{ bytes}
  • Block Size: 16 bytes=24 bytes16\text{ bytes} = 2^4\text{ bytes}
  • Associativity: 22-way set associative

2. Number of Blocks and Sets

  • Total Cache Blocks (Lines): Number of Blocks=Cache SizeBlock Size=21624=212=4096 blocks\text{Number of Blocks} = \frac{\text{Cache Size}}{\text{Block Size}} = \frac{2^{16}}{2^4} = 2^{12} = 4096\text{ blocks}
  • Number of Sets: Number of Sets=Total BlocksAssociativity=40962=2048=211 sets\text{Number of Sets} = \frac{\text{Total Blocks}}{\text{Associativity}} = \frac{4096}{2} = 2048 = 2^{11}\text{ sets}

3. Address Fields

The 32-bit virtual address is divided into three fields:

  • Block Offset: log⁡2(16)=4 bits\log_2(16) = 4\text{ bits}
  • Set Index: log⁡2(2048)=11 bits\log_2(2048) = 11\text{ bits}
  • Tag: Tag bits=32−(Index bits+Offset bits)=32−(11+4)=17 bits\text{Tag bits} = 32 - (\text{Index bits} + \text{Offset bits}) = 32 - (11 + 4) = 17\text{ bits}

4. Total Tag Directory Size

Each of the 40964096 blocks in the cache directory must store its corresponding tag.

Total Tag Size=Total Blocks×Tag bits=4096×17 bits=69,632 bits\text{Total Tag Size} = \text{Total Blocks} \times \text{Tag bits} = 4096 \times 17\text{ bits} = 69,632\text{ bits}

Converting this to Kbits (1 Kbit=1024 bits1\text{ Kbit} = 1024\text{ bits}):

Total Tag Size=69,6321024 Kbits=68 Kbits\text{Total Tag Size} = \frac{69,632}{1024}\text{ Kbits} = 68\text{ Kbits}

Therefore, the correct option is D.

Free practice · Your answers on this page are not saved.

Published
Report a correction
Keep exploringMore Memory Hierarchy: Cache, Main Memory and Secondary Storage questions