how to find the number of misses in this problem

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+13 votes

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

- 0%
- 25%
- 50%
- 75%

+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\%$

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\%$

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 )

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)

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

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

total no of blocks required = 2^19

no of miss = no of hit = 2^19

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

- All categories
- General Aptitude 1.3k
- Engineering Mathematics 5.1k
- Digital Logic 2k
- Programming & DS 3.7k
- Algorithms 3.1k
- Theory of Computation 3.9k
- Compiler Design 1.5k
- Databases 2.9k
- CO & Architecture 2.5k
- Computer Networks 2.9k
- Non GATE 1k
- Others 1.3k
- Admissions 446
- Exam Queries 428
- Tier 1 Placement Questions 17
- Job Queries 55
- Projects 8

35,485 questions

42,741 answers

121,445 comments

42,135 users