GATE Overflow Test Series | Data Structures | Test 1 | Question: 30

Question

Consider the following two structure declarations and their initialization in C language.

struct node1
{
    int a1, a2;
}mynode1[10000];

for(i = 0; i < 10000; i++)
{
    mynode1[i].a1 = rand();
    mynode1[i].a2 = rand();
}
struct node2
{
    int a1[10000], a2[10000];
}mynode2;

for(i = 0; i < 10000; i++)
{
    mynode2.a1[i] = rand();
    mynode2.a2[i] = rand();
}

Assume size of integer as $4$ bytes, a $64$ byte cache line, and a $32 KB$ fully associative cache implementation with all lines invalidated initially. If $n_1$ and $n_2$ denote the number of cache misses during the initializations of $mynode1$ and $mynode2$ respectively and if both $mynode1$ and $mynode2$ are aligned to cache lines with no other intervening cache accesses, the absolute value of $(n_1 - n_2) = $ _____

Answer 1

This can be solved easily by considering the cache line utilization. i.e., when a $64$ byte cache line is fetched, what percentage of this is accessed before this gets replaced.

Here, each array is of size $10000$ and so will need $40KB$ memory since size of int is 4 bytes. Since size of cache is $32$ KB, it is clear that there will be cache line replacements. So, lets see the cache line utilizations for mynode1 and mynode2.

For mynode1, the accesses are sequential and it is clear that cache line utilization is $100%.$

For mynode2, in one iteration, cache line for a1 and a2 are accessed. These two cache lines won't conflict -- because we are having a fully associative cache and there are no intervening cache line accesses. (In a fully associative cache of size 32 KB and 64B block size, a cache replacement happens only after $\dfrac{32 \times 2^{10}}{2^6} = 512$ unique cache line accesses).

Now, in the next iteration, the next elements of a1 and a2 are accessed and there wont be a cache miss. This way for mynode2 too the cache line utilization is $100%.$

Thus $n_1 - n_2 = 0.$

Answer 2

Mynode1 is an array which contains two integer each.

Mynode1[0] contains a1,a2

Mynode1[1] contains a1,a2

Mynode1[2] contains a1,a2………..

So, 1^st miss occur while accessing Mynode[0].a1 & because of this miss a cache block will be fetched and each cache block can hole 8 Mynode array elements as each Mynode array element has size of 8 Bytes & Cache line size is 64 Bytes.So due to 1^st miss we’ll have Mynode[0] to Mynode[7]. similarly for next miss we’ll have Mynode[8] to Mynode[15].

So Total number of misses for Mynode array is = $\frac{10000}{8}$ = 1250 = $n_{1}$

Now Mynode2 is a single variable which contains two different array a1 & a2 of size 10,000

now, a1[0] to a1[15] will come

a2[0] to a2[15], a1[16] to a1[31], a2[16] to a2[31] …………….

Because of Fully associative cache any cache block can be replaced.

So, cache miss occur for both array = $\frac{10000}{16}$ * 2  = 1250 = $n_{2}$

$n_{1}$ – $n_{2}$ = 0