The Gateway to Computer Science Excellence
+22 votes
2.6k views
For a set-associative Cache organization, the parameters are as follows:
$$\begin{array}{|c|l|} \hline \text {$t  _c$} &  \text{Cache Access Time }\\\hline \text{$t _m$} &  \text{Main memory access time}\\\hline \textit{l} & \text{Number of sets}\\\hline \textit{b} & \text{Block size}\\\hline \textit{$k \times b$} & \text{Set size}\\\hline \end{array}$$
Calculate the hit ratio for a loop executed 100 times where the size of the loop is $n\times b$, and $n = k\times m$ is a non-zero integer and $1 < m \leq l$.

Give the value of the hit ratio for $l = 1$.
in CO and Architecture by Veteran
edited by | 2.6k views
+18

Loop is of the size of n blocks, each block size is b
maximum value of m can be equal to $l.$

loop size $= k*l*b$
Cache size $= k*l*b$

both are of equal size.

for the first iteration = n blocks are accessed and all are miss
for next 99*n blocks all will be hit

hit ratio = number of hits/ total number of requests
$= 99n/100n = 99/100$ (or) $1 - n/100n$

Hit/ Miss ratio is irrespective of $l.$

ps:  For cache hit/miss we always count no. of memory accesses and not no. of unique block accesses. but we can ignore b for the sake of simplicity.

