# Scenario

想像你現在是飯店打掃員工，你負責的是「清洗床單」的工作，內容有三個階段：洗床單，脫水，晾床單。

此時你手邊就只有一台洗衣機、一台脫水機、一個晾衣架，但是你負責了整整一棟飯店，此時你有兩種做法：

## Sequential

你可以先洗完一間房間的床單，可能花個 10 分鐘，接著再去把床單脫水，可能花個 10 分鐘，最後是晾床單，可能需要 10 分鐘。

這樣你一趟下來要 30 分鐘，如果一棟飯店有 200 間房間，你就要花 6000 分鐘才可以收工。

## Pipeline

聰明的想到說，如果洗完一個床單後，確實是要接著給他脫水，但我們還可以同時去洗第二個床單。

第一個床單脫完水，除了要拿去晾，第二個床單也可以接著脫水了，第三個床單也可以洗了。

假設你的移動速度飛快可以不用計算，則每個 10 分鐘為一個階段 epoch ，並且因為使用了 Pipeline 技術，所以每個 10 分鐘都有工作再進行，完美的利用了每個 10 分鐘。

因此總共時間就是 2000 分鐘，但是要加上最後一項工作的最後兩個階段，所以是 2020 分鐘。

## Time Consume

我們來比較兩者的時間差異，假設有 n 個床單要洗，總共有 m 個階段，並假設都 10 分鐘。

序列需要花：

$$
n\times m\times 10 = O(nm)
$$

Pipeline 需要花：

$$
n\times 10 + (m - 1)\times 10 = O(n+m)
$$

如果 m 是某個常數，當 n 很大的時候，Pipeline 的效率會比 Sequential 快了 m 倍。

當中 $(m - 1)\times 10$ 的部分又叫做「drain the pipeline」，也就是把管子抽乾的部分。

## 特點

- Pipeline 並沒有改變原本一份工作的時間 / Latency，但是增加了 Throughput
- 也就是每個 10 分鐘都做好做滿
- 多項工作可以同時進行，因為一份工作內在不同階段需要的資源不一樣
- 所以如果需要的資源是一樣的，那麼就會發生「hazard」
- 會被最慢的階段所影響
- 不平衡的工作階段長度會降低 Pipeline 的效果
- 假設剛剛的脫水需要 1 小時，那麼就算洗好床單了，也無法緊接著脫水，要等上一輪的脫完水

因此對於 Pipeline 的時間花費，假設每個階段時常不一樣，時間所花公式會變成：

$$
n\times max(\text{epoch time}) + (m - 1)\times \text{epoch time}
$$

所以 CPU 的 Pipeline 會盡量讓一個指令的每個階段，時間長度要是接近的；而這個階段，就是我們之後的 cycle。

<iframe src="https://drive.google.com/file/d/1OF-BV1H_1vKz5JzdEBcK4lHR3OegW-Ur/preview" height="480"></iframe>

所以回顧上周的圖，Inst Fetch、Ref Access 這些就是上面提到的「階段」，上週是以執行時間最長的作為一個 cycle，這裡我們將每個階段所花時間最大者設為一個 cycle。

<iframe src="https://drive.google.com/file/d/1rpVKmONH6tvhVgteQKD0YgpCtZ4rVtVv/preview" height="380"></iframe>

我們從 single cycle 邁入了 multi cycle。

# RISC V 的特性

1. 因為指令長度都一樣，所以 fetch 跟 decode 都可以很容易在 one cycle 達成
- X86 因為 cycle 長度不一樣所以要達到 one cycle 會更複雜
3. 因為有著固定的格式，像是 rs1 都固定在同個位置，所以 REG 的讀取可以做到 1 cycle
4. Load 跟 Store 也都因為固定了格式，且只需要做簡單的地址偏移，所以分別只需要 3 跟 4 個 cycle

---

# Pipeline Hazard

上面都是完美的情況，但是實際上，會因為發生一些事情而不完美。

# Structural Hazards

:::warning
如果今天你只有一台洗衣兼脫水機，那麼你洗了第一個床單就不能洗第二個床單
:::

