[toc]
# Dynamic Scheduling
## Hazard
首先 講到dynamic scheduling 就必須要提到hazard。
首先 有幾中harzard WAR, WAW, RAW

Data Dependency

RAW（Read After Write）:
fadd.d f6, f0, f8   # f6 ← f0 + f8
fsub.d f8, f6, f2   # 需要 f6 的結果，但上一行尚未寫回

lw x5, 0(x1)        # 從mem load data to x5
add x6, x5, x2      # 需要 x5 的值，但前 load 尚未完成

Anti Dependency

WAR :
f8 in 
fadd.d f6, f0, f8
fsub.d f8, f10, f14

lw x5, 0(x1)        # 讀取mem (x1)
sw x1, 0(x2)        # 寫回 x1 

Output Dependency

WAW :
f6 in 
fadd.d f6, f0, f8
fmul.d f6, f10, f8

sw x5, 0(x1)        # 把 x5 寫到mem
sw x6, 0(x1)        # 接著又寫到same address

其中 RAW 在5-stage pipeline CPU 中需要處理 例如 bypassing 或是藉由store 來將它處理掉。(在軟體層面，我們可以藉由 Code Reordering 來將處理)

但是，假設以下得指令

sw r2, 8(r1)     # store value of r2 to memory address (r1 + 8)
ld r6, 24(r3)    # load value from memory address (r3 + 24)

如果在執行的時候，(r1 + 8) 和 (r3 + 24) 其實指向相同的記憶體位址，那這兩條指令之間就存在一個 RAW hazard。

然而，在 compile 時期，Compiler 並不知道 r1 與 r3 的值，因此無法得知這兩條指令是否會存取同一個位址，也就無法預先偵測或避免這種 hazard。

同時，對於WAW 跟 WAR，他們在in order execution 其實不需要特別留意。(不過在ooo的時候就必須要注意了)

但是，想像一下一個前一個指令是lw，我們只能等待他從mem讀取資料，在這種情況下面，需要長時間的stall來等到data ready才能繼續後面的instruction。

## Out of order
因此，我們希望在 execution 的時候，可以先處理一些「可以執行」的指令，而不必等所有前面的指令都完成。這樣能提高 pipeline 的利用率，減少等待資料的時間。

(前面提到的waw, war hazard 就會變成一個問題，你會發現他們執行的順序還是重要的，我們需要去保證他們在out of order執行的時候也要保證他的正確性)

（圖為 Out-of-Order CPU 的概念圖）

可以發現，我們在 Decode 階段之後，必須多做一些事情，例如：
* dependency check
* register renaming
* 將指令放入 Issue Queue 或Reservation Station 中等待執行

### Live cycle of an instruction
在 In-Order Pipeline 中，一條指令的生命週期大致為：

issue -> exe -> commit

改成 Out-of-Order Execution 後
在 Out-of-Order 架構中，指令之間的執行順序可以不同，因此生命週期需要更細分。
常見的順序如下：

Issue → Execute → Write Result → Commit

## OOO execution (scoreboading)

一言以蔽之 對於hazard來說，scoreboarding分別在這幾個stage處理完


* 在 Issue stage 不讓 WAW 進去
* 在 Read operand 讓 RAW 處理完
* 在 Write Result 處理 WAR


想像一下，假設我們今天要execute out of order，最重要的事情就是我們要知道就當前的cycle來說 哪些instruction 可以被執行。我們需要考慮的有以下幾點事情
1. Is the required function unit available?
2. Is the input data available? (RAW)
3. Is it safe to write the destination? (WAR? WAW?)
4. Is there a structural conflict at the WB stage?

在 CDC6600 總共有 16 separate functional units, 包含了
* 4 floating-point units,
* 5 units for memory references
* 7 units for integer operations.

### Life cycle of instruction for scoreboarding
在scoreboarding裡面，instruction總共有四個步驟
issue -> read operands -> Execution -> Wrtie result

Issue:
一個Instruction可以被issue的話他必須要滿足幾個條件
1. 有functional unit
2. 沒有WAW，假設有我們就<span style="color:red"> **stall** </span> (這也是之後的進步的地方)
3. 在stall的時候 if stage還是會把 instr 放到buffer until it's full

Read Operand:
1. Scoreboard monitors 會持續地看source operand 有沒有滿足有的會就執行。 (在這部會處理RAW)

Execution:
1. 正常的execution 並且會在結束的時候去notify scoreboard

Write Result:
1. With WAR hazard

fadd.d f6, f0, f8
fsub.d f8, f8, f14

在這邊，fadd.d 會需要讀取f8，但因為out of order，假設fsub.d 先被執行了，scareboard會一直<span style="color:red"> **stall** </span>直到fadd.d read到operand。

注: scoreboarding不會bypass!

Example 自己看
https://csg.csail.mit.edu/6.5900/Lectures/L06.pdf

https://www.youtube.com/watch?v=TJcNJh8tS6w

### DrawBack of scoreboarding
1. 沒有forward (raw)
2. <span style="color:red"> **stall** </span> 很多 其實 (war 跟 waw)可以藉由renaming來完成
3. <span style="color:red">Centralized </span> Hazard detection.

## OOO execution (Tomasulo)

相較於scoreboarding，tomasulo 有以下幾點improve
1. 使用了更distribute的hazard detection (revervation station level)
2. 使用了register renaming 來處理 WAW 跟 WAR，因此不需要再做額外的stall (in reservation station)


我們來先講一下他怎麼處理hazard的
* WAW and WAR hazard : Register renaming in <span style="color:red"> **reservation stations** </span> (in issue state)
* RAW hazard: Delaying instruction execution until all the operands are available.

