The Gateway to Computer Science Excellence
+8 votes
1.3k views

Consider an array A[100] and each element occupies 4 word. A 32 word cache is used and divided into 8 word blocks. What is the hit ratio for the following statement.

for(i=0;i<100;i++)
  A[i]=A[i]+10

What mapping is going to be used in the Solution ?

in CO and Architecture by Boss (45.4k points)
retagged by | 1.3k views

4 Answers

+9 votes
Best answer

According to the question, a block can have 2 elements. And each element has size of 4 words.

Now, the looping is given as follows ==>

for(i=0;i<100;i++)
  A[i]=A[i]+10

This means that for each value of i, we have to read the element first,and +10 shows that after reading , we have to add this constant value to the array element .

Hence, we will consider read and write cases now. Also, of the question was about just reading and no updating , then would have considered only read cases .

Now, first iteration will read first A[0] value, which is not there in the cache ( we have assumed cache to be initially empty), it will be a cache miss . 

Now, A[0] and A[1] cache block will be brought to the cache , and now write reference for A[0] is a hit, whereas, for A[1] ,both read and write access will be hits .

Hence, for a particular cache block , we have 1 miss and 3 hits .

Hence, hit ratio = 75% ..

by Veteran (50.9k points)
selected by
0

@kapil your explanation is great but clear my this doubt

a/c to the problem statement we can have 2 element in a cache block .....thats over now ;ets come to this statement    for(i=0;i<100;i++)
                   A[i]=A[i]+10      in this the loop is from i=0 to <100 rt .

to execute this loop which is asking us  to take i=0 first .....so we should have considered only a[0]   but we are also getting a[1] into picture..........

i assumed i must be the index of the array and if we are running the loop then a/c to this statement  A[i]=A[i]+10   we must go at 10 indexe's beyond what we are working on right now means if we have taken i=0 then at RHS A[i] should have value A[i]+10 (value of i plus 10) please explain this.....

0
@shekhar sir, if value at i = 0 , is 5 .

Then, it will just add the value ,

Also , if 1 word = 1 byte , then element size is 32 bits.... It won't affect next element...
0
@kapil you men loop is on index not value if value is incrementing it is not going to effect the loop
0
Yes sir, it won't affect, as we are just changing our elements.. We are providing them new value...
0
@shekhar sir,

The answer could change , if we consider write cases ,i.e , whether our cache is write back or write through. We can also consider them, but as such nothing is given like this in the question , so I didn't considered them. I just made it simple...
0
@kapil you did not say anything  about why a[1] getting fetched along with a[0] when we are working on a[0] at first iteration ......i understood that part that cache block can hold 2 elements at the same time but it is not necessary condition here that we should fetch a[1] along with a[0] evenif we have space to place it in block ..........
+1
Sir, it is neccesary, as we can only transfer blocks from memory to cache . we cannot pass only 1 element. Cache line acts as a basic building block to transfer information between memory levels...
+1
@kapil thanks this is point i was looking for ...everything is clear now .
0
@Kapil In case, if each element has size of 8 words, it will not fetch it's adjacent element and hit rate will be 25% right ?
0
We don't fill half line/block at a time (one element of the said array is equal to half the line/block size). we fetch whole block/page from memory. and the block in memory are also  8 word size and due to contiguous memory locations of consecutive array elements a[0] and a[1] will be present in same block in MM.
0

@Kapil @shekhar chauhan @Arjun

What will happen once all the Cache Blocks get occupied? 

A complete Block is replaced by a new Block. Correct me, if i am wrong.

+1 vote

Each cache block is of 8 words.

One array element is of 4 word size

Hence each block can store 2 array elements.

In the for loop, 

When i=0, cache miss, A[0] and A[1] are fetched

When i=1,cache hit

When i=2,cache miss, A[2] and A[3] are fetched

When i=3 cache hit

***************

When i=98, cache miss, A[98] and A[99] are fetched

When i=99 cache hit

So cache hit and miss come alternatively.hit ratio is 50% and set associative mapping is used

by Boss (33k points)
0
@shiva for i=0 it is okay that we are fetching a[0] but why a[1] ?

A/c to the statement A[i] = A[i] +10

if we consider i = 0 then there is no way we are getting a[1] any where in first iteration .
+2
first of all here for each iteration memory is accessed for 2 times- one for read and another for write. Now since block size is = 8 words and element size is = 4 words so two elements will come into block.

So for i= 0 , a[0] and a[1] is in the 0th cache block. read a[0] - miss and write a[0] - hit.

     for i=1 , as a[1] is already in the cache block , so both a[1] - hit and write a[1] - hit.

so for i= 0 and i= 1 .. total memory access = 4 where hit = 3 and miss = 1.

Similarly, for i= 2 and 3 , total memory access = 4 where hit = 3 and miss= 1.

So for i=0 to 99 , total memory access= 100 * 2 = 200 , where hit = 150 and miss = 50 ,

Hit ratio = 150/200 = 3/4 = 0.75
0
@vijay does it has nothing to do with the statement how many memory location going to to accessed in each iteration .as you said there will be one read one write  at first place. ?

in your explanation you did not say anything about  this part of increment "+10". how is it going to effect the answer ?
0 votes

According to the question size of block 8 words=3bits

No of  blocks=32/8 =22 = 2

Array A has 100 elements =400 words

Each block contain 8 words

So  in a block 1st one is hit and next 7 words are miss.

No of miss here 400/8 =50

Number of hits =350

So, hit ratio 350/400⨉100=87.5%

by Veteran (119k points)
0 votes
for(i=0;i<100;i++)
  A[i]=A[i]+10

Since cache clock size=8 words 

Each array element size is 4words 

Now in each cache block there exist two array elements like below way

A[0]A[1] A[2]A[3]   ........ A A[94]A[94] A[96]A[97] A[98]A[99]

So when ever we access A[0] then we can access both A[0]A[1]

A[0]     R(Miss)    W(Hit)

A[1]     R(Hit)         W(Hit)

Hit=3/4

Miss=1/4

by Boss (10.2k points)

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
50,737 questions
57,309 answers
198,338 comments
105,026 users