Cache access time for write back and write through caches

Question

I was solving exercise questions on caching from the book Computer Organization and Architecture by William Stallings. The exercise has following question:

The performance of a single-level cache system for a read operation can be characterized by the following equation:

$$T_a = T_c + (1-H)T_m$$

where T_a is the average access time, T_c is the cache access time, T_m is the memory access time (memory to processor register), and H is the hit ratio. For simplicity, we assume that the word in question is loaded into the cache in parallel with the load to processor register.

a. Define T_b= time to transfer a line between cache and main memory, and W= fraction of write references. Revise the preceding equation to account for writes as well as reads, using a write-through policy.
b. Define W_b as the probability that a line in the cache has been altered. Provide an equation for T_a for the write-back policy.

The solution given was:

a. $$T_a = T_c + (1 – H)T_b + W(T_m – T_c)$$ b. $$T_a = T_c + (1 – H)T_b + W_b(1 – H)T_b = T_c + (1 – H)(1 + W_b)T_b$$

Doubts

1. Shouldnt it be: $$T_a = T_c \color{red}{\times H}+ (1-H)(T_m\color{red}{+T_c})$$? I felt "× H" is required because its during cache hit, when we do only cache access. Also we need "+ T_c" represents cache access time during cache miss.

2. I know what is write through and write back caches. In write through cache, both main memory and cache are simultaneously updated and in write back cache only modified cache word is copied to main memory when that word is to be replaced with other one from main memory. I also understand why we replaced T_m with T_b. However I am not able to understand how above equations have be arrived. Can someone explain how those formulae were come up? How those two terms involving W make sense.

Answer 1

Unless you did it intentionally, you can see how your edited equation is equivalent to the one they provided. Instead of separating cache access time between a hit and miss as you have done, they have taken it unified as \$T_c\$. Then it doesn't need to be accounted for when calculating memory access time

Answer 2

1. Yes, you are right when you say that the average access time is

$$T_a = T_c \times H + (1-H)(T_m+T_c)$$

but the original formula

$$T_a = T_c + (1-H)T_m$$

is also right -- both formulas are always mathematically equal.

In words, your formula is saying that during a hit, the total time is \$T_c\$, but during a miss, the total time is \$T_c + T_m\$.

In words, the original formula is saying that a memory read has two phases, the first takes \$T_c\$ time no matter if it's a read or a write; the second phase can be skipped on a hit but when there's a miss it takes an additional \$T_m\$ time.

Those are two different ways of saying the same thing.

2. a. To get the average memory access time, we need to combine the times for all three cases of this write-through cache.

Assuming the hit rate is the same for both reads and writes:

• access time there is a hit on a read = \$Tc\$ (but this only happens (H)(1-W) of the time)
• access time when a read misses the cache = \$T_c + T_b\$ (check the cache, and then do a full line read from memory) (but this only happens (1-H)(1-W) of the time)
• access time when a hit on a write = \$T_c + T_m\$ (read a full line from cache, modify it with the byte / short / register written, and then write it back to memory) (but this only happens (H)(W) of the time)
• access time when a write to a location not cached = \$T_c + T_b + T_m\$ (check the cache, and when that misses, read a full line from memory, modify it with the byte / short / register written, and then write it back to memory) (but this happens (1-H)(W) of the time)

If we write separate terms for \$T_c\$, \$T_b\$, and \$T_m\$ and (to get the average access time) multiply them by how often they happen, we get

$$T_a = T_c \times ( (H)(1-W) + (1-H)(1-W) + (H)(W) + (1-H)(W) )$$ $$+ T_b \times ( (1-H)(1-W) + (1-H)(W) )$$ $$+ T_m \times ( (H)(W) + (1-H)(W) ) $$

which can be simplified to:

$$T_a = T_c + T_b \times (1-H) + T_m \times (W) $$

In other words, the time to check the cache \$T_c\$ affects every access, the time to load a line of cache from main memory \$T_b\$ affects only and every cache miss (whether it's a read or a write), and the time to write to memory \$T_m\$ affects only and every write (whether it's a hit or a miss).

2. b. In a write-back cache, there's generally 3 phases:

• First we check for a hit, which takes \$T_c\$ time (this happens every time, no matter if there is a read or a write, hit or a miss), and we check if the cache line is dirty. If there is a hit, we're done. (If it's a write, we update the value in the cache during this time).
• If there is a miss, and the line in the cache that we're about to replace is dirty (which happens \$(W_b)(1-H)\$ of the time), then we also we need to write out the dirty cache line (to whatever address is stored in its tag, which is not the desired address of the current instruction) with additional \$T_b\$ time, before we read in the new data. (It doesn't matter if this is a read or a write).
• If there is a miss (\$(1-H)\$ of the time), whether or not we previously write out dirty data, we need to read the desired line into cache (from the desired address of the current instruction), which takes additional $\T_b$ time (and happens (1-H) of the time). (It doesn't matter if this is a read or a write).

If we write separate terms for each phase and (to get the average access time) multiply them by how often they happen, we get

All 3 phases combined give: $$T_a = T_c + T_b \times (W_b)(1-H) + T_b \times (1-H) $$

This can be simplified to $$T_a = T_c + T_b \times (W_b+1)(1-H) $$