The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+27 votes
4.9k views

Consider a machine with a byte addressable main memory of 216 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
asked in CO & Architecture by Veteran (69k points)
retagged by | 4.9k views

5 Answers

+90 votes
Best answer

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
coz only $8$ lines from cache line number $4$ to $11$ are miss operation,
rest are Hits(not counted) or Compulsory misses(first 32).

Hence,answer = option C
 

answered by Veteran (31k points)
edited by

+infinity upvotes yes

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....
any body answer this asked part

@Prashanth kumar

I didn't fully understand ur question , but i think this is what you wanted to know .

In 1st Iteration

line4--- A0
.
.
line 31 -- A27
line0-- A28
..
..
line3 -- A31

This is the first 32 Misses..
line 4 to 11 we will have 8 more misses

2nd Iteration

line 0 to 3 and line 12 to31 data already present . So no miss.
line 4 now contain A32 but we require A0
line 4 to line 11 we need A0 toA7 which causes 8 miss

after that we require A32 to brought back to line 4 .( A32 to A39 should be brought back to line 0 to line 4 ) which causes 8 miss
SO we will have
32+8 (1st iteration ) +

8+8 (2nd iteration ) = 56 misses

 

too good an explanation. (y)
i have a doubt ... After B39 ... why we put b0 at location 4 why not from 12 ?
@anup, it is direct mapped cache, for an index we will have fixed location in the cache.
Thank you so much. Precise and clear explanation. I wanted to upvote this infinite times.
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
it is mentioned as array of $bytes$
Awesome Explanation
+24 votes

$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.

 

answered by Veteran (346k points)
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 ???
Exactly. Nice informal explanation :)
In this question why there is 1 cache miss for the first 64 bytes of array ..Plz explain.....
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.

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.

There were some mistakes, is it clear now?

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

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.
+8 votes
Simple way to answer this.
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.
answered by Veteran (10.3k points)
edited by
anyone please explain this
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.
@ahwan please explain the solution!
+2 votes

 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/

answered by (147 points)
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
–2 votes
80-c ,because a miss is related to cache line.Initially all lines are empty so 32.Then 2500(50×50,size of array)-2048(32×64,size of cache)=452.this requires 7.0625 cachelines so another 8 misses then 2nd time 8 and 8 =16 .net = 56.

81-c , everytime this first 8 line 0-7 are being replaced and a total of 3 times they've been replaced.
answered by Loyal (3.3k points)

 WRONG!! 

Answer:


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

33,687 questions
40,230 answers
114,269 comments
38,798 users