0
\$\begingroup\$

I was solving exercise from William Stallings book on Cache memory chapter. The problem was:

For a system with two levels of cache, define Tc1 = first-level cache access time; Tc2 = second-level cache access time; Tm = memory access time; H1 = first-level cache hit ratio; H2 = combined first/second level cache hit ratio. Provide an equation for Ta for a read operation.

The solution given was:

$$T_{a} = [T_{c1} + (1 – H_{1})T_{c2}] + (1 – H_{2})T_{m}$$

I am not able to get this. Shouldn't it be

$$T_{a} = \color{red}{H_{1}}T_{c1} + (1 – H_{1})(T_{c2}+\color{red}{T_{c_1}}) + (1 – H_{2})(T_{m}\color{red}{+T_{c2}+T_{c_1}})$$

The reason for H1 is that its the probability with cache hit occurs. We cannot simply add L1 access time.

The reason for Tc1 is that we have already accessed L1 cache before accessing L2 cache, when L1 cache miss occurs.

The same is the reason for Tc1 + Tc2. We have already accessed L1 and L2 cache before accessing main memory cache, when L1 and L2 cache miss occurs.

Am I wrong with my equation or the book is wrong?

\$\endgroup\$
0
\$\begingroup\$

You MUST always access the L1 cache before you know if you have a hit or miss.

(Edited)
All misses then go to the L2 cache after which you know if you had an L2 hit or miss etc.

Note that

$$\color{red}{H_{1}}T_{c1} + (1 – H_{1})(T_{c2}+\color{red}{T_{c_1}})$$

Equals.

$$T_{c1} + (1 – H_{1})(T_{c2})$$

So the first part of your formula agrees with the book. The last part does not. But following reasoning leading to the first two terms the third term should look as the book says.


Multiply out the second term:

$$\color{red}{H_{1}}T_{c1} + (1 – H_{1})(T_{c2}+\color{red}{T_{c_1}}) <=>$$

$$\color{red}{H_{1}}T_{c1} + (1 – H_{1})T_{c2}+(1 – H_{1})\color{red}{T_{c_1}} $$

And $$\color{red}{H_{1}}T_{c1} + (1 – H_{1})T_{c1} <=> $$ $$\color{red}{H_{1}}T_{c1} + T_{c1} – H_{1}T_{c1} <=> $$ $$ T_{c1} $$

I apologize, My comment about the third terms was a bit cryptic.

We should count the full L1 cache (hit and miss): $$T_{c1}$$ All the remaining accesses (which are all the misses from L1) go to the L2 cache: $$(1 – H_{1})T_{c2}$$ Following the same logic, all the remaining accesses (which are all the misses from L2) go to the main memory: $$(1 – H_{2})T_{m}$$

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ I am not getting how you are saying those two equations you stated are same. How those variables in red color can be omitted? Does that have something to do with first two sentences of your answer? If yes, I am able to understand those two sentences, but not able to understand how those two sentences allow us to omit those red variables. Also didnt get what you said about third term. You said "third term should look as the book says". But the third term $(1–H_2)(T_m+T_{c2}+T_{c1})$ is not simply there in book's equation. \$\endgroup\$ – anir Dec 20 '18 at 20:23
0
\$\begingroup\$

As @Oldfart answered, the logic

We should count the full L1 cache (hit and miss): $$T_{c1}$$ All the remaining accesses (which are all the misses from L_1) go to the L2 cache: $$(1–H_1)T_{c2}$$

does indeed yield simplified version of equation: $$H_1T_{c1}+(1-H_1)(T_{c1}+T_{c2})$$

However, I feel the equation I specified:

$$T_{a} = {H_{1}}T_{c1} + (1 – H_{1})(T_{c2}+{T_{c_1}}) + (1 – H_{2})(T_{m}{+T_{c2}+T_{c_1}})$$

is wrong as it does not gets simplified to the books equation:

$$T_{a} = [T_{c1} + (1 – H_{1})T_{c2}] + (1 – H_{2})T_{m}$$

The mistake was that I cannot just have term: $$ (1 – H_{1})(T_{c2}+{T_{c_1}}) $$

I have to consider the probability that L2 hit occurs, which is what I missed. Note that H2 is combined probability of L1 and L2 hit. So if I use H2' as probability of (only) L2 hit, then by principle of inclusion and exclusion:

$$H_2=H_1+H_2'-H_{1}H_2'$$ Thus,

$$H_2'=\frac{H_2-H_1}{1-H_1}$$

Thus the equation I specified in the question should have been

$$\require{enclose}$$

$$T_{a} = {H_{1}}T_{c1} + \enclose{updiagonalstrike}{(1 – H_{1})}\frac{H_2-H_1}{\enclose{updiagonalstrike}{1 – H_{1}}}(T_{c2}+{T_{c_1}}) + (1 – H_{2})(T_{m}{+T_{c2}+T_{c_1}})$$

$$=\color{red}{\enclose{updiagonalstrike}{H_1T_{c1}}} +\color{blue}{\enclose{updiagonalstrike}{H_2T_{c1}}} +\color{green}{\enclose{updiagonalstrike}{H_2T_{c2}}} -\color{red}{\enclose{updiagonalstrike}{H_1T_{c1}}} -H_1T_{c2}+T_{c1}+T_{c2}+T_m -\color{blue}{\enclose{updiagonalstrike}{H_2T_{c1}}} -\color{green}{\enclose{updiagonalstrike}{H_2T_{c2}}} -H_2T_m $$

$$ =T_{c1}+(1-H_1)T_{c2}+(1-H_2)T_m $$ This last equation is what the book comes up with directly.

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