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

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?

1 Answer

+15 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 (355k points)
edited by
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)
0

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


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

37,996 questions
45,492 answers
131,517 comments
48,592 users