2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Can you provide a url or reference to the original problem? It looks like the solution depends on the definition of "the time to access the L1" and "the penalty to access L2 and main memory". $\endgroup$ – John L. Nov 26 '18 at 1:05
  • $\begingroup$ @Apass.Jack: I have added some references. Please see the post again. $\endgroup$ – mahmood Nov 26 '18 at 17:01
  • $\begingroup$ I am writing an answer ... $\endgroup$ – John L. Nov 26 '18 at 17:25
4
$\begingroup$

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
Cache performance
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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks for the answer. I would like to know if penalty is the same as including the time spent on checking and missing the faster caches or not? Assume t1 means access to L1 and t2 means access to L2 (there is no L1). It is correct to assume that in a system with CPU->L1->L2 configuration, the penalty time for missing in L1 is larger than t2. Do you agree with that? $\endgroup$ – mahmood Nov 26 '18 at 19:06
  • $\begingroup$ In other words, the first formula which is Teff = t1 + (1-h1)[t2 + (1-h2)t3] actually assumes that t2 and t3 are the time to access L2 and memory in a configuration like CPU->L2 and CPU->memory. $\endgroup$ – mahmood Nov 26 '18 at 19:07
  • $\begingroup$ Miss penalty mean extra spent time beyond the time spent on checking and missing the faster caches. $\endgroup$ – John L. Nov 26 '18 at 19:11
  • $\begingroup$ So, for includes you are saying that t1=10, t2=20 means that the time to access L2 includes the time to access L1. Therefore, for a CPU->L2 configuration a t2' should be less than 20. Right? $\endgroup$ – mahmood Nov 26 '18 at 19:19
  • 1
    $\begingroup$ @anir, I believe I have said enough on my answer above. The access time for L1 in hit and miss may or may not be different. Above all, either formula can only approximate the truth and reality. I will let others to chime in. $\endgroup$ – John L. Dec 27 '19 at 14:21
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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