當同個 cycle 內，有兩條以上指令需要用相同的資源，例如記憶體，就會發生 Structural Hazards。

<iframe src="https://drive.google.com/file/d/1mU7HktYLpx24iCi3HyaRIiziGY1uLJX3/preview" height="580"></iframe>

例如上圖中，Load 跟 Instr3 都需要讀取記憶體(藍色在右)，但是記憶體只有一個，此時就屬於使用相同資源。

## 解法一：Stall

就是等待。

等待是處理 Hazards 的通解，但是通常來說會讓效率變很差，因此非不得已才用。

## 解法二

修改結構。

<iframe src="https://drive.google.com/file/d/1arOu3h0opFxkW5Vs-rlfLrPW8Vk2ug-s/preview" height="480"></iframe>

例如剛剛的記憶體，Load 需要讀的是資料區域的記憶體，但是 Instr3 讀取的是指令的記憶體，所以現實中會把記憶體區分成兩個區域，一個放指令，一個放資料，這樣兩個區域就可以獨立進行了。

# Data Hazards

這跟 「Dependencies」 有關：在一連串的指令中，使用到==相同的 REG==。

如果 Dependencies 發生，並且，後者要使用該 REG 時，資料已經寫入完成，就沒有 Data Hazards；反之，就會有 Hazards。

<iframe src="https://drive.google.com/file/d/1BqNn1oboDFAHPtyad5yP0o0rFrN_wsK0/preview" height="480"></iframe>

例如上面的圖中，第一個 Add 存入的 REG 會被接下來的 4 個指令使用，此時 Pipeline 會導致接下來的 sub, and 跟 or 都會出問題，因為那時候資料尚未寫入，xor 則沒事。

不過可以發現 or 指令跟寫入是發生在同個 cycle，這時候就看 ISA 怎麼處裡的，有些可能會更動寫入跟讀取的順序，先寫入再讀取，or 指令在這裡就不會發生 Hazards。

## 解法一：Forward

就是看能不能在寫入之前，先拿取計算好的內容過來。

<iframe src="https://drive.google.com/file/d/1CIFP5Cn-STXsTSGlc3wZ1mXYXRb5OT20/preview" height="480"></iframe>

像上圖中， Add 的結果在第 3 個 cycle 就算好了，所以我們可以「神奇的」把它拿到第 4 個 cycle 或之後的 cycle 使用。

其手法是透過之後的「Latch」。

:::warning
- 要注意，能不能 forward 是要看該 cycle 的前一個 cycle，算好的值有沒有在 Latch 裡面。
- 例如第二條 sub 會在第 3 個 cycle 去取得 r1 的值，而 r1 的值在第 3 個 cycle 就會存在 ALU 跟 Dm 之間的 latch 裡面了，也就是 EX/MEM 裡面。
- and 在第 4 個 cycle 指令所拿取的 r1 也是存在 ALU 跟 Dm 之間的 latch。
- or 在第 5 個 cycle 指令所拿取的 r1 應該是存在 MEM/RB 裡面的 ALUout。
:::

## 解法二：Stall

但是有時候 forward 也不能解決，此時就真的要等待了。

<iframe src="https://drive.google.com/file/d/1PMXIe4sVW3XguD4okADshN15cKgRwI6P/preview" height="320"></iframe>

像上圖中，sub 在第 3 個 cycle 就要使用 REG 的內容了，但是 REG 的內容要等到第 3 個 cycle 結束才跑出來，這種就真的欲哭無淚了，乖乖等待。

這種的因為跟讀取指令有關，所以又叫 **Load-use data hazard**。

:::warning
- 那有沒有 Store-use data hazard 呢？理論上是沒有的，雖然 store 指令跟 load 指令一樣要到 MEM 階段才會把資料處理好(寫入記憶體)，但如果一個指令要用這個資料，必須要先 load 才可以，而一個 store 接一個 load 並不會怎麼樣：)
:::

:::info
- 可以注意到原因在於 load 指令的結果要等到第 4 個 cycle 才會送進 latch，時間上來說太晚了
- 一般的運算指令都是第 3 個 cycle 就有值了，因此就算下一個指令有 data hazard，也來的及送到該指令的第 3 cycle，或者說上一條指令的第 4 個 cycle
:::

