8.9k views

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$ x $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?

1. $48$
2. $50$
3. $56$
4. $59$

edited | 8.9k views
+1

If someone like me wondered why first block is in 4th block, this is why.

1100 H = (0001 0001 0000 0000)b excluding lower 6 bits for offset, we get 0001 0001 00 bits for cache block which is the 4th block.

Source: Arjun sir answer here: https://gateoverflow.in/43511/gate2007-81

Bits used to represent the address = $\log_2{2^{16}} = 16$

Each cache line size $=64$ bytes; means offset requires $6\text{-bits}$

Total number of lines in cache $= 32;$ means line # requires $5\text{-bits}$

So, tag bits $= 16- 6-5=5$

We have a $2\text{D-array}$ each of its element is of size $=1\text{ Byte};$
Total size of this array $= 50 \times 50 \times 1\text{ Byte}=2500\text{ Bytes}$

So, total number of lines it will require to get contain in cache

$=\dfrac{2500B}{64B} = 39.0625 \approx 40$

Starting address of array $= 1100H = 00010 \ 00100 \ 000000$
The group of bits in middle represents Cache Line number $\implies$ array starts from cache line number $4$,
We require $40$ cache lines to hold all array elements, but we have only $32$ cache lines

Lets group/partition our $2500$ array elements in those $40$ array lines, we call this first array line as $A_0$ which will have $64$ of its elements.

This line(group of $64$ elements) of array will be mapped to cache line number $4$ as found by analysis of starting address of array above.

This all means that among those $40$ array lines some array lines will be mapped to same cache line, coz there are just $32$ cache lines but $40$ of array lines.

This is how mapping is:
$\begin{matrix} 0& A_{28} & \\ 1& A_{29} & \\ 2& A_{30} & \\ 3& A_{31} & \\ 4& A_{0} & A_{32} \\ 5& A_{1} & A_{33} \\ 6& A_{2} & A_{34} \\ 7& A_{3} & A_{35} \\ 8& A_{4} & A_{36} \\ 9& A_{5} & A_{37} \\ 10& A_{6} & A_{38} \\ 11& A_{7} & A_{39} \\ 12& A_{8} & \\ \vdots\\ 30& A_{26} & \\ 31& A_{27} & \end{matrix}$

So, if we access complete array twice we get $=32+8+8+8 = 56$ miss because only $8$ lines from cache line number $4$ to $11$ are miss operation, rest are Hits(not counted) or Compulsory misses(first 32).

by Boss (30.7k points)
edited by
+22

0
I have doubt when after placing into A39 into 11 block then A1 will be miss where will be the A1 placed will it be placed in 4 block or 12 block cache??? if it is the case 12 block it will having more miss than 56 if it is placed in 4 block then it will 56.... is there any replacement algoritham to be followed here??? plz help me i am confused....
0
+9

0
too good an explanation. (y)
0
i have a doubt ... After B39 ... why we put b0 at location 4 why not from 12 ?
+6
@anup, it is direct mapped cache, for an index we will have fixed location in the cache.
+1
Thank you so much. Precise and clear explanation. I wanted to upvote this infinite times.
+1
Why we have taken size of each element of an array as 1Byte???? As there is no information about the size of each element in array is given in question
+1
it is mentioned as array of $bytes$
0
Awesome Explanation
0
Please explain me the part after you get the total number of lines in the cache to be 40.
+1

I think for 1100 hexa decimal number is equal to 0001 0001 0000 0000, of binary number

by rearranging it ac cording to the problem then, it will  be 00010 00100 000000

0

Please explain me the part after you get the total number of lines in the cache to be 40.😓

0

@Gupta731, after finding number of lines in cache we are just finding the starting address of array as given in question 1100H means 00010 00100 00000 so we already determined that first 6 bit represent the offset next 5 bits represent the cache line index and last 5 bits represent tag bits.

0
And the mapping part, how cache miss is calculated.
0

Starting address of array =1100H=00010 00100 000000=1100H=00010 00100 000000
The group of bits in middle represents Cache Line number ⟹⟹ array starts from cache line number 44,

Can someone tell me what is the significance of the tag bits here? i.e., 00010.

0
Great Explanation!
0

A Little Help:

The total number of lines required = 40. Then,

 Tag Bits Cache Line Number Block Offset

This Comes out to be:

 5 5 6

dividing the Starting Address by the number of bits shown above table:

 00010 (5 bits) 00100 (5 bits) 000000 (6 bits)

Since Middle bits in the table are cache line number. Hence, A0 comes at line 4 in the above explanation.

The significance of tag bits is nothing but to divide the starting address.

$2^{16} = 64$ KB main memory is mapped to 32 lines of 64 bytes. So, number of offset bits = 6 (to identify a byte in a line) and number of indexing bits = 5 (to identify the line).

Size of array = 50* 50 = 2500 B. If array is stored in row-major order (first row, second-row..), and if elements are also accessed in row-major order (or stored and accessed in column-major order), for the first 64 accesses, there will be only 1 cache miss, and for 2500 accesses, there will be 2500/64 = 40 cache misses during the first iteration.

We have 5 index bits and 6 offset bits. So, for 211 (5 + 6 = 11) continuous memory addresses there wont be any cache conflicts as the least significant bits are offset bits followed by index bits.