0
Can I simply say answer is 99 percent?
0
Unable to  understand the question :(
0
" the loop will require the same set of data that it required in iteration 1 ( since a for loop is used to execute same set of instructions again and again)".    

This is not that initutive .

4 Answers

+24 votes
Best answer
$\text{Size of the loop} = n\times b = k \times m \times b$

$\text{Size of a set} = k \times b$ ($k-way$ associative)

Here, size of the loop is smaller than size of a set as $m \leq l$. Now, however be the mapping (whether all be mapped to the same set or not), we are guaranteed that the entire loop is in cache without any replacement.

For the first iteration:

$\text{No. of accesses} = n \times b$
$\text{No. of misses} = n$ as each new block access is a miss and loop body has $n$ blocks each of size $b$ for a total size of $n \times b$.

For, the remaining 99 iterations:

$\text{No. of accesses} = n \times b$
$\text{No. of misses} = 0$

So, $\text{total no. of accesses} = 100 nb$

$\text{Total no. of hits} = \text{Total no. of accesses} - \text{Total no. of misses}$

$= 100 n b - n  $

So, $\text{hit ratio} = \frac{100nb - n}{100nb} = 1- \frac{1}{100b}$

The hit ratio is independent of $l$, so for $l=1$ also we have $\text{hit ratio} = 1- \frac{1}{100b}$
by Veteran
edited by
0
yeah u r right. absolutely clear explanation. Thanx a lot sachin.
0
Here we are considering 1 time iteration , all blocks are accepted in cache. Even 1 time iteration is equal to size of cache.

Otherwise remaining 99 iteration miss cannot be 0.rt?

But how it considered?We have just to assume it.
+1

Isn't total block access=100 n out of which n are compulsory misses and 99n are hits??

+7
@Sushmita Yes, that is correct. But for cache hit/miss we always count no. of memory accesses and not no. of unique block accesses.
+1
OHHHH!!!!! understood it. Thanx a lot sir.
0
Here, size of the loop is smaller than size of a set as m≤lm≤l. Now, however be the mapping (whether all be mapped to the same set or not), we are guaranteed that the entire loop is in cache without any replacement.
 

@Arjun sir, shouldnt it be size of loop smaller than cache and not set???

loop=k*m*b

cache size=l*b*k

and m<=l, which imply loop is smaller than or equal to cache size.
0
Sir here is it assumed that one word = one byte ?
0
Size of Loop = Set Size * m ( m <= l ), l = 1, therefore m <= 1,

So, Size of Loop = Set Size * 1(or less than 1)
+3

Is my understanding correct ?

0
Hi... Is is true to say that

Memory access is in terms of words that is why we take 100nb accesses

If cache is accessing main memory so the movements are in terms of blocks so we take n misses and not nb misses.
0
@Sushmita I am having the same doubt as you had earlier. Out of 100n access 99n access are hits. As per the solution if the total no of access are 100*n*b then no of misses should be n*b?? Please help here to understand
0
@Arjun "No. of misses=n as each new block access is a miss and loop body has n blocks each of size b for a total size of n×b"...Here as each new block access is a miss and loop body has n blocks then total number of access should also be n, why n*b is taken ?? Please help me understand
0
@Arjun sir, When the loop is accessed second time then how can we be sure that i access the same data.

Let us say my for loop access 100 elements and i have block size=10 elements.Now total 10 misses will come for second iteration.

Now in my next iteration also i will access the 100 elements,but in answer you have assumed that these are same 100 elements that are accessed in previous iteration,but these elements can be different also.In general if nothing is given,then we should assume that these can be different also.

So 100*nb total access and n miss per iteration.

Total hit= 100nb -n

Hit ratio =$(100nb-100*n)/(100nb)$

Please tell why this is not correct?
0
Even I have same doubt.!! But answer is explained well thanks sir
0

@rahul sharma 5

i think here we are considering that the size of cache is as large as to accomodate the complete loop;

size of cache = k* l * b  and size of loop = k* l * m and m<=l

so cache will contain the whole loop , so misses will be there only when the loop runs for the first time (COMPULSORY MISSES) and rest 99 times all hits will be there.

 

+1

sushmita  YOU ASKED THIS DOUBT ....I HAVE SAME DOUBT

Isn't total block access=100 n out of which n are compulsory misses and 99n are hits??

YOU GOT THIS REPLY 

@Sushmita Yes, that is correct. But for cache hit/miss we always count no. of memory accesses and not no. of unique block accesses

CAN U PLEASE EXPLAIN WHAT IS MEANT BY WE ALWAYS COUNT NUMBER OF MEMORY REFERENCES SO HOW TOTAL NUMBER OF ACCESSES BECAME 100nb...........

+1
it means that we always take no of word references while calculating hit/miss ratio.

Every block access for the very first time will result in a compulsory miss and suppose there are 10 blocks with 8 words per block then if we assume fully associative cache it will result in 10 misses and 80-10=70 hits assuming cache is large enough.
0

@Sachin Mittal 1

We're considering total no of memory-accesses here i.e "100nb" and not "100n".

And misses are being counted as per blocks i.e "n".

Is this because once we incur a miss, the whole BLOCK is brought from higher-level memory to lower-one?

+1

@Arjun sir

*****PLEASE DO CHECK*****

you said size of loop=kmb

size of set=kb

m is within 1 and L

so why do you say size of the loop is smaller than the size of a set.

casuse kmb is always greater than kb if m>1

shouldn't the correct interpretation be like

size size of the loop is smaller than the size of all sets.

so in worst case m=L

size of 1 loop access=kLb

its written 1 set is kb

so size of loop(1 access)=L×kb.  i.e. size of all sets.   i.e. size of all blocks in cache.

now 1 loop access=nb accesses

here no. of misses=n 

now in worst case n=km=kL

so with n misses we have filled all cache blocks..

so in each loop access i.e. 100 times in total we get total 100n misses

so 100nb accesses and 100n misses

therefore,

(100nb-100n)/100nb    is the hit ratio.

i.e.   (b-1)/b

i.e.   1 - 1/b

please check @Arjun sir.....

 

0

@Arjun sir quoting your answer - "Here, size of the loop is smaller than size of a set as m≤lm≤l. Now, however be the mapping (whether all be mapped to the same set or not), we are guaranteed that the entire loop is in cache without any replacement."

According to me the size of the loop is smaller the size of the entire cache and not a set. Please correct me if I am wrong.

P.S. - asked by many users, not yet answered.

+9 votes

Given a set associative cache.

$l-Number\,of\,sets$

$b-\,block\,size$

$k *b - \, set\,size$

So given set associativity=k

Number of sets in cache=$l$

Size of loop=$n*b \rightarrow k*m*b$(Means $k*m$ number of blocks of Main memory)

Considering worst case when $m=l$

Size of loop(In blocks)=$l*k$

Now Mapping function of this cache=(MM Block Number) $mod\,l=(l*k)mod\,l$ means atmost "K" blocks can map into the same set.

What is the set associativity of this cache=>K(means at max, K blocks of Main-memory can be accommodated without replacement which maps into the same set).

So, this means, even in worst case, after my full loop comes into the cache, then subsequent accesses to the loop won't cause replacement in the cache and full loop can be accommodated in the cache without any replacement.

At first iteration: All "n" Main-memory blocks will be brought into the cache and mapped into "L" sets of cache having "K" lines each.

So, first "n" misses here(In terms of blocks).

For Remaining 99 iterations: Since, now full loop is in cache, so no cache misses.

-------------------------------------------------------------------------------------------------------------------------------

Or we can directly give the answer now. Only during the first iteration, misses will occur and the remaining 99 iterations will be a hit.

So, hit ratio=99 percent.

Hit rate=$\frac{100n-n}{100n}=0.99=99\,percent$

 

by Boss
edited by
0
"Now Mapping function of this cache=(MM Block Number) modl=(l∗k)mod l"

Sir here in place of block no why you are using no of block(l*k) and by putting block no we get least significant bit which tell the set no but by putting no of block(k*l) mod l it always give remainder 0 .And it doesn't give any least significant bit which doesn't tell anything about set no .
+1
See in that expression my intention was to show that utmost K blocks will map into the same set.

Here according to the question,  a single set of the cache can hold k lines.

Suppose the size of loop was $l(k+1)$, then this means k+1 blocks would map into same set of cache. But cache can hold only k lines at once.Means, one of the set line will be replaced in the cache when the loop will be accessed and hence cache replacement policy will come into effect.
0
PeRFect explanation :)
0

