The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+15 votes
1.5k 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.7k points)
retagged by | 1.5k views
+10

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 (369k points)
edited by
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.

 

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

0
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.
+2 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.

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

 

answered by Boss (18.9k 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

44,303 questions
49,797 answers
164,409 comments
65,857 users