edited by
11,874 views
33 votes
33 votes
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$.
edited by

5 Answers

42 votes
42 votes
$\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}$
edited by
19 votes
19 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$

 

edited by
7 votes
7 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} $

edited by

Related questions

0 votes
0 votes
0 answers
1
4 votes
4 votes
3 answers
2
Kathleen asked Sep 25, 2014
4,467 views
The address space of $8086$ CPU isone Megabyte$256$ Kilobytes$1 \;\text{K}$ Megabytes$64$ Kilobytes
36 votes
36 votes
2 answers
3
40 votes
40 votes
4 answers
4
Kathleen asked Sep 25, 2014
10,889 views
Which of the following addressing modes permits relocation without any change whatsoever in the code?Indirect addressingIndexed addressingBase register addressingPC relat...