@Ayush Upadhyaya

Very Easy & Intuitive explanation . Thanks

0

@Ayush Upadhyaya We generally access a Byte/Word in a Cache, therefore, No. of accesses = n*b. Once, the desired Block is loaded in Cache, we get a Hit for remaining Bytes/Words for that particular Block.

Correct me, if i am wrong.

+2 votes

Let us first draw the cache with the configuration given in the question


In question, we are given a loop that executes for $100$ times and the size of loop is $n*b$ or we can say $n$ blocks.

i.e. The loop requires $n$ blocks of data in each iteration.

 

Let us now execute the loop,

 

Iteration 1

First the CPU checks whether the data i.e. $n$ blocks that the loop requires to execute in the first iteration is present in the cache or not.

In worst case it may happen that none of the $n$ blocks that we require are present in the cache memory.

So we go to main memory and select those $n$ blocks and also bring them in cache memory so that iteration $1$ could be executed successfully.

Given : $n= k*m$ and in worst case $m=l\  (\because 1 \leq m \leq l)$

i.e. in worst case $n = k*l$ .......$eq (i)$

i.e. number of blocks that we need to bring into cache memory from main memory for iteration $1$ at max.

      $=n$ blocks

      $=k*l$ blocks

      $=$ size of cache. (from diagram)

 

Hence, we can say that in iteration $1$ all the data that we require = The size of cache memory (at max)

and after bringing the data in cache, the iteration $1$ of loop is executed successfully.

$\therefore$ iteration $1$ was a $MISS$ case since we did not found the data that we were looking for in the cache memory.

 

How many misses and block accesses were there ?

 

We need to bring $k*l$ blocks into the cache.(From $eq (i)$)

Also, the cache is set associative so we could bring $k$ blocks whenever a miss is encountered for a block.

Eg :-

if block $1$ of set $1$ is missing we could bring $k$ blocks of set $1$ in cache.

if block $1$ of set $2$ is missing we could bring $k$ blocks of set $2$ in cache.

..........

if block $1$ of set $l$ is missing we could bring $k$ blocks of set $l$ in cache.

We can do this because initially the whole cache is empty.

From this we can say that there were $l$ block misses and we brought $k*l$ blocks or $n$ blocks ( From $eq(i)$ )  into the cache memory.


Iteration 2