So, number of array elements that can be accessed without cache conflict = 2048 (as element size is a byte). The next 452 elements conflict with the first 452 elements. This means 452/64 = 8 cache blocks are replaced. (We used ceil, as even if one element from a new block is accessed, the whole block must be fetched).

So, during second iteration we incur misses for the first 8 cache blocks as well as for the last 8 cache blocks. So, total data cache misses across 2 iterations = 40 + 8 + 8 = 56.

by Veteran (424k points)
+9
I am getting 40 miss for whole 2500 elements in first iteration .

Now again in second iteration ie for 2500 elements again , majority of data would be already in cache right ?

But in first iteration after filling the cache with 2048 elements we had replaced 8 block to accomadate 452 bytes , But these 452 byte are last byte right ? so in second iteration what we actually wat is the first 452 byte (that is 8 block ) and then again for last 452 byte ( again 8 block need to be replaced )

so miss = 8+8+40=56 miss

Am i right ???
0
Exactly. Nice informal explanation :)
0
In this question why there is 1 cache miss for the first 64 bytes of array ..Plz explain.....
+1
Initial access to the array will be a cache miss. Now, during a cache miss we go to a memory block fetch the requested content and this gets stored in the cache and also given to the CPU. But this doesn't happen as simple as this.

As we know access from disk to memory happens in units of page. Similarly, access from memory to cache happens in units of cache lines. This is because memory access is slow and so while accessing we take the maximum possible amount of data together assuming they will be needed in near by future (spatial locality).

In the given question cache line size is 64 bytes. So, for the first access to a cache line (be it any element corresponding to the memory in that cache line), the whole cache line is filled from memory. Since, we have a byte array and so when the first element is accessed, we are filling the next 63 elements also in the cache. So, 1 cache miss for 64 CONSECUTIVE accesses.
0

sorry for asking silly things but i hv doubt so m asking y 16 y not 6KB?16 KB main memory is mapped to 32 lines of 64 bytes. So, number of offset bits = 6 and number of indexing bits = 5.

We have 5 index bits   so shd  5 tag bcz 16-5-6=5 and 6 tag bits. So, for 211 continuous accesses there wont be any cache conflicts.how??

So, number of array elements that can be accessed without cache conflict = 2048. The next 452 elements conflict with the first 452 elements. This means 452/64 = 8 cache blocks are replaced.  how???(We used ceil, as even if one element from a new block is accessed, the whole block must be fetched).

So, during second iteration we incur misses for the first 8 cache blocks as well as for the last 8 cache blocks. So, total data cache misses across 2 iterations = 40 + 8 + 8 = 56.

0
There were some mistakes, is it clear now?
0

how this????the next 452 elements conflict with the first 452 elements. This means 452/64 = 8 cache blocks are replaced.

0
There are only 64 bytes in a set and we have 32 sets. So, for 32*64 = 2048 B of CONTIGUOUS memory accesses, we won't have a cache conflict as each of them will go to a distinct location in cache. After this the CYCLE repeats.  The next location after 2048, will go to the first location and removes that entry- as we are having direct mapped cache. Like wise for the next 452 elements.
0
@arjun sir last 8 cache misses for what..?
We do not care what is the starting address to solve this question.

Total 50x50 = 2500 elements.
One block can hold 64 elements.
2500/64 = 39.06  so  40 blocks are needed to hold them.

So for initial 40 blocks, there will be 40 misses.

When the second iteration starts, (9 to 40 of array are present) in 0 to 32 blocks.
Now for the first 8, there will be 8 misses.

It is direct mapped cache, so respective blocks with same reminder will be replaced
The first 8 blocks of array will replace the last 8 blocks( Since last 8 have same reminder as 1st 8 elements.  33 mod 32 =1, 34 mod 32 = 2 so on)

Again after 32 blocks, (33 to 40 will replace  1 to 8)  8 miss.

Total 40+8+8 = 56 misses.
by Boss (12.2k points)
edited by
0
0
Note that, it is a linked question. So to find the answer of 2nd one, you have to draw that figure given in best ans.
But just to answer this question, it is straight forward.
0

Size of main memory=216 bytes

Size of cache=32*64 Bytes

=2 11 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/

by (169 points)
0
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

### SIMPLIFIED VERSION OF THIS QUESTION:

There are 40 blocks in the Main Memory, that are to be "directly mapped" to a cache of 32 lines., twice. If the first block maps to the fourth line, calculate the cache misses.

For the first 32 blocks (block 0 - 31) — 32 misses.

For the next 8 blocks (block 32 - 39), we'll have to replace block 0 - 7 — 8 misses.

Now, in the second iteration, for the first 8 blocks (block 0 - 7), we'll have to replace block 32 - 39 — 8 misses.

Towards the end, we find out block 32 - 39 aren't present. So, we replace block 0 - 7 with them. — 8 misses.

So, total = 56 cache misses.

PS: All this replace, and counter-replace action is going on on blocks 0 - 7 (or 32 - 39), which are present at line no. 4 to 11. (b mod l)

by Active (1.7k points)
+1 vote

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

by Active (1.2k points)

PIC1-

PIC2-

by Junior (985 points)

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

by Active (1.2k points)