Cache effective access time calculation

Question

In order to calculate the effective access time of a memory sub-system, I see some different approaches, a.k.a formulas. All are reasonable, but I don't know how they differ and what is the correct one.

Assume a two-level cache and a main memory system with the following specs:

h1 = 80%       t1 = 10ns    L1 cache
h2 = 40%       t2 = 20ns    L2 cache
h3 = 100%      t3 = 100ns   Main memory

t1 means the time to access the L1 while t2 and t3 mean the penalty to access L2 and main memory, respectively.

I see two formulas as described below:

1- Teff = t1 + (1-h1)[t2 + (1-h2)t3] which will be 32. The logic behind that is to access L1, first. So, t1 is always accounted. Then with the miss rate of L1, we access lower levels and that is repeated recursively. I agree with this one! You can see further details here.

2- As discussed here, we can calculate that using Teff = h1*t1 + (1-h1)*h2*t2 + (1-h1)*(1-h2)*t3 which yields 24. However, that is is reasonable when we say that L1 is accessed sometimes. You can see another example here. Although that can be considered as an architecture, we know that L1 is the first place for searching data. So, the L1 time should be always accounted.

Is there any suggestion for that?

Answer 1

This is the kind of case where all you need to do is to find and follow the definitions. There is nothing more you need to know semantically. What is actually happening in the physically world should be (roughly) clear to you. It is a question about how we translate the our understanding using appropriate, generally accepted terminologies. It is a question about how we interpret the given conditions in the original problems.

(By the way, in general, it is the responsibility of the original problem/exercise to make it clear the exact meaning of each given condition. A notable exception is an interview question, where you are supposed to dig out various assumptions.)

Let us take the definitions given at Cache Performance by gshute at UMD as referenced in the question, which is consistent with the Wikipedia entry on average memory access time.

Cache Access Time

The fraction or percentage of accesses that result in a hit is called the hit rate.
The fraction or percentage of accesses that result in a miss is called the miss rate.
It follows that hit rate + miss rate = 1.0 (100%).
The difference between lower level access time and cache access time is called the miss penalty.
Effective access time is a standard effective average.

effective-access-time = hit-rate * cache-access-time
                      + miss-rate * lower-level-access-time  

Miss penalty is defined as the difference between lower level access time and cache access time. Then the above equation becomes

effective-access-time = cache-access-time + miss-rate * miss-penalty

Since "t1 means the time to access the L1 while t2 and t3 mean the (miss) penalty to access L2 and main memory, respectively", we should apply the second formula above, twice. That is,

Teff = t1 + (1-h1)[t2 + (1-h2)t3] = 32

For the sake of discussion, if we assume that t2 and t3 mean the time to access L2 and main memory including the time spent on checking and missing the faster caches, respectively, then we should apply the first formula above, twice. That is,

Teff = h1*t1 + (1-h1)*h2*t2 + (1-h1)*(1-h2)*t3 = 24. 

For the sake of discussion again, if we assume that t2 and t3 mean the time to access L2 and main memory directly assuming there is no caches at all, respectively, then we should claim there is not enough information to compute a reasonable answer. Or if we can assume it takes relatively ignorable time to find it is a miss in $L1$ and $L2$ (which may or may not true), then we might be able to apply the first formula above, twice.

You could say that there is nothing new in this answer besides what is given in the question. I would actually agree readily. All I have done is basically to clarify something you have known as well as showing how to select the right definition or formula to apply.

---

Now that the question have been answered, a deeper or "real" question arises. Are those two formulas correct/accurate/make sense?

The picture of memory access by CPU is much more complicated than what is embodied in those two formulas. The actual average access time are affected by other factors [1]. However, we could use those formulas to obtain a basic understanding of the situation.

Answer 2

Actually, this is a question of what type of memory organisation is used. There are two types of memory organisation- Hierarchical (Sequential) and Simultaneous (Concurrent). In the hierarchical organisation all the levels of memory (cache as well as main memory) are connected sequentially i.e. the CPU can access L2 cache only if there is a miss in L1 cache.

CPU -> L1 -> L2 -> Main Memory

In this case the first formula you mentioned is applicable as access of L2 starts only after L1 misses. But, in sequential organisation, CPU is concurrently connected all memory levels and can access them simultaneously.

CPU ->L1
CPU ->L2
CPU ->Main Memory

In this case, the second formula you mentioned is applicable because if L1 cache misses and L2 cache hits, then CPU access L2 cache in t2 time only and not (t1+t2) time. This is due to the fact that access of L1 and L2 start simultaneously. The hierarchical organisation is most commonly used. But it is indeed the responsibility of the question itself to mention which organisation is used.