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

GATE CS 2008 Q72 — 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}.

Which of the following array elements have the same cache index as ARR[0][0]\text{ARR[0][0]}?

Choose one option
View worked solution

Answer: B

To find which element has the same cache index as ARR[0][0]\text{ARR[0][0]}, we first determine the cache parameters:

  • Cache Size: 64 KB=216 bytes64\text{ KB} = 2^{16}\text{ bytes}
  • Block Size: 16 bytes=24 bytes16\text{ bytes} = 2^4\text{ bytes}
  • Associativity: 22-way set associative
  • Number of Sets: 64 KB2×16 B=2048=211\frac{64\text{ KB}}{2 \times 16\text{ B}} = 2048 = 2^{11} sets

The cache index is determined by the 1111 set index bits. For any two memory addresses to map to the same cache index, the difference between their byte addresses must be a multiple of:

Block Size×Number of Sets=16×2048=32768 bytes\text{Block Size} \times \text{Number of Sets} = 16 \times 2048 = 32768\text{ bytes}

Since each double element is 88 bytes, the address difference between ARR[i][j]\text{ARR[i][j]} and ARR[0][0]\text{ARR[0][0]} in row-major order is:

Δ=(i×1024+j)×8 bytes\Delta = (i \times 1024 + j) \times 8\text{ bytes}

For this difference to be a multiple of 3276832768 bytes:

(i×1024+j)×8=k×32768  ⟹  i×1024+j=k×4096(where k∈Z)(i \times 1024 + j) \times 8 = k \times 32768 \implies i \times 1024 + j = k \times 4096 \quad (\text{where } k \in \mathbb{Z})

Let us test the given options:

  • Option A: ARR[0][4]  ⟹  0×1024+4=4\text{ARR[0][4]} \implies 0 \times 1024 + 4 = 4 (not a multiple of 40964096)
  • Option B: ARR[4][0]  ⟹  4×1024+0=4096\text{ARR[4][0]} \implies 4 \times 1024 + 0 = 4096 (which is exactly 1×40961 \times 4096)
  • Option C: ARR[0][5]  ⟹  5\text{ARR[0][5]} \implies 5 (not a multiple of 40964096)
  • Option D: ARR[5][0]  ⟹  5120\text{ARR[5][0]} \implies 5120 (not a multiple of 40964096)

Thus, ARR[4][0]\text{ARR[4][0]} maps to the exact same cache index as ARR[0][0]\text{ARR[0][0]}.

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