Now the CPU again checks whether the data i.e. $n$ blocks that the loop requires to execute in the second iteration is present in the cache or not.

Now in this case the loop will require the same set of data that it required in iteration $1$ ( since a for loop is used to execute same set of instructions again and again)

And we know that the data is present in cache since we have already loaded them in iteration $1$. 

$\therefore$ iteration $2$ would be a $HIT$ case since we found the data that we were looking for in the cache memory.

 

How many misses and block accesses were there ?

As already explained above there are no misses since data blocks that we require are already present in cache.

This iteration also needed $l*k$ blocks of data i.e. $n$ blocks ( From $eq(i)$ )


Similarly, the remaining $98$ iterations of the loop would also be counted as $HIT$ cases and each one of them require $l*k$ blocks of data i.e. $n$ blocks ( From $eq(i)$ )

$\therefore \ Miss\ Ratio\ =\frac{Miss\ cases}{Total\ blocks\ access\ required}= \frac{l}{l*k+l*k+l*k....._{100\ times}} = \frac{1}{100k} $

 $\therefore \ Hit\ Ratio\ =1 - \ Miss\ ratio\ = 1 - \frac{1}{100k}= \frac{100k-1}{100k} = 1 - \frac{1}{100k} $

Now in worst case $k=1b$ i.e. each set has only $1$ block.

 $\therefore \ Hit\ Ratio\ = 1 - \frac{1}{100b} $

by Boss
edited by
0

@Satbir

ans given as

$= 100 n b - n  $

why not same for u??

+1
For cache hit/miss we always count no. of memory accesses and not no. of unique block accesses, so we can ignore b for the sake of simplicity.

see the last comment on best answer
0

@Satbir

for a loop executed 100 times

but in question, they havenot mentioned what that loop atually is?

rt?? 

0
Yes , they just gave size of loop = size of cache.

and from loop we should deduce that same data/instruction are used again and again for 100 times.
0
Now suppose,

if all elements are different from other.

So, 1st time $n*b$ miss

So, in 100 time of loop execution  $100*n*b$ miss

right??

This can be case too.
0
Yes. Its like we are accessing different set of data in each iteration so hit ratio would become 0.
0
Then how r u telling that hit will be 99%
+1

if all elements are different from other.

This is not the case in loops.

Loops are used when we want to execute same instruction multiple times and not different instructions.

generally, In each iteration of loop we will get same set of instructions again and again.

for(i=0;i<100;i++)

{

    printf("Hi');

    printf("bye");

}

First time cahe is empty , so we load printf("Hi'); and printf("bye"); in cache so its a MISS case.

For next iteration 99 iterations printf("Hi'); and printf("bye"); are already in cache so its a HIT case.

so 99 HIT cases out of 100 cases = 99% HIT RATE

0

@Satbir

yeah.

but see selected answer once.

It is telling

$\text{hit ratio} = \frac{100nb -\color{ \red}{n}}{100nb} = 1- \frac{1}{100b}$

shouldnot it be $\text{hit ratio} = \frac{100nb -\color{ \red}{nb}}{100nb} = 1- \frac{1}{100b}$ then?

 

0

@srestha

Please check my answer, I updated it now. First i calculated hit and miss cases in terms of how many times loop would create hit and how many times there would be miss, but hit and miss should be calculated based on memory access.

0

@Satbir

hope now correct.

One thing tell me 

Size of loop $n\times b=k\times m\times b$

Now, $k\times b$ set size.

So, we can think , k way set associative

and number of sets are m

Number of blocks are n

right?

0
yes...in worst case m=l since 1<=m<=l
+1

this is the best one !! @Satbir thanks !

" the loop will require the same set of data that it required in iteration 1 ( since a for loop is used to execute same set of instructions again and again)".    

This is not that initutive .

+1

You can assume like 

int i;
for(i 0;i<100;i++)
{
    printf("hello");
    printf("world");

}

Here we  need same set of instructions again and again inside the loop.

0 votes

Please have a look and tell if this is the right process to do it.

 

by Active
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
52,217 questions
59,907 answers
201,103 comments
118,146 users