Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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?

share|improve this question
add comment

2 Answers

up vote 2 down vote accepted
+50

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.

share|improve this answer
    
Got it. Your method 1 is equivalent to my method 2. I think that is the right one. The solution of the first question is wrong. The answer should be $1.23T_1$. Thank you. –  Shashwat Dec 4 '12 at 18:17
    
I have expanded the useless information though it is of no use here. –  Shashwat Dec 4 '12 at 18:18
    
The first answer in your question is wrong (for computer architectures that are common now). It is wrong just in case if you have some hypothetical machine. But let me explain once more. You always try to access a part of memory on level 1 (with probability 1), and if you miss, then you access level 2 memory with probability $1-h$. –  Nejc Dec 4 '12 at 21:21
    
And I think you should still look at the formula in my Method 1 - it is not the same as with your Method 2. The answers are the same just because the numbers add up. For an overview, see cs.fsu.edu/~hawkes/cda3101lects/chap7/avgmemaccesstime.html –  Nejc Dec 4 '12 at 21:23
    
Both methods are same not only because the answers match. Mine can be written in statements as "if there is a hit, only cache would be accessed (0.9 $T_1); if there is a miss, both cache and memory would be accessed (0.1 $T_1 + 2*T_1)". Its just an arrangement of variables and statements. But I would prefer your statement. –  Shashwat Dec 5 '12 at 10:17
add comment

It's a design choice for the cache. So if you are designing a cache, do both and examine the consequence in term of performance, complexity of the design and other impacts in order to make your choice.

If you are trying predicting for a given cache, look at its spec.

And note anyway that cache have often a more complex behavior than that so whatever is your result, don't take it for an absolute truth, there are factors you aren't taking into account with such a simple minded computation (grace buffers, prefetch, bus contention, ...)

share|improve this answer
    
But how do I know what is expected in the question? –  Shashwat Dec 4 '12 at 8:47
    
You search clarification near the one who is asking the question if you are not in position to decide yourself. Or the useless information isn't as useless as you first though. –  AProgrammer Dec 4 '12 at 9:40
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.