他有一個特點
<span style="color:red">no instruction is allowed to initiate execution until a branch that precedes the instruction in program order has completed</span>
(why?)
:::spoiler
Because no concept of program order is maintained after the issue stage, this restriction is usually implemented by
preventing any instruction from leaving the issue step if there is a pending branch already in the pipeline.
:::

### Core component
Reservation Station:

Reservation station <span style="color:red"> fetches and buffers an operand as soon as it is available</span>, eliminating the need to get the operand from a register.

Reservation station 總共有七個field
分別為Op, Vj, Vk, Qj, Qk, A, Busy

<span style="color:red">對於任意的j,k 他們只會有其中一個 Qj, Vj 有值 </span> 可以看上圖

Instruction status

Register status:
Qi: 哪條指令的 result 會寫進去這個 register

### How the reservation station remove WAW & WAR

1. fld f6,32(x2)
2. fld f2,44(x3)
3. fmul.d f0,f2,f4
4. fsub.d f8,f2,f6
5. fdiv.d f0,f0,f6
6. fadd.d f6,f8,f2

#### WAR

假設我們 issue 這些指令時，第 5、6 條看起來有 WAR hazard。若會出問題，只會有一件事：<span style="color:red">fdiv.d 讀到 fadd.d 寫回 f6 的新值</span>。但這永遠不會發生，原因如下：

1. **Tomasulo 不從暫存器讀資料**
fdiv.d 需要的 f6 不是直接從 register file 讀，而是從 RS 的 Vj/Vk 或 tag（Qj/Qk）取得。
→ 所以不會誤讀 register 中被 fadd.d 覆蓋的值。

2. **若 f6 的值已經計算完成(第一個instr 已經完成了)，RS 會直接保存該值**
fdiv.d 在 issue 時已拿到正確的 f6（存到 Vk），之後與暫存器無關。

3. **若 f6 還沒準備好，fdiv.d 會記住提供者的 tag**
Qk 指向 load 或前一個 RS，等待 CDB broadcast。
→ fdiv.d 不會因 fadd.d 寫 f6 而提早讀錯資料。

因此，即使 fadd.d 先寫回 f6，也完全不會影響 fdiv.d 的 operand，WAR hazard 被自然消除。

#### WAW

其實蠻像的，所以不展開。

### Life cycle of instruction for Tomasulo
Tomasulo，instruction總共有三個步驟
issue -> Execution -> Wrtie result

請自行看example，這邊不展開了。

Example 請看 :
https://drive.google.com/file/d/1EzdwLdD4kEhS6hFt4-dSq1lDbYEuRPnl/view?usp=sharing

有幾個重點
1. <span style="color:red">Notice that all writes occur in Write Result, whether the destination is a register or memory. </span>
2. The performance can also be limited by the single CDB. (Common Data Bus 每個cycle只會傳有限比的資料)

### DrawBack
1. If more than one instruction is ready for a single functional unit, the unit will have to choose among them.
2. Commit arbitary <span style="color:red">(imprecise exception)</span>
3. Without speculation, processors must stall on branches because the next PC is unknown.

我們需要precise exception，Precise exception的意思就是假設我們今天執行到假設第五條指令並且發現錯誤，後面執行到的指令必須要rollback，前面沒有執行到的指令必須要繼續執行。但因為tomasulo是arbitary commit，所以會出問題。

## OOO execution (Speculation)

相較於Tomasulo，在speculation裡面我們新增了reorder buffer 讓我們可以<span style="color:red"> commit in order</span>。

然後 commit the results only if prediction was correct

**說重點:**
* 多加了一個reorder buffer
* 我們會在reservation station裡面多加 destination 同時我們原本的operand Qk,j 之類的都會從 <span style="color:red">reorder buffer</span> 拿，然後execute完之後也是寫到 <span style="color:red">reorder buffer</span>
* 我們的register從原本的instruction的tag變成 <span style="color:red">reorder buffer</span> 的tag


### Core component
Reorder Buffer:
* 跟issue一樣，是一個FIFO的structure。
* 只有在complete的時候會把ROB的東西寫到register跟memory

Register status:
從原本的instruction變成instruction的編號，

Reservation station:
多了一個Destination

### Life cycle of instruction

這篇寫得很好
https://zhuanlan.zhihu.com/p/501631371

Issue → Execute → Write Result → Commit

Issue :
* Issue 跟原本的Tomasulo 很像 唯一不一樣的地方是他同時會看rob有沒有滿，只有在reorder buffer跟 reservation station都有位置的時候才會issue，否則就是 <span style="color:red">structural hazard</span>。

Execute:
* 也是一樣等到Data都好，跟之前的很像 也是藉由這個階段解決RAW Hazard
* Load 仍需要 兩個步驟：
1. 計算有效位址 EA(effect address) → 2. memory access
* Store 在此階段僅做 EA 計算（資料部分等後續 CDB）

Write Result:
* 等compute好了之後，把資料用CDB來broadcast給很多東西(ROB 跟Rs)
* RS entry 被標記為 free
* Store 特殊處理：
* 如果 store 的 data 已經 ready → 寫入 ROB 的 Value
* 若尚未 ready → store 會持續監聽 CDB，直到 data 被 broadcast

Commit :
有三種情況 依 ROB 順序：
* Normal：寫回暫存器
* Store：寫記憶體
* Branch mispredict：flush ROB、重啟 pipeline

## Draw Back
太多同一筆資料存在不同地方