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

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

Explain with AI

Consider a machine with a 22-way set associative data cache of size 6464 Kbytes and block size 1616 bytes. The cache is managed using 3232 bit virtual addresses and the page size is 44 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 88 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 cache hit ratio for this initialization loop is:

Choose one option
View worked solution

Answer: C

To find the cache hit ratio for the initialization loop, we analyze the memory access pattern of the array elements.

1. Cache and Element Parameters

  • Block size: 16 bytes16\text{ bytes}
  • Element size (double): 8 bytes8\text{ bytes}
  • Elements per block: Since each block is 16 bytes16\text{ bytes} and each double is 8 bytes8\text{ bytes}, each cache block can hold exactly: 16 bytes8 bytes=2 elements\frac{16\text{ bytes}}{8\text{ bytes}} = 2\text{ elements}

2. Array Alignment and Access Pattern

  • The array ARR starts at the beginning of a virtual page (0xFF000), which is page-aligned (4 KB4\text{ KB} boundary). Since 4 KB4\text{ KB} is a multiple of the block size (16 bytes16\text{ bytes}), the array is perfectly aligned with the cache blocks.
  • The loop accesses the array sequentially in row-major order: ARR[0][0],ARR[0][1],ARR[0][2],ARR[0][3],…\text{ARR}[0][0], \text{ARR}[0][1], \text{ARR}[0][2], \text{ARR}[0][3], \dots

3. Hit/Miss Analysis

Let's trace the sequential accesses for the first few elements:

  1. Access ARR[0][0]: This is a Miss. The cache block containing both ARR[0][0] and ARR[0][1] is fetched into the cache.
  2. Access ARR[0][1]: This is a Hit, as it resides in the same block that was just loaded.
  3. Access ARR[0][2]: This is a Miss. The cache block containing ARR[0][2] and ARR[0][3] is fetched.
  4. Access ARR[0][3]: This is a Hit.

Since the access is strictly sequential, the second element in each block is always accessed immediately after the first. There are no intervening accesses to cause conflict or capacity evictions before the second element is read.

Thus, for every 22 consecutive accesses, there is exactly 11 miss and 11 hit.

Hit Ratio=12=50%\text{Hit Ratio} = \frac{1}{2} = 50\%

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