## 解法三：Compiler

我們也可以在 Compiler 的層面就避免掉 Dependency：

$$
\begin{align}
&\text{lw \$t1, 0(\$t0)}\\
&\text{lw \$t2, 4(\$t0)}\\
&\color{red}{\text{add \$t3, \$t1, \$t2}}\\
&\color{red}{\text{sw \$t3, 12(\$t0)}}\\
&\text{lw \$t4, 8(\$t0)}\\
&\color{red}{\text{add \$t5, \$t1, \$t4}}\\
&\color{red}{\text{sw \$t5, 16(\$t0)}}\\
\end{align}
$$

可以發現紅色的地方都會發生 Dependency，或者畫成圖的話會長這樣：

<iframe src="https://drive.google.com/file/d/1S1vqA844uPgrB82XiNdmMIyyvDjZNSfy/preview" height="580"></iframe>

Mem 代表並沒有進行 Memory Access，橘色線代表可以 Forward，綠色則不行。

可以發現如果第 3 個 add 要做 forward，那就要往後一個 cycle，所以我們可以把下面的 ld 拉上來：

<iframe src="https://drive.google.com/file/d/1aVgm4k6wlT_h3lF5uhDtvaJX97-6kpdy/preview" height="580"></iframe>

這樣就可以避免掉 Hazard 了。

:::warning
可以注意到第一個 store 指令是存在 t0 + 12 這個位置，剛好錯開了下一行 load 指令需要的 t0 + 8 的值；如果這兩個指令有衝突，那麼就不能用換順序解決這個問題的。

:::

# Control Hazard

由 branch 所導致的，因為它會影響 PC 的值。

<iframe src="https://drive.google.com/file/d/1YNaWqtp7MANgpitvfVAcds95Le13Eq33/preview" height="380"></iframe>

例如上圖中，要不要 branch 最快也是在第 2 個 cycle 才出來(偷偷先做運算，不用 ALU)，此時下一條指令也應該要讀進來了，那到底要讀哪條指令？

## 解法一：Stall

<iframe src="https://drive.google.com/file/d/1hqDJ6XlZEED_VhkTk-6UfGESaJdtdWgz/preview" height="380"></iframe>

老樣子，會拖累太多速度，況且 branch 也是很長使用的指令。

## 解法二：多等一下並提早更新

就是用上面自己偷偷算的結果，送回去給 PC，讓他在第 3 個 cycle 可以成功更新成 branch 的地址

<iframe src="https://drive.google.com/file/d/1RuaM1Fum1PeX9PER3K_Jix1FxCzz44Ny/preview" height="380"></iframe>

但是因為 branch 是很長使用的指令，所以有了很有名的第三種解法。

## 解法三：分支預測

也就是用猜的。

<iframe src="https://drive.google.com/file/d/1ghKsK46c-tqVLuct8aCTbG8MvlxQtmok/preview" height="380"></iframe>

但是猜錯的話要記得 roll back，也就是停止執行錯誤的指令，這又叫 flush pipeline。

下圖是猜對的時候，我們就省了一個 cycle。

<iframe src="https://drive.google.com/file/d/112tv_Oz4UAg6jy0m-NvD9OS1pYT6upR8/preview" height="280"></iframe>

下圖是猜錯的時候，此時要記得 roll back，「神奇的」停止後面指令的執行。

<iframe src="https://drive.google.com/file/d/1kG_tINdEqD4S9oh-AYvurvKQqb04yY40/preview" height="250"></iframe>

預測有分兩種：

- 靜態預測
- 每次都猜 nontaken，也就是沒有分支發生，直到過了 1 個 cycle 後如果發現是需要分支的話，就 roll back ，停掉錯誤的指令，改執行正確的指令。
- 就執行方式來說 50 % 的機率會猜中，因此省了剛剛解法二等待的 1 個 cycle。
- 動態分支 dynamic scheme
- 會有一個專門的 hardware module 叫 branch predictor
- 他會根據過往的指令或紀錄來預測到底要不要分之。
- 這種解法的訴求是要比靜態的好，就好像 ML 訓練出來的 model 至少要比亂猜好。
- 通常來說是用狀態機來實作
---

