1. Early restart, Critical Word First

• CPU normally needs just one word of the block at a time. Don’t wait for full block before restarting CPU
• Early restart — As soon as the requested word of the block arrives, send it to the CPU and let the CPU continue execution
• Critical Word First —Request the missed word first from memory and send it to the CPU as soon as it arrives; let the CPU continue execution while filling the rest of the words in the block
• Long blocks more popular today -> Critical Word 1st Widely used

---

1-6 is not on EXAM

---

from now on it's in exame

2. Merging Write Buffers

A write buffer removes most of the time the CPU would otherwise spend waiting on writes. A merging write buffer (also called write merging) makes it more efficient still. The exercise at the end builds on both.

A. Why a write buffer?

With a write-through L1, every store must also be written to the next level (L2 or memory), which is slow. Without help, the CPU would wait on every store.

A write buffer is a small queue between L1 and the next level:

1. On a store, the address and data are placed in the write buffer.
2. From the CPU's point of view, the write is finished, so it continues right away.
3. The buffer sends its entries to the next level in the background, oldest first.

The CPU waits only when the buffer is full.

B. The three cases on your slide

C. Write merging: how it works

Write merging OFF

---

Write merging ON

Each buffer entry holds a whole block's worth of space, for example 4 words of 8 bytes, with a valid bit per word. When a new store arrives, the buffer checks: does a valid entry already cover this address?

• Yes: put the word into that entry and set its valid bit (merge).
• No: use a new entry.

Without merging, each store takes its own entry even when the stores are to neighboring addresses, so the buffer fills up quickly.

In the simulator below, the stores come faster than the buffer can drain. Run the same 9 stores with merging off, then on, and compare the stalls.

D. Why write merging helps (common exam question)

1. Fewer stalls. Neighboring stores share one entry, so the buffer fills up more slowly.
2. Fewer, more efficient writes to the next level. Sending one entry with 4 words uses the memory bus better than 4 separate one-word writes, since each transfer pays the setup cost only once.
3. Better use of buffer space. Without merging, each entry holds one word and the rest of its space is wasted.

Two more points worth knowing:

• Reads must check the write buffer. A load may want data that is still sitting in the buffer and not yet in L2. The cache either checks the buffer for a matching address or waits for the buffer to drain, so the load doesn't read a stale value.
• I/O addresses are not merged. Writes to device registers must each happen separately and in order.

Exercise: write time with a write-through L1

L1 is write-through. 95% of the time the store can go into the write buffer; 5% of the time the buffer is full. How do you compute the write time?

Step 1: Identify the two cases

Case A, buffer has space (95%): the store goes into L1 and the buffer, and the CPU continues. The time is just the L1 write time, the L1 hit time.

Case B, buffer is full (5%): the CPU must wait until an entry is written to L2 and freed. That wait is the time to write one entry into L2, including L2 misses:

T_L2write = hit time L2 + miss rate L2 × miss penalty L2

Step 2: Combine with the probabilities

Write time = 0.95 × T_L1  +  0.05 × (T_L1 + T_L2write)
           = T_L1 + 0.05 × T_L2write

Every store pays the L1 time, and 5% of stores also pay the full drain time.

If the question asks for stall time only (as in the earlier homework):

Write stall time = 0.95 × 0 + 0.05 × T_L2write

Step 3: Plug in numbers (from your earlier problem)

L1 hit time = 1 ns, L2 hit time = 15 ns, L2 local miss rate = 20%, L2 miss penalty = 150 ns.

T_L2write = 15 + 0.20 × 150 = 15 + 30 = 45 ns

Write time        = 1 + 0.05 × 45 = 1 + 2.25 = 3.25 ns
Write stall time  = 0.05 × 45     = 2.25 ns

Step 4: Exam traps

• Read the question for what to include. "Stall time only" → 2.25 ns. "Write time to L1" including the access → 3.25 ns. Show the formula so you get credit either way.

• The waiting time depends on the stated assumption. In your homework, the store arrives just as the buffer starts writing an entry to L2, so it waits the entire 45 ns. If a problem instead says a store arrives at a random point during the drain, the average wait would be about half of that. Use exactly what the problem states.

• The L1 miss rate is not used for writes when the L1 is write-through, no-write-allocate. Every store goes into the buffer whether it hits or misses in L1. If a problem says write-allocate, write misses would also pay an L1 miss penalty.

• Don't forget the L2 miss part of T_L2write. Using only the 15 ns L2 hit time (giving 0.05 × 15 = 0.75 ns) is a common mistake. L2 is write-allocate, so 20% of buffer writes miss in L2 and pay the 150 ns.

AMAT

The notes write miss_rate(RLL + %dirtyD), which means miss_rate × (RLL + %dirty × D).

The one idea behind every equation

AMAT = (time every access pays) + Σ (how often an extra event happens) × (how long it takes)

Every access pays its hit time (RH or WH). Then you ask which extra trips to the lower level this access can cause, and how often each one happens. There are only four possible trips:

1. Fetching a block (RLL). Happens when a miss brings the block into the cache. Reads always do this. Writes do it only with write-allocate. It happens only on misses, so it is multiplied by miss_rate.

