{%hackmd r14yVks8p %}

# 背景 Instruction-Level Parallelism

管線的效果不錯，但我們希望更厲害，所以：

- 可以用更深的管線，也就是切更細
- 但是越切越細頻率會越高，功耗炸裂
- 另一個方法，也是待會的主角，叫做 Multiple issue
- 讓沒有相依性，或是相依性較小的指令放在同個 cycle 一起運行，下面會講細節
- 這樣可以使得 CPI 小於 1

# Multiple issue

分為靜態跟動態兩種。

:::warning
下列 by Gemini
:::

兩種主要的 Multiple Issue 處理器類型
--------------------------

Multiple Issue 的實現在很大程度上取決於**誰**來決定哪些指令可以同時發行：是**硬體**還是**編譯器**。

### 1. **動態多重發行處理器 (Dynamic Multiple-Issue Processors) / 超純量 (Superscalar)**

- **誰決定？** **硬體**在程式執行時 (Run-time) 動態決定。
- **發行方式：** 處理器會從指令串流中抓取多條指令，並在執行時檢查它們之間是否存在**資料相依性 (Data Dependencies)** 或**結構相依性 (Structural Hazards)**。
- 如果指令之間**沒有**相依性，硬體就會將它們分派給空閒的功能單元，並允許它們**亂序執行 (Out-of-Order Execution)**，但保證**按序完成 (In-Order Completion)**。
- **優點：** 程式設計師或編譯器不需擔心指令排程；適用於現有的程式碼。
- **範例：** 大多數現代伺服器、桌上型電腦和高效能行動處理器。

### 2. **靜態多重發行處理器 (Static Multiple-Issue Processors) / 超長指令字 (VLIW, Very Long Instruction Word)**

- **誰決定？** **編譯器**在程式編譯時 (Compile-time) 靜態決定。
- **發行方式：** 編譯器會將一組可以平行執行的指令打包成一個**超長指令字**，並在程式碼中明確指示哪些指令要同時執行。
- **優點：** 硬體設計相對簡單，不需要複雜的亂序執行電路。
- **缺點：** 對編譯器要求很高，如果程式碼的 ILP 不足，會浪費指令空間（用 NOP 填充）；硬體一旦改變，可能需要重新編譯。
- **範例：** 某些數位訊號處理器 (DSP) 和嵌入式系統。

# Static multiple issue

靜態是編譯器負責的，由他判斷指令間的相依性，讓他們在時序上是相同的，同個 cycle 會在同個 stage。

這些被放在一起的指令會被放入叫做「Issue slot」或「Issue packets」裡面，代表他們是一起的。
>`n` 個指令放在一起的話 Issue packets 就有 `4n` Bytes 這麼大。

因為還是有可能會發生相依性，所以編譯器也要知道何時放 nop
>會因為 ISA 而有所不同，而編譯器都要知道，編譯器 yyds

# RISCV Static Dual Issue

下面用 Dual Issue 示範 Static Issue。

## Issue Rule

一個 Issue 重要的是他的「rule」，規定哪些指令可以放一起，哪些不行。

制定 Rule 時要去評估要給多大的彈性，哪幾種指令可以放一起；如果是任意放的話，需要做調整的硬體也會越複雜，這樣反而 cost 會變高，本末倒置。

這裡 Dual Issue 的規則是：

- 一個只能是 ALU/branch 指令
- 一個只能是 load/store 指令

## 電路圖

下圖是根據 Dual Issue Rule 所修改的電路圖：

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

>這個電路圖有個很迷的地方，為甚麼 `ALU/branch` 的 `RS1` 會有 MUX 做判斷。

- 在 IF 的階段，因為要同時執行兩個指令，所以線路要複製一份出來。
- 在 ID 階段：
- `ALU/branch` 因為只是單純計算，不需要用到記憶體，所以 ALU 的結果不會通過記憶體而是直接拉回來
- 並且可以看到 Branch 的操作統一拉到 `Decode` 的部分了。
- `load/store` 因為只需要計算地址，並且是從 IMM 來，所以直接拉 IMM 到 ALU，最後直接拉進記憶體。

## Aggressive Scheduling