# Pipeline Registers / Latch

<iframe src="https://drive.google.com/file/d/1PpBHcLdOTcQFXEffFqaBeH7n3EM7EAJ-/preview" height="380"></iframe>

剛剛提到的「神奇」解法，就是透過這個東西所達成的。

可以看到總共有四個 Latch，每個上面有一個代號：「A/B」，其中 A 是在他之前的指令，B 是在他之後的指令。

例如第一個 Latch 是「IF/ID」，也就是 Instr Fetch 跟 Instr Decode。

- EX：Execution
- MEM：Memory Access
- WB：Write Back Reg

這東西就像是個擋水閘，會把每個 cycle 得到的值先攔截，存在自己裡面，下一個 cycle 再放行到下一區域。

每個 Latch 都具有各自要儲存的東西，接下來以 Load 指令來做介紹。

下面會搭配 RTL 表示法，其中「Latch.Variable」的寫法，代表 Latch 裡面有 Variable 這個變數。例如 IF/ID.IR 就是 IF/ID 這個 Latch 裡面有 IR 這個變數。

# IF Stage

$$
\displaylines{
\text{IF/ID.IR = mem[PC]}\\
\text{IF/ID.PC = PC ;}\\
\text{PC = PC +4;}\\
}
$$

首先，IF/ID 存了 IR 跟 PC，因為要把拿到的指令以及 PC 的值往下傳遞。

<iframe src="https://drive.google.com/file/d/1SvHnp0lnES39DYB3yQ8ugbMIw6MRubEI/preview" height="380"></iframe>

# ID Stage