2. Writing back a dirty victim (D). When a block is brought in, another is thrown out. Only write-back caches have dirty blocks, so D appears only for write-back, only inside the miss term, and only %dirty of the time.

3. Sending a write down (WLL).

• Write-through: every write goes down, hit or miss, so WLL is added without miss_rate.
• Write-back + no-write-allocate: hits stay in the cache, but a write miss goes straight down, so the term is miss_rate × WLL.

4. Write buffer → multiply each write-down cost by (1 − %wb). The buffer absorbs outgoing writes, so the CPU waits only when it is full. This applies to WLL and D only, never RLL. A buffer can hold data going out, but it can't make data come in faster.

---

Reads: only two versions

A read miss always brings the block in, whatever the write policy. Write-allocate vs. no-allocate decides what happens on write misses only, so it never changes the read formula. Only one thing matters for reads: can the replaced block be dirty?

Write-back + no-write-allocate still has the dirty term. No-allocate only means write misses don't bring blocks in. Write hits still mark blocks dirty, so a later read miss can evict a dirty block.

---

Writes: four versions, one at a time

Write-through + write-allocate: WH + WLL + miss_rate × RLL

• Every write goes to the cache (WH) and down to the lower level (WLL), hit or miss.
• On a write miss, the block is also fetched first (miss_rate × RLL), because of allocate.
• No D: write-through blocks are never dirty.

Write-through + no-write-allocate: WH + WLL

• Every write goes down (WLL), hit or miss.
• On a miss, the block is not fetched, and the write just goes down. That is the same WLL already counted, so a miss costs nothing extra and the formula has no miss_rate at all.

Write-back + write-allocate: WH + miss_rate × (RLL + %dirty × D)

• A write hit stays in the cache and marks the block dirty (just WH).
• A write miss behaves exactly like a read miss: fetch the block (RLL), possibly evicting a dirty victim (%dirty × D), then write into it.
• That's why it's identical to the write-back read formula, with WH in place of RH.

Write-back + no-write-allocate: WH + miss_rate × WLL

• A write hit stays in the cache (just WH).
• A write miss sends the write straight down (WLL) and does not fetch the block.
• No RLL (nothing fetched) and no D (nothing evicted).

---

Adding a write buffer: one rule

The write buffer only affects writes going down. Find every WLL and D term and multiply it by (1 − %wb). Leave RH, WH, and RLL alone.

That turns all 8 buffer formulas from your notes into the 8 non-buffer ones with one change each. For write-through reads nothing changes at all, since there is no WLL or D in them.

Where (1 − %wb) comes from: with probability %wb the write drops into the buffer and the CPU waits 0. With probability (1 − %wb) the buffer is full, and the CPU waits the whole write time:

%wb × 0 + (1 − %wb) × WLL = (1 − %wb) × WLL

---

Patterns to check your answer

질문 ① 미스 때 블록을 가져오나? → miss_rate × RLL

• 읽기 미스는 항상 가져옴
• 쓰기 미스는 write-allocate일 때만 가져옴

질문 ② 블록을 가져올 때, 밀려나는 블록이 dirty일 수 있나? → + %dirty × D (미스 항 안에)

• write-back일 때만 해당. write-through는 원본이 항상 최신이라 dirty가 없음

질문 ③ 쓰기가 아래로 내려가나? → WLL

• write-through: 쓰기마다 항상 → WLL (miss_rate를 곱하지 않음)
• write-back + no-allocate: 쓰기 미스일 때만 → miss_rate × WLL

질문 ④ 쓰기 버퍼가 있나? → WLL과 D 앞에 (1 − %wb)

• 우편함에 자리가 있으면(%wb) 기다림 0, 꽉 차면(1 − %wb) 끝까지 기다림
• RLL에는 절대 붙이지 않음. 우편함은 "보내는 것"만 도와주고, "가져오는 것"은 빨라지게 못 함writes going down (WLL, D), never RLL.

Write through + write allocate
- Read AMAT = RH + miss_rate*RLL
- Write AMAT= WH + WLL + miss_rate*RLL

Write through + no write allocate
- Read AMAT = RH + miss_rate*RLL
- Write AMAT = WH + WLL

Write back + write allocate
- Read AMAT = RH + miss_rate*(RLL+%dirty*D)
- Write AMAT = WH + miss_rate*(RLL+%dirty*D)

Write back + no write allocate
- Read AMAT = RH + miss_rate*(RLL+%dirty*D)
- Write AMAT = WH + miss_rate*WLL

Write through + write allocate + write buffer
- Read AMAT = RH + miss_rate*RLL
- Write AMAT= WH + (1-%wb)*WLL + miss_rate*RLL

Write through + no write allocate + write buffer
- Read AMAT = RH + miss_rate*RLL
- Write AMAT = WH + (1-%wb)* WLL

Write back + write allocate + write buffer
- Read AMAT = RH + miss_rate*(RLL+%dirty* (1-%wb)* D)
- Write AMAT = WH + miss_rate*(RLL+%dirty* (1-%wb)* D)

Write back + no write allocate + write buffer
- Read AMAT = RH + miss_rate*(RLL+% dirty* (1-%wb)* D)
- Write AMAT = WH + miss_rate* (1-%wb)* WLL