GATE2002-10

Question

In a C program, an array is declared as $\text{float} \ A[2048]$. Each array element is $4 \ \text{Bytes}$ in size, and the starting address of the array is $0x00000000$. This program is run on a computer that has a direct mapped data cache of size $8  \ \text{Kbytes}$, with block (line) size of $16 \ \text{Bytes}$.

• A. Which elements of the array conflict with element $A[0]$ in the data cache? Justify your answer briefly.
• B. If the program accesses the elements of this array one by one in reverse order i.e., starting with the last element and ending with the first element,  how many data cache misses would occur? Justify your answer briefly. Assume that the data cache is initially empty and that no other data or instruction accesses are to be considered.

Comments

Suppose the question mentioned array having 4096 elements.Then the  2049^th element would conflict $A[0]$ right?

---

Question say each element is access one by one means there . will be 2048 miss instead of 512.Now if u consider block by blck access it should be 512. Correct me if I am wrong.

---

When we fetch element from main memory into the cache we always do that in blocks by considering the spatial locality of reference,so there will be 512 miss.

---

@Hitesh Yes if array is having 4096 elements then 2049th element will conflict with the  A[0] as 2049%2049=0.

---

@

Hitesh Junior

there will not be a single element that will conflict complete block of elements will conflict with that that is why in question part a elements is written

---

@Cristine i have a silly doubt , that if there 4096 elements,then when A[0] would be fetched it would bring A[1],A[2],A[3] also in cache right,now when we bring A[2048] it will bring A[2049],A[2050],A[2051] with itself.so how do we say that  A[0] conflicting with A[2048] or with all  A[2048],A[2049],A[2050],A[2051]?

---

@codingo1234 with all A[2048],A[2049],A[2050],A[2051]

Answer 1

• A. Data cache size $= 8 \ KB.$
  
  Block line size $= 16 \ B.$
  
  Since each array element occupies $4 \ B,$ four consecutive array elements occupy a block line (elements are aligned as starting address is $0$ )
  
  Number of cache blocks $=\dfrac{8 \ KB}{16 \ B}= 512.$
  Number of cache blocks needed for the array $=\dfrac{2048}{4}=512.$
  So, all the array elements has its own cache block and there is no collision.
  
  We can also explain this with respect to array address.
  Starting address is $\text{0x00000000} = 0_b0000\ldots0 \text{(32 0's)}.$
  Ending address is $\text{0x00001FFF} = 0_b0000\ldots 01111111111111 (4\times 2048
  = 8192 \text{ locations), $0 - 8191$}$.
  
  Here, the last $4\text{ bits}$ are used as OFFSET bits and the next $9$ bits are used as SET bits. So, since the ending address is not extending beyond these $9\text{ bits},$ all cache accesses are to diff sets.
   
• B. If the last element is accessed first, its cache block is fetched. (which should contain the previous $3$ elements of the array also since each cache block hold $4$ elements of array and $2048$ is and exact multiple of $4$ ). Thus, for every $4$ accesses, we will have a cache miss $\Rightarrow$ for $2048$ accesses we will have $512$ cache misses. (This would be same even if we access array in forward order).

Comments

Ending address is 0x00001000 ?​

---

corrected :)

---

part (a) -  although we have 512 cache blocks to store the array (4 contiguous elements in 1 cache block )
but since it is DIRECT MAPPED cache so we will apply { K mod c = i  ; where K is main memory block no  , c is no. of cache blocks , i is cache block no.} then there will be so many locations which will be mapped to same cache block line and hence misses will occur as a result of which A[0] data will get conflict........plz correct if i am wrong...!!

---

For each block mapping block will be different try this.

---

@Arjun sir, It might be a silly doubt but still please help... Isn't the whole array being stored in the 8KB cache itself? If yes then there shouldn't be any miss at all, isn't it?

---

same doubt

---

The cache initially is empty so to fetch the array elements misses will occur.

for ( int i = 0; i < 2048; i++)

      printf("%d ",arr[ i ]);

So to loop over the whole array once compulsory misses will occur. But if again I loop over the array then there would be 0 misses since the whole array can get fit perfectly in the cache.

---

If the last element is accessed first, its cache block is fetched. (which should
contain the previous 33 elements of the array also since each cache block
hold 44 elements of array and 2048 is and exact multiple of 44 ). Thus,
for every 44 accesses, we will have a cache miss ⇒⇒ for 2048
accesses we will have 512 cache misses. (This would be same even if we
access array in forward order).

@Tuhin Dutta Iam not able to relate this with the above explanation given by arjun Sir. please help  

---

Please explain me the B part

---

Each block size is 16 bytes and total 512 blocks so when A[2047] is accessed (miss) whole block is available so there will be no misses for A[2046], A[2045], A[2044] then again a miss for A[2043] then for A[2039]

so total 512 misses

---

@tusharp

Ending address is 0x00001FFF = 0b0000…0 1111 1111 1111(4×2048=8192 locations).

should'nt final address be 0x00000FFF?
 

---

YES

---

0x00001FFF is correct. Cache size is 8KB. so total addressable memory - 2^13 which is 0-8191 locations

---

So, all the array elements has its own cache block and there is no collision.

Since the array occupies continuous space, there should be 4 elements in a single block.

How is the above-quoted sentence justified??