$$
\displaylines{
\text{ID/EX.A = Reg[IF/ID.IR[19-15]]}\\
\text{ID/EX.B = Reg[IF/ID.IR[11-7]]}\\
\text{ID/EX.Immediate = (sign-ext(IF/ID.IR[31-20])}\\
\text{ID/EX.PC = IF/ID.PC}\\
}
$$

前三項就是拿取 A 跟 B 兩者 REG 的值，以及算出 IMM。然後 PC 一樣傳遞下去。

<iframe src="https://drive.google.com/file/d/1LWK8O7m0yt3-I4kBMlU8lcoUxY-nOL-h/preview" height="380"></iframe>

# EX

$$
\text{EX/MEM.ALUout = ID/EX.A + ID/EX.immediate}\\
$$

因為這裡是 Load，所以 B REG 就沒有用到，只會用到 IMM。

<iframe src="https://drive.google.com/file/d/1WYhwAHe0YSUeCql1zDB0Ge9UdX3qeeMG/preview" height="480"></iframe>

# MEM

$$
\text{MEM/WB.MDR = mem[EX/MEM.ALUout]}\\
$$

<iframe src="https://drive.google.com/file/d/1MKr8NSUAj4DcmbsOgQ1K07PXylnFpqax/preview" height="480"></iframe>

因為是 load 所以是讀取記憶體。

# WB

$$
\text{Reg[Rd] = MEM/WB.MDR}\\
$$

最後要把讀到的內容存回 rd，但是先前我們並沒有傳遞 rd？

<iframe src="https://drive.google.com/file/d/19zV1Xd-9lVWWdYQs6jc7rCD9HuAdgMGh/preview" height="480"></iframe>

所以正確的結構是 rd 要一直傳遞下去，也就是說每個 Latch 都有一個變數來記錄 rd 的地址。

<iframe src="https://drive.google.com/file/d/1O_HBHAG39zVLq1McZOXEM7wojX7jYHtZ/preview" height="480"></iframe>

你說我們剛剛傳遞的 PC 去哪了？

# Beq EX

沒錯，因為剛剛 load 並不需要用到 PC，可以發現後半部的 Latch 並沒有繼續傳遞 PC。

這裡就會需要用到 PC 了，用於將 IMM 加上 PC 的位置以移動 PC；並且會往後傳：

$$
\displaylines{
\text{EX/MEM.PC = ID/EX.PC + (ID/EX.immediate << 1);}\\
\text{EX/MEM.Zero = (ID/EX.A – ID/EX.B) ? 0 : 1}\\
}
$$

以及算出 Zero 的值。

<iframe src="https://drive.google.com/file/d/1M4AKctnHKOi6U2b81MbPqhHFeu21Yx_l/preview" height="480"></iframe>

# Beq MEM

$$
\text{If EX/MEM.zero == 1 then PC = EX/MEM.PC}\\
$$

剛剛傳遞過來的 PC 會用在這裡。

<iframe src="https://drive.google.com/file/d/1lALo_xdBWltj746sPZ-rMgfOheM6QpMT/preview" height="580"></iframe>

---

# Noop Stage

現在來說明為何每個指令都要走固定 5 個 stage。

<iframe src="https://drive.google.com/file/d/1OF-BV1H_1vKz5JzdEBcK4lHR3OegW-Ur/preview" height="380"></iframe>

從這張圖中可以發現，不同指令在某些 Stage 其實不會有任何動作。
如果就這樣直接去設計 pipeline，會發生如下的衝突，也就是兩者同時都要使用到寫回 REG 的線路。

<iframe src="https://drive.google.com/file/d/1qdI0ILQ4BbstTvtYZ-9C1BpWNqh5FO2w/preview" height="380"></iframe>

## 解法一：Bubble

或許我們就乾脆給他延遲，這樣就不會衝突了？

<iframe src="https://drive.google.com/file/d/1HEoIfhvfMPvpD6Ia6nnA4k3hPA131VXv/preview" height="380"></iframe>

但是這就跟上面 Stall 一樣，會拖延後面的效率，並且為了設計添加 Bubble 的機制，線路可能會變更複雜。

## 解法二：Noop Stage

我們尊崇 RISCV 的意志，固定格式。

也就是每個指令都一定要經過 5 個 Stage，但是沒有做事的 Stage 就放空。

這種 Stage 就是所謂的 Noop Stage，甚麼事也不會做。例如下面 R type 的 MEM Stage 就是 Noop Stage。

<iframe src="https://drive.google.com/file/d/16JWtR0sybrcRTFqp1QkER-lxfA5dWOL_/preview" height="430"></iframe>

---

# Control Signals

聰明的你應該發現了，之前的 Control Signal 去哪裡了？

<iframe src="https://drive.google.com/file/d/1NTm0Ais9RNM6qzvf64G0ohn0evcYem29/preview" height="480"></iframe>

沒錯，他們也會在 Latch 之間傳遞，下面就是他們的傳遞過程。

<iframe src="https://drive.google.com/file/d/192bSKx6WcPa5yu_4T1h7_o_b_UXjhQmo/preview" height="380"></iframe>

但是通常會把類似功能的合在一起：

- ALUSrc 跟 ALUOp 會一起存進 ID/Ex.EX 這個變數
- MemRd、MemWr 跟 Branch 會一起存進 ID/Ex.M 這個變數
- 並且會傳遞到 Ex/Mem.M
- MemtoReg 跟 RegWr 會一起存進 ID/Ex.WB 這個變數
- 並且會傳遞到 Ex/Mem.WB
- 並且會再傳遞到 Mem/Wr.WB

<iframe src="https://drive.google.com/file/d/1I_8wcFYRcTyLd-xIHv53yhKbFMbXf4s6/preview" height="580"></iframe>

所以畫出圖來就會長這樣：

<iframe src="https://drive.google.com/file/d/1KVbsIdw0RRXWWRXaw9uf8dtePHantg4l/preview" height="580"></iframe>

:::warning
從上面的結構可以知道， Forward 就是「後者」從「在他之後的 Latch」 中拿「前者」的資料，也因此如果前者的資料尚未算好，或是尚未存進 Latch 裡面，後者也拿不到任何資料。

Branch 的預先寫入也是同樣的道理，在資料存入 EX/MEM 之前，就拿去更新 PC；這通常需要額外的線路，因為 Zero 跟 Branch 的 AND 判斷要提早做。

而分支預測也是利用一樣的結構，並且還要多加線路，如果判斷出是要分支，就要把後續的 Stage 全都設 0。
:::