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

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.