The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+14 votes
1.4k views

For a set-associative Cache organization, the parameters are as follows:

$t_c$ Cache access time
$t_m$ Main memory access time
$l$ number of sets
$b$ block size
$k\times b$ set size

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

asked in CO & Architecture by Veteran (59.6k points)
retagged by | 1.4k views
+9

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?

2 Answers

+16 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 if $l$, so for $l=1$ also we have $\text{hit ratio} = 1- \frac{1}{100b}$
answered by Veteran (363k points)
edited by
+1
Please explain no. of access and no. of misses point.

And what does 1<m<=1 mean?
0
@Arjun How no of misses =n?
0
@shikhar that is $l$. Corrected now.

@Pranabesh See now..
0
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?
0
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.
0
But you have mentioned "we have n blocks each of size b for a total size of n×b"
+1
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$
+5

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.

0
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?
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 what if every block of loop maps to the same set?? plzz clear this part.
0
same doubt, it should be 100 n accesses and n misses, and hence 99n hits. plzz see arjun sir.
+3
@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.
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.
0

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

+4
@Sushmita Yes, that is correct. But for cache hit/miss we always count no. of memory accesses and not no. of unique block accesses.
0
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)
+1

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.

 

0

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 vote

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.

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

 

answered by Boss (16.1k points)
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 .
0
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.

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

42,626 questions
48,616 answers
155,902 comments
63,874 users