GATE CSE 2007 | Question: 80

Question

Consider a machine with a byte addressable main memory of $2^{16}$ bytes. Assume that a direct mapped data cache consisting of $32$ lines of $64$ bytes each is used in the system. A $50 \times 50$ two-dimensional array of bytes is stored in the main memory starting from memory location $1100H$. Assume that the data cache is initially empty. The complete array is accessed twice. Assume that the contents of the data cache do not change in between the two accesses. 

How many data misses will occur in total?

• A. $48$
• B. $50$
• C. $56$
• D. $59$

Comments

in this question, it does not matter where the array is stored in the memory right??

---

GO to the Root of Concept: Video Explanation with timestamp: Many Questions on Direct Mapped Cache Memory From Standard Universities | With NOTES | COA

---

Another Approach :

Total Number elements in Array[50][50] = 50*50 = 2500 byte 

Total Number Blocks ( lines ) in cache = 32 ( Cache Line number given 5 bit = 2^5 = 32)

Total Block need to store Array[50][50] = Ceil(2500/64) = 40 ( Block SIze = 64 bytes ) 

Overlapping Blocks = 40 – 32 = 8 blocks 

Now for time access = All blocks from the array is Miss so for first time = 40 miss 

Now for second time miss will happen in overlapping blocks = 8*2 = 16 

Total miss = 40 + 16 = 56 miss 

Same you go for the n round = 1 * ( 40 ) + (n-1) * ( number of overlapping block ) * 2 

 

Answer 1

 Size of main memory=2¹⁶ bytes

Size of cache=32*64 Bytes

=2 ¹¹ Bytes

Size of array=2500 Bytes

Array is stored in main memory but cache will be empty

Size of cache=2048 Bytes

So number of page faults=2500-2048=452

Complete array will be access twice

So for second access no. of total page faults=452*2=904

So total page faults=452+904=1356

So data cache misses will be 56

So (C) is correct option

http://www.geeksforgeeks.org/gate-gate-cs-2007-question-80/

Comments

does the answer 56 here depend on row major or column major access?if yes then What if we acces in fashion of column major order?

Does the first block consist of both a00 and a10 as there is extra space of 14 elements in block 1.

@Arjun sir

Answer 2

1 cache block contains maximum of 64 elements

which means there will be 1 miss in every 64 references

We have Total 2500 (50*50) elements.

Since 1 element = 1 Byte

 

In first iteration :

Maximum capacity of elements in cache = 32 * 64 = 2048 elements = 2048 references (compulsory miss )

That means 2500-2048=452 elements will be left , when the cache size gets full

these 452 references will again replace 452 elements in the cache. ( conflict miss )

 

 

In second iteration :

452 elements will again be replaced as they were the last 452 elements of the array. ( conflict miss )

In between for 1144 elements there will not be any conflict misses

And Finally the last 452 elements will again  require the replacement of first 452 elements. ( conflict miss )

 

So total misses = 2048/64 + ceil(452/64) + ceil(452/64) + ceil(452/64) = 56 misses

 

Answer 3

PIC1-

PIC2-

 

Answer 4

The image is self explanatory

I have drawn 50*50 array which is stored in contigious fashion.

Now calculate how much data 1 line can store which is 64B 

Now 2500/64 = 39.05 so 40 blocks will be needed.