因為讓兩條指令有相同的時序，所以如果發生 Data Hazard，就不能做 forwarding 來解決，就必須要讓一條指令等另一條，這相當於一個 stall。
遇到 [load-use data hazard](https://hackmd.io/6N6TSxpxTSu_p7C5cDgLxg?view#Load-use-data-hazard)，一樣靠 stall 1 cycle 解決。

所以想要避免 stall 唯一的手段就是更積極的重新排序。如果重新排序也解決不了，則該 packets 就會有一邊是 nop，只能浪費掉了。

下面是一個跟地址操作有關的例子：

Loop: ld   x31, 0(x20)     // x31=array element
      add  x31, x31,x21    // add scalar in x21
      sd   x31, 0(x20)     // store result
      addi x20, x20,-8     // decrement pointer
      blt  x22, x20,Loop   // branch if x22 < x20

填進 packets 表格如下：

| | ALU/Branch | Load/Store | Cycle |
|:-------------:|:----------------------------------------:|:---------------------------------------------:|:-----:|
| $\text{Loop}$ | $\text{nop}$ | $\color{yellow}{\text{ld x31, 0(x20)}}$ | 1 |
| | $\text{addi x20, x20,-8}$ | $\text{nop}$ | 2 |
| | $\color{yellow}{\text{add x31, x31,x21}}$ | $\text{nop}$ | 3 |
| | $\text{blt x22, x20,Loop}$ | $\text{sd x31, }\color{red}{8}\text{(x20)}$ | 4 |

- 首先看==黃色的==，因為第一條 `ld` 跟第二條 `add` 發生了 load-use data hazard，所以必須等一個 cycle，因此他們兩個才會相隔一個 cycle。
- 再來，可以很神奇地發現，第 4 行的 `addi` 被往上提了
- 因為 `addi` 是在將地址 -8，我希望他可以早做一些，所以就大膽地給他放在第 2 個 cycle
- 只要將第 3 行的 `sd` 中儲存的地址，往回移動 8 就可以存到正確的地址了
- 這樣一來就可以壓縮 cycle 數了，跟鬼一樣
- 不然原本 4、5 行會放在第 5 跟第 6 個 cycle

:::warning
上面的 IPC(Instruction Per Cycle) 是 $\frac{5}{4}=1.25$，但是理論上 Dual Issue 最佳 IPC 應該是 2，也就是每個 cycle 應該要可以執行兩個指令。
:::

## Loop Unrolling & Renaming

如果上面的例子，實際上是個迴圈，此時我們的編譯器更積極的去檢查程式碼做了甚麼。

Loop:     ld   x31, 0(x20)     // x31=array element
          add  x31, x31,x21    // add scalar in x21
          sd   x31, 0(x20)     // store result
          addi x20, x20,-8     // decrement pointer
          blt  x22, x20,Loop   // branch if x22 < x20

- 因為上面的 code 就只是跑個迴圈，單純的把某個陣列內的每個值加上一個常數
- 所以聰明的編譯器就打算一次做四次同樣的操作，這樣就不需要每次都經過 `blt` 判斷
- 但不一定做的次數都是 4 的倍數，所以編譯器會額外加邊界處理的 code，這裡不提這個
- 然後這些指令就可以壓縮在一起做了

所以編譯器將指令稍微修改後，就會變成這樣：

Loop:   ld   x31, 0(x20)
        add  x31, x31, x21
        sd   x31, 0(x20)
        
        ld   x31, -8(x20)
        add  x31, x31, x21
        sd   x31, -8(x20)
        
        ld   x31, -16(x20)
        add  x31, x31, x21
        sd   x31, -16(x20)
        
        ld   x31, -24(x20)
        add  x31, x31, x21
        sd   x31, -24(x20)
        
        addi x20, x20,–32
        blt  x22, x20,Loop

>可以看到就直接從對應地址拿值出來改。

- 但是這樣會遇到一個問題，因為修改後的值都「暫時放在」 `x31` 這個相同的 REG 裡面，會造成所謂的 name dependency
- 所以聰明的編譯器知道說，既然是暫存用的，那我就給每個人放在不同的 REG 就好了
- 這個操作就叫做「**Renaming**」；編譯器分別用了 `x31` `x30` `x29` `x28`。

Loop:   ld   x31, 0(x20)
        add  x31, x31, x21
        sd   x31, 0(x20)
        
        ld   x30, -8(x20)
        add  x30, x30, x21
        sd   x30, -8(x20)
        
        ld   x29, -16(x20)
        add  x29, x29, x21
        sd   x29, -16(x20)
        
        ld   x28, -24(x20)
        add  x28, x28, x21
        sd   x28, -24(x20)
        
        addi x20, x20,–32
        blt  x22, x20,Loop

最後再將這些指令放到 packets 表格：

| | ALU/Branch | Load/Store | Cycle |
|:-------------:|:----------------------------------------:|:-----------------------------------------------:|:-----:|
| $\text{Loop}$ | $\text{addi x20, x20,-32}$ | $\text{ld x31, }\color{green}{0}\text{(x20)}$ | 1 |
| | $\text{nop}$ | $\text{ld x30, }\color{red}{24}\text{(x20)}$ | 2 |
| | $\color{yellow}{\text{add x31, x31,x21}}$ | $\text{ld x29, }\color{red}{16}\text{(x20)}$ | 3 |
| | $\color{yellow}{\text{add x30, x30,x21}}$ | $\text{ld x28, }\color{red}{8}\text{(x20)}$ | 4 |
| | $\color{yellow}{\text{add x29, x29,x21}}$ | $\text{sd x31, }\color{red}{32}\text{(x20)}$ | 5 |
| | $\color{yellow}{\text{add x28, x28,x21}}$ | $\text{sd x30, }\color{red}{24}\text{(x20)}$ | 6 |
| | $\text{nop}$ | $\text{sd x29, }\color{red}{16}\text{(x20)}$ | 7 |
| | $\text{blt x22, x20,Loop}$ | $\text{sd x28, }\color{red}{8}\text{(x20)}$ | 8 |

上面的表格跟原本的稍為不一樣，原因跟上面的第一個版本一樣，聰明的編譯器想要讓 `addi` 一開始就執行，也就是原本 17 行的指令被移到第一行，所以一開始的 `x20` 就已經被往後 32 `btyes` 了，因此原本 `ld` 跟 `sd` 的地址都要進行修改。

而第一個 `ld` 因為跟 `addi` 是同個 packet，所以他還不會受地址的影響，因此地址依舊是綠色的 0。

:::warning
爆改後的 IPC(Instruction Per Cycle) 是 $\frac{14}{8}=1.75$，很接近理論值 2 了，但是付出的代價是使用更多 REG 跟記憶體來儲存修改過的新的指令。
:::

# Dynamic multiple issue

有個專門的硬體叫 Out of order unit 會去判斷當前指令能不能同時序執行。

他會將指令讀取後去做分類，判斷當前指令是哪種操作；然後沒有相依性的就可以先算出結果，所以是沒有順序的 Out of Order。

但是最後寫回記憶體或暫存器時就會依照正確的順序把值寫入。

:::warning
會需要 Dynamic 的原因是，Static 的其實會比較保守，無法做到更多地步，因為：

- 實際上的 code 會因為一堆原因而不是那麼好 predicable
- branch 相關指令很難做 Schedule
- 不同 ISA 的硬體會不一樣

因此還是需要有硬體，在第一現場做判斷。
:::

# Multiple Issue 功效

Multiple Issue 確實有效，但是也還是有他的極限，越多 Issue，得到的回報會越來越少。

# Power Efficiency

額外的硬體，就需要功耗。

除了上面的 Dynamic Multiple Issue，還有一個輔助他的傢伙叫 speculations，負責猜的，他也需要電。

所以統整來說，Power 會受下面幾項影響

- Clock Rate
- Pipeline Stages
- Issue Width
- Out-of-order&Speculation
- Cores

所以要看不同的規格在不同的 benchmark 有何種表現，去做取捨。

# 不同的設計

伺服器級別的 CPU ，因為他的使用場景是為了應付大量，但性質相似且簡單的任務，所以通常會具有高核心，時脈低(pipeline 數少)，以及 issue width 不會很高等特性。

---

## 回顧

- Multiple Issue 操作
- Loop Unrolling 操作