The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+14 votes
1.4k 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 (103k points)
edited by | 1.4k 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 (10.9k 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 ?
+1 vote

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 (57 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

40,840 questions
47,503 answers
145,762 comments
62,260 users