GATE CSE 1998 | Question: 18

Question

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 \leq m \leq l$.

Give the value of the hit ratio for $l = 1$.

Comments

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.

---

Can I simply say answer is 99 percent?

---

Unable to  understand the question :(
Understood now

---

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

Answer 1

$\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 cache as $m \leq l$. So we are guaranteed that the entire loop is in cache without any replacement. (Here we assumed that the memory size of $n \times b$ used by the loop is contiguous, or else we could have a scenario where the entire loop size gets mapped to the same set causing cache 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}$

Comments

Please explain no. of access and no. of misses point.

And what does 1<m<=1 mean?

---

@Arjun How no of misses =n?

---

@shikhar that is $l$. Corrected now.

@Pranabesh See now..

---

set size =k*b and block size =b so no of blocks per set is k so k-way set associative and size of loop is n*b and n= k*m then how can we conclude that  no of blocks is n?

---

sizeof loop is $n*b$. That means $n$ blocks. $k$ is the associativity- which can tell where the block goes in cache, but dont help in saying how many blocks are there.

---

But you have mentioned "we have n blocks each of size b for a total size of n×b"

---

Here size of loop=$k\times m\times b$

size of 1 set =$k\times b$

there are l sets

So, total set size =$k\times b\times l$

---

Here, size of the loop is smaller than size of a set as m≤l.

Shouldn't this be size of the loop is smaller than size of a cache. As size of a loop is $k*m*b$, size of a set is $k*b$ and $m > 1$. Also if I am correct then above answer may be wrong if all lines map to same set.

---

why total number of access = n x b ?

You said there are n blocks each of size b, so in total there should be 100n accesses?

---

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 what if every block of loop maps to the same set?? plzz clear this part.

---

same doubt, it should be 100 n accesses and n misses, and hence 99n hits. plzz see arjun sir.

---

@sushmita
Set size = $k\times b$
Loop size = $k\times b\times m$
Means there are $m$ different sets in loop, right ?
What you are saying is- what if these all $m$ sets maps to same set. Is it possible ?
If there are $m$ different sets then they must be having $m$ different set numbers.
Ohk, consider this eg-
starting address of loop is say $0\text{x}1260$ i.e. $0001\text{  }0010\text{  }0110\text{  }0000$
Let least significant 4 bits are Line offset (here size of line is $2^4$ and in question it is $l$)
Next 4 bits are set number. (total sets = $2^4$), and it is $2$ way set associative.
Now, we compare Tag fields of line $01100$ to $01101$
[Notice that i appended 1 extra bit in last, bcoz it is 2 way set associative, it is $4$ way set associative then i will compare Tag fields of line $011000$ to $011011$]

if a match is found then return byte $0000$ (0th Byte of line) of that line.
Now Simply tell me Next byte address?
-$0\text{x}1261$ i.e. $0001\text{  }0010\text{  }0110\text{  }0001$ (it will be in same line)

Simmilarly adress of 3rd Byte = $0\text{x}1262$ and So on..
Once u exhaust size of one line, next adress would be second line-
$0\text{x}1270$ =   $0001\text{  }0010\text{  }0111\text{  }0001$ this address maps to set $7$.
Set $7$ has two lines- line 14 and 15. We compare line number $01110$  and line number $01111$ to tag field.
-------
All i mean is, u can not map all addresses to same set, at one moment u will exhaust then The next adress will automatically map to next set.

---

yeah u r right. absolutely clear explanation. Thanx a lot sachin.

---

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.

---

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

---

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

---

OHHHH!!!!! understood it. Thanx a lot sir.

---

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.

---

Sir here is it assumed that one word = one byte ?

---

Size of Loop = Set Size * m ( m <= l ), l = 1, therefore m <= 1,

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

---

Is my understanding correct ?

---

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.

---

@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

---

@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

---

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

---

Even I have same doubt.!! But answer is explained well thanks sir

---

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

 

---

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

---

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.

---

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

---

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

 

---

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

---

What if a set is 4-way set associative and m=2, and in a single loop all the k*m(=8 here) MM blocks are mapping to same cache set? Then we have to replace some of the existing cache block which is already existing in the same set.

I think number of block access will be less than the total cache size as k*b*m can max goto k*b*l which is the cache set size. But nowhere in the question stated that in a single cache set only k blocks can be mapped at max.

Even second part looks vague to me as value of l=1 and at the same time 1<m<=l which means 1<m<=1 and there is no integer solution for m for this.

---

yes, it is total cache size – updated now and the loop size is assumed to be contiguous.

---

Why are we replacing in terms of blocks and not in terms of words? 

When the CPU will generate an address, it will do so for a specific word in the RAM as RAM is word addressable. So, when we access that WORD, it will bring the BLOCK from RAM to CACHE and for the next k-1 words, it will actually be a hit. 

 

So, in the first iteration:-

No of words we want to access → k*m

No of words that were a hit → (k-1)*m

For the next 99 iterations:-

No of words we want to access → k*m*99

No of words that were a hit → k*m*99

 

Total number of hit words → 100km-m

Total word access → 100*k*m

Hit ratio → (100km-m)/100km = 1-(1/100k)

 

It makes sense to me that this answer depends on k(associativity). The answer that is selected depends on block size(b). How is that possible ??

Please reply with what's wrong with my approach !!!

---

@Arjun sir here number of accesses will be n not nb. As we will consider the number of blocks.

---

That will be the case for “unique” accesses right?

---

@gatecse sir n is the number of blocks and nb is the size. 

---

Cannot the same block be accessed multiple times within one iteration of the loop?

Answer 2

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$

 

Comments

PeRFect explanation :)

---

@Ayush Upadhyaya

Very Easy & Intuitive explanation . Thanks

---

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

Answer 3

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} $

Comments

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

---

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 .

---

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.

Answer 4

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