GATE Overflow Test Series | Computer Organization and Architecture | Test 1 | Question: 21

Question

In a C program, an array is declared as $\text{double arr[8192]}$. The starting address of the array is $\textsf{0x}00000000$. This program is run on a computer that has a $4$-way set associative cache of size $32$ Kbytes, with block size of $64$ Bytes. If the program accesses the elements of the array one by one in order from first element to last and then one more time in reverse order from the last element to the first element, total number of cache misses will be _______

(Assume that the data cache is initially empty and that no other data or instruction accesses are to be considered.)

• A. $2048$
• B. $1536$
• C. $256$
• D. $1024$

Answer 1

Number of array elements in a block = $\frac{64}{8}=8$
    
Number of cache blocks = $\frac{2^{15}}{2^6}=512$
    
Number of cache blocks needed for the array = $\frac{2^{13}}{2^3}=1024$
    
So, after every $512$ block accesses, we will need to replace the cache lines from cache.
    
During the forward access, we will have $1024$ compulsory misses as all $1024$ block accesses are their first accesses.
    
During the reverse access, the first $512$ block accesses will be a hit in the case.
    
Remaining $1024 - 512 = 512$ block accesses will cause a miss.
    
So, total number of cache misses $ = 1024 + 512 = 1536$

Comments

This is such a beautiful question

as given address start from 0*00000000 we can place the array elements from address 0 to full capacity of cache 

i hope this helps you to understand 

 

 

---

@gatecse   @Nikhil_dhama

In case of fully Associative cache :

Min no of Cache Misses will be: 1536

Maximum no of cache misses will be 2043

By using LRU replacement policy??

---

@lalitver10

ig , LRU will work same as FIFO here.