Doubt regarding cache hit ratios and access time

Question Detail: 

Question 1: What is the average access time for a 3-level memory system with access time $T_1$, $2T_1$ and $3T_1$? (Hit ratio $h_1$ = $h_2$ = 0.9)

The solution given is: $0.9[T_1] + 0.1(0.9[2*T_1] + 0.1[3*T_1]) = 1.11[T_1]$ (Method 1)

Here, they have considered the page won't be copied to the lower level. Otherwise, it would have been like the following

If a page is not there in cache, it would be copied from main memory to cache and then accessed. $T_1 + 2T_1$

If a page is not there even in main memory, it would be brought to main memory, then cache and then accessed. $T_1 + 2T_1 + 3T_1$

$0.9[T_1] + 0.1(0.9[T_1+2*T_1] + 0.1[T_1 + 2*T_2 + 3*T_1]) = 1.23[T_1]$ (Method 2)

I went through another similar problem.

Question 2

Cache Access Time = 20ns Memory Access Time = 120ns Hit Ratio = 0.8 Some other useless information below... Cache Block size = 16 words Set size = 2 blocks Number of sets = 128 Size of main memory address = 21bits What is the hit ratio if the average access time is increased by 40ns? (A) Remains same      (B) 0.921     (C) 0.467      (D) 0.592 

I simply calculated it using Method 1 as follows

Effective access time = 0.8*20 + 0.2*(120) = 40ns Increase by 40ns, so new time = 80ns 80 = h*20 + (1-h)*120 Hit ratio = 0.4 

But this is not in the options

But when I calculated it using Method 2

Effective access time = 0.8*20 + 0.2*(20 + 120) = 44ns Increase by 40ns, so new time = 84ns 84 = h*20 + (1-h)*120 Hit ratio = 0.467 

That is option (C)

Here, the answer is coming using Method 2 but in the above question they are using Method 1.

How do I know which method to take while solving such problems? Whether would the missed page be brought into the lower memory (cache) or not?

Asked By : Shashwat

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/7071

Answered By : Nejc

I think, that the part with some other useless information... in your problem specification must contain some information on solving your problem. As I was trying to calculate the numbers that you got I found some errors, and I thought there must be some more input. Let me first explain:

Your formulas are incorrect for both Method 1 and Method 2. When accessing some memory level you ALWAYS access this level, not with probability! Explanation goes something like this: You ACCESS $L1$, if you MISS (some probability), you go to $L2$. On $L2$ you again make an ACCESS, and if you MISS (with some probability), you move to $L3)...

So Method 1 with your first problem would be: $$[T1]+0.1([2*T1]+0.1*[3*T1])=1.23[T1]$$

And Method 2 for first problem: $$[T1]+0.1([T1+2*T1]+0.1[T1+2∗T1+3∗T1])=1.36[T1]$$

So now looking at your second problem, you can solve it by using Method 1:

New Method 1

Effective access time = 20 + 0.2*(120) = 44ns Increase by 40ns, so new time = 84ns 84 = 20 + (1-h)*120 Hit ratio = 0.467 

Note that here I assumed you made a mistake with answer $(C)$ in your problem description (it is not $0.4467$, but it is $0.467$).

Now if you would have miss penalties defined in your problem statement, then you would use Method 2. Miss penalty just says, that if you do not get a result in your current level, then you have to copy it from the upper level. Now let us assume, that miss penalty on second level is 300ns (that means copying the contents to level 1 and accessing it). Everything else stays the same. The calculations would go:

New Method 2

Effective access time = 20 + 0.2*(120+0.2*300) = 56ns Increase by 40ns, so new time = 96ns 96 = 20 + (1-h)*(120+(1-h)*300) Hit ratio = 0.65840 

One other caution... You need to use the same formula for calculating the average access time if you chose one method. (In your Method 2 you calculated access time by Method 2 and then calculated the new hit ratio with Method 1)

So how do you know which method to choose? From the problem description! If you have miss penalty given, then you take the second approach. If you do not have miss penalty, then you use the first approach.