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

Consider a machine with a $2$-way set associative data cache of size $64$ $Kbytes$ and block size $16$ $bytes$. The cache is managed using $32$ $bit$ virtual addresses and the page size is $4$ $Kbytes$. A program to be run on this machine begins as follows:

double ARR[1024][1024];
int i, j;
/*Initialize array ARR to 0.0 */
for(i = 0; i < 1024; i++)
    for(j = 0; j < 1024; j++)
        ARR[i][j] = 0.0;


The size of double is 8 bytes. Array $ARR$ is located in memory starting at the beginning of virtual page $0xFF000$ and stored in row major order. The cache is initially empty and no pre-fetching is done. The only data memory references made by the program are those to array $ARR$.

The cache hit ratio for this initialization loop is:

  1. $0$%
  2. $25$%
  3. $50$%
  4. $75$%
asked in CO & Architecture by Veteran (112k points)
edited by | 1.6k views

2 Answers

+17 votes
Best answer
Block size $=16B$ and one element$=8B.$
So, in one block $2$ element will be stored.

For $1024\times 1024$ element num of block required $=\dfrac{1024\times 1024}{2} =2^{19}$ blocks required.

In one block the first element will be a miss and second one is hit(since we are transferring two unit at a time)

$\Rightarrow \text{hit ratio}=\dfrac{\text{Total hit}}{\text{Total reference}}$

               $=\dfrac{2^{19}}{2^{20}}$

               $=\dfrac{1}{2}=0.5$

               $=0.5\times 100=50\%$
answered by Boss (11k points)
edited by
0
how to find the number of misses in this problem
0
(1-HIT RATIO) OR (TOTAL MISS/TOTAL REFERENCE)
0
i want miss rate??? is it (1024 x 1024)/2?? please explain
0
RATE MEANS PER UNIT TIME

IF U WANT MISS RATE THEN IT WILL BE NUMBER OF MISS PER UNIT ACCESS

THAT IS 1/2 HERE(IN ONE BLOCK )
0
ok.thanks so,total number of misses =(2^12)/2..=2^11...pls correct me if i am wrong,total number of misses=2048 pls verify.
0
JUST THINK

MISS RATE IS A TIME = AT WHAT RATE WE HAVE A MISS(THAT MEANS PER 100 INSTRUCTION,,1000 INSTRUCTION......)

                                  = SIMPLY MISS RATIO*MEMORY ACCESS PER INSTRUCTION

AND HERE WE CAN'T CALCULATE MEMORY ACCESS PER INSTRUCTION(COZ TO ACCESS ONE BYTE THERE IS NO TIME BOUND)
0
Ok thanks buddy...
0
for each block reference we have 1 hit and 1 miss
total no of blocks required = 2^19
no of miss = no of hit = 2^19
0
yes
0
It is 2 way associative, why we are ignoring it on question?
0
we need 2^19 blocks for array but we have 2^12 blocks only...right ?? so how 2^20 comes and also please elaborate your answer ..?
0
we are not ignoring it in the question, but it doesn't matter. Since one block is 16 bytes and each array element takes 8 bytes, and we are fetching the elements row wise and default storage scheme is also row wise, we will get one hit out of 2 elements accessed. Hence 50% hit.
0

@  sushmita Boss  

i understand 50% by thinking only but in answer given above how it is done that i want to know..?

0
Are we transfering 2 units at a time because its 2 way associative ?
0
doesnt the 2 way assosciativity play any role here?
0
@arjun sir

This explanation is awesome and I'm clear how it worked for this question.

However I have a general doubt regarding virtually addressed caches. When CPU generates the virtual address 0XFF000 000, cache has to check whether the MM block corresponding to this VA is present in cache or not. So to performs this check, is it the same way as it's done for physically addressed cache, by breaking the address into tag bit, block offset and word offset then comparing tag bits for corresponding block? Is this process same for all Pipt cache, Vivt cache, Vipt cache?

Help would be really appreciated. Thanks!

(P-physically, v- virtually, i- indexed, t- tagged)
+2 votes

Given cache block size = 16B, 1 element size in array = 8B (size of Double =8B). Therefore 1Block contain 2 elements

     Total elements = 1024 x1024 =2^20
     each time 1 block ( 2 elements) stored in to  cache, so 1st element is compulsory miss and when we access  2nd element           that will be hit because it is already present in cache.

     Therefore each time 1 miss 1 hit occur, For complete 2^20 elements 2^19 misses and 2^19 Hits will occur
      Hit ratio = 2^19/2^20 = 0.5

                    = 0.5 x 100 = 50%

answered by (331 points)
Answer:

Related questions



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

46,734 questions
51,201 answers
176,305 comments
66,556 users