# 平行處理

有分為兩種層面：

- 工作層面 Task-level (process-level) parallelism
- 讓單一個工作(independent jobs)的 throughput 增加
- 例如工作的某個程序由某個核心來做
- 程序層面 Parallel processing program
- 單一個程序(program)用多個核心執行

## Amdahl’s Law

一樣，想要平行化？要先看看平行化帶來的效率提升夠不夠。

舉例來說，我們動用了 100 個核心平行化處理，來看看新的所耗時間跟舊的相比差多少：

$$
T_{\text{new}}=\frac{T_{\text{parallelizable}}}{100}+T_{\text{sequential}}
$$

或者我們換個方法表示，$T_{\text{parallelizable}}$ 跟 $T_{\text{sequential}}$ 加起來等於 1，$T_{\text{parallelizable}}$ 跟 $T_{\text{sequential}}$ 的比例分別為 $F_{\text{parallelizable}}$ 跟 $F_{\text{sequential}}$，那麼，改成用比率表示的話為：

$$
\frac{1}{\frac{F_{\text{parallelizable}}}{100}+F_{\text{sequential}}}=\frac{1}{\frac{F_{\text{parallelizable}}}{100}+(1-F_{\text{parallelizable}})}
$$

我們用了 100 顆核心，想要有 90 倍的提升應該不為過吧？，那麼我們來算算看 $F_{\text{parallelizable}}$ 要佔多少的比例：

$$
\frac{1}{\frac{F_{\text{parallelizable}}}{100}+(1-F_{\text{parallelizable}})}=90
$$

可以解得 $F_{\text{parallelizable}}=0.999$，代表我們要有非常大的部分屬於可平行化，才可以達到 90 倍的提升。

# Strong vs Weak Scaling

從上面的例子可以看到，不是狂堆核心，效能就會上去，而是跟工作的類型有關。

為此聰明的人們分出兩種類型：

- Strong Scaling
- 工作的大小固定，核心堆越高效能越好
- 這就是上面我們理想的工作
- Weak Scaling
- 工作量跟核心的需求量成正比
- 也就是說工作量要多，高核心才可以提高效能

舉個例子。

- 工作 A，他是將 10 個純量加起來，並且再做兩個 10X10 的矩陣元素相加。
- 工作 B，一樣是將 10 個純量加起來，但是再做兩個 100X100 的矩陣元素相加。

可以看到將 10 個純量加起來就是 Seq 的部分。然後我們分別用單核心跟多核心的情況模擬，並且計算 「Potential」：

- 工作 A
- 單核心：$(10+100)\times t_{\text{add}}=110\times t_{\text{add}}$
- 10 顆核心：$(10+\frac{100}{10})\times t_{\text{add}}=20\times t_{\text{add}}$
- 跟單核心相比：$\frac{110}{20}=5.5$ 倍的提升
- 但是理論上 10 顆核心應該要有 10 倍提升，所以 Potential 為 $\frac{5.5}{10}=55\%$
- 100 顆核心：$(10+\frac{100}{100})\times t_{\text{add}}=11\times t_{\text{add}}$
- 跟單核心相比：$\frac{110}{11}=10$ 倍的提升
- 但是理論上 100 顆核心應該要有 100 倍提升，所以 Potential 為 $\frac{10}{100}=10\%$

可以看出如果工作量固定的話，狂疊核心的 Potential 反而會變低。

- 工作 B
- 單核心：$(10+10000)\times t_{\text{add}}=10010\times t_{\text{add}}$
- 10 顆核心：$(10+\frac{10000}{10})\times t_{\text{add}}=1010\times t_{\text{add}}$
- 跟單核心相比：$\frac{10010}{1010}=9.9$ 倍的提升
- 但是理論上 10 顆核心應該要有 10 倍提升，所以 Potential 為 $\frac{9.9}{10}=99\%$
- 100 顆核心：$(10+\frac{10000}{100})\times t_{\text{add}}=110\times t_{\text{add}}$
- 跟單核心相比：$\frac{10010}{110}=91$ 倍的提升
- 但是理論上 100 顆核心應該要有 100 倍提升，所以 Potential 為 $\frac{91}{100}=91\%$

可以看到工作量如果變多了，100 顆核心的 Potential 會變高。

:::warning
所以我們其實可以列出一個方程式來計算這個問題：

- 單核心：$(10+x^2)\times t_{\text{add}}$
- 10 顆核心：$(10+\frac{x^2}{10})\times t_{\text{add}}$
- 跟單核心相比：$\frac{10+x^2}{10+\frac{x^2}{10}}=\frac{100+10x^2}{100+x^2}$ 倍的提升
- 但是理論上 10 顆核心應該要有 10 倍提升，所以 Potential 為 $\frac{\frac{100+10x^2}{100+x^2}}{10}=\frac{10+x^2}{100+x^2}$
- 100 顆核心：$(10+\frac{x^2}{100})\times t_{\text{add}}$
- 跟單核心相比：$\frac{10+x^2}{10+\frac{x^2}{100}}=\frac{1000+100x^2}{1000+x^2}$ 倍的提升
- 但是理論上 100 顆核心應該要有 100 倍提升，所以 Potential 為 $\frac{\frac{1000+100x^2}{1000+x^2}}{100}=\frac{10+x^2}{1000+x^2}$

所以我們可以知道，要到何種程度 100 顆才會比 10 顆好，就是：

$$
\displaylines{
\frac{10+x^2}{100+x^2}<\frac{10+x^2}{1000+x^2}\\
1000+x^2<100+x^2\\
}
$$

永遠不會比較好。
:::

Data Decomposition

Task Decomposition

Pipelining

---

# Shared Memory Multiprocessor / SMP

顧名思義，就是每個核心都共用一塊記憶體。

聰明的人們用 Memory access time 來劃分出兩個種類：

- UMA：uniform memory access
- 各個核心存取的延遲是一樣的，如那張圖，因為就只有一塊記憶體，所以大家延遲都一樣
- NUMA：nonuniform memory access

下面主要著重 UMA 的部分。

# UMA - Cache Coherency

因為每個核心都共用一塊記憶體，但是 Cache 是各自擁有的，例如下圖：

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

所以必須要維持 Cache 內容的一致性。

我們的手段是透過一個叫 Snooping 的方式來處理。

# Snooping

講白話一點他就是 broadcast。上面的圖可以看到有個 Interconnection Network，這個東西又叫做 Bus，他是 broadcast 可以運作的主要結構。

大致維護的方法一個核心就是將「requests for data」的訊號給其他的核心，然後做一些操作。

在 Bus 上 Snooping 的手段，被廣泛用於小型的機器 small scale machines，也就是家用主機這樣的類別。

至於詳細的 Snooping，分為兩種：

- Write Invalidate Protocol
- Multiple readers, single writer
- 發出 request 的人叫其他人把他們的資料變為不合法
- 這個動作又叫 Write to shared data
- Read Miss 的部分，如果某個核心他沒有找到要讀的資料怎麼辦？
- Write-through：memory is always up-to-date，所以不用擔心
- Write-back：snoop in caches to find most recent copy，也就是去看其他人的 cache，把有最新 cache 的核心的資料複製過來
- 這個待會會細講，會透過資料的 validate 狀態來判斷
- Write Update Protocol
- 在 Bus 上廣播給大家，叫大家以及記憶體一起更新
- Read Miss？永遠不會發生，因為隨時大家資料都是最新的

## 優缺

Invalidate 的每次寫入操作，只需要一次的 bus 傳輸訊號，因為第一次的廣播就會讓其他人的 cache 資料都變 invalidate，自己的保持 validate，所以如果第二次寫入同個 block 並保持是 validate，就不用再次做廣播，因為其他人已經是確保是 invalidate。

除非有其他人也做寫入，就會換你的資料變成 invalidate。

Update 則可以讓 read 跟 write 之間有較低的延遲，因為每次都是一次性叫全部人一起更改，資料隨時都是最新的，所以發生 read miss 時就不用花時間去查誰的 cahce 是最新的。

下面是個流程的範例：

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

可以看到 Invalidate 中的 B，在 A 發出寫入訊號後，他的 cache 資料就變成了 invalidate，所以就不見了，並且這裡的例子是 write back，所以記憶體中的資料並沒有一起更新，這也是為何其他核心如果要拿資料的話，必須要從有最新資料的核心拿的原因。

在 Update 中則是 A 發出寫入訊號後，大家都一起更新了。

:::warning
所以如果某個處理器的規模較小， bus 能力有限，就會採用 Invalidate 這種對 bus 負擔較小的 Protocol
:::

# Invalidate Snoopy with write-back cache

下面以「狀態圖」的方式完整介紹 Invalidate Snoopy 的內容，搭配 write-back cache。

在那之前，要先說明：

- 對於每個 cache block(也就是一個 set)來說，他只會在下面的三種狀態其中一種：
- Shared：分享狀態，這個 block 是可以被其所擁有的 CPU 讀取的
- Exclusive：獨特狀態，這個 block 擁有最新的資料，其他人的都是舊的
- 此時這份資料除了可以被其所擁有的 CPU 讀取，也可以被寫入
- 但是因為是 write back 所以要設置 dirty bit。
- Invalid：cache 沒有 block 的資料，或是不是最新的，所以不能用了

下面介紹兩種角度的狀態圖。

## Request 發起人

我們一個一個的來看各個狀態：

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

- 當前 block 狀態是 **Invalid**：
- 如果此時發起 CPU **read**，會向 Bus 吐出「**Read Miss**」
- 代表這個 block 之後會被放入從其他人來的「**最新的資料**」
- 也因此進入了 **Shared state**，代表其他人如果想拿最新資料...
- **不可以跟他要，只能從記憶體拿**
- Shared 的意思只代表該資料目前是處於「分享的狀態」，所以記憶體的資料是合法的
- 如果此時發起 CPU **write**，會向 Bus 吐出「**Write Miss**」
- 代表這個 block 之後會被放入從其他人來的「**最新的資料**」
- 並且會對他進行寫入，成為比**目前為止最新的資料**
- 也因此進入了 **Eclusive state**，代表目前的 block 擁有最尖端的資料
- 當前 block 狀態是 **Shared**：
- 如果此時發起 CPU read，不過好家在，block 在 cache 內，所以就一樣指回自己
- 如果此時發起 CPU **read** 但是**沒有資料**，會向 Bus 吐出「**Read Miss**」
- 代表這個 block 之後會被放入從其他人來的「最新的資料」
- 所以跟剛剛 Invalid state 一樣，都是進到 Shared state
- 如果此時發起 CPU write
- **無論資料有沒有在 cache 內，都會向 Bus 吐出「Write Miss」**
- 代表目前的核心即將會擁有這個 block 最尖端的資料，也因此進入了 **Exclusive state**
- 同時也在告知其他核心，**你們的資料都過期啦**
- 當前 block 狀態是 **Exclusive state**：
- 如果此時發起 CPU read 或 write，但是好家在，block 在 cache 內
- 所以就一樣指回自己，資料一樣是維持最新穎的資料
- 如果是 read，但是沒有資料，會向 Bus 吐出「**Read Miss**」
- 並且還會將自己最頂尖的資料先寫回記憶體
- 然後就會進到 **Shared state**，代表該資料目前是處於「分享的狀態」
- 要拿資料就從記憶體去拿
- 如果是 write，但是沒有資料，會向 Bus 吐出「**Write Miss**」
- 跟 read miss 一樣，會先將自己最尖銳的資料寫回記憶體
- 然後因為是寫入的操作，所以之後擁有的 block 一樣還是最尖端的科技
- 因此停留在 **Eclusive state**

:::warning
- 沒有資料的意思是，該 block 的資料不是要 read 或 write 的資料，是一個 miss
- 簡單來說，發起 write 的時候會進到 **Exclusive**；發起 read 的時候，進到 **Shared**
- 關於「Shared state 的意思」跟「從記憶體拿」，請看下面。
:::

## Request 接收者

我們一個一個的來看各個狀態：

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

- 當前 block 狀態是 **Invalid**：
- 可以看到並沒有任何指向外面的箭頭，關鍵在於這是「**以某個核心的角度來說**」
- 因為以某個核心來講，他雖然收到了 write 或 read miss，但是它本身該 block 的資料就是 invalid，也就不能給別人
- 所以對於最初始的狀態，如果某個 miss 的發起人沒有收到其他人的回覆，就得要從記憶體拿資料
- 當前 block 狀態是 **Shared**：
- 如果收到的請求是 write miss，並且本身的該 block 的狀態是 Shared
- 代表**該 block 的資料就要失效了**，所以會進入 Invalid state
- 這就是上面提到的，request 發起人會叫其他人把資料設成 Invalid
- 那為甚麼收到的請求是 read miss，並且本身的該 block 的狀態是 Shared，卻沒有箭頭呢？
- 其實可以看到在 Exclusive state 的時候，如果收到 read miss，會**將資料寫回記憶體**
- 也就是代表，當前最尖端的資料已經放在記憶體了，所以資料是 **Shared** 的狀態
- 也因此 Shared state 的核心如果又收到 read miss，並不會做任何動作
- 告訴你要拿請跟記憶體拿，**記憶體有最新的資料**
- 當前 block 狀態是 Eclusive state：
- 如果收到的是 read miss
- 會將最新穎的資料先寫回記憶體，然後進入 Shared state
- 代表當前該 block 的資料是最新的，最純的
- 並因此可以看到有個 abort memory access 的字樣，代表不需從記憶體讀取
- 相對的，Shared state 沒有寫的就是要從記憶體讀取
- 如果收到的是 write miss
- 一樣會將最新穎的資料先寫回記憶體
- 但是發起 write 的核心待會就會有最新的資料了，所以自己的資料即將過期
- 因此進入了 Invalid state
- 也一樣可以看到 abort memory access

## 下面是模擬

<iframe src="https://drive.google.com/file/d/17bvbRjVpe8zvHyKeasB5f8bV1cjP5nCy/preview" height="300"></iframe>)

---

# 四個 C

從上次的三個 Miss 多加了這次的第四個 Miss：Coherency Misses，代表是跟維持一致性有關而造成的 miss。

當兩個 CPU 要存取相同的 block 時，Coherency Misses 有分成兩種：

- True sharing misses
- 是真的因為該 block 的資料要維持一致性而造成的 miss
- 像上面提到的，如果某個 block 處於 Shared state，那麼要發起寫入時一定會送出 write miss
- False sharing misses
- 但是我們知道一個 block 內可能會放有很多資料，但是因為他們都在同個 block 內，所以可以會發生 A 資料的更新導致了 B 資料的 invalidate，例如下圖

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

這圖的假設是一開始 P1 跟 P2 兩個核心內的某一個 block 內，有著 x1 跟 x2 兩個資料，並且當前是 Shared state：

- 第一時刻，P1 想要 write x1，根據上面第一個狀態圖，可知 P1 會向 Bus 發送「write miss」
- 這個 miss 是因為想要 write x1 而引起的，所以是 **True (sharing) miss**
- 但是此時 P1 該 block 就會進入 Exclusive，P2 的就會進入 Invalid
- **而倒楣的 x2 因為跟 x1 同個 block，所以害他也跟著變 Invalid**
- 第二時刻，P2 想要 read x2，因為 P2 該 block 目前是 invalid，可知 P2 會向 Bus 發送「read miss」
- **這個 miss 是因為剛剛的 write x1 所導致的 invalid，所以是 False miss**
- 而此根據上面的狀態圖，P1 跟 P2 的該 block 都會進入 shared state
- **倒楣的 x1 也就因為這樣進到了 shared state**
- 第三時刻，P1 想要 write x1，因為 P1 該 block 目前是 shared，可知 P1 會向 Bus 發送「write miss」
- **這個 miss 是因為剛剛 read x2 而引起的，所以是 False (sharing) miss**
- 但是此時 P1 該 block 就會進入 Exclusive，P2 的就會進入 Invalid
- 而倒楣的 x2 因為跟 x1 同個 block，所以害他也跟著變 Invalid
- 這件事跟剛剛第一時刻一模一樣，歷史總是驚人的相似
- 第四時刻，P2 想要 write x2，因為 P2 該 block 目前是 invalid，可知 P2 會向 Bus 發送「write miss」
- **這個 miss 是因為剛剛的 write x1 所導致的 invalid，所以是 False miss**
- 而此根據上面的狀態圖，P1 的該 block 會進入 invalid state
- 而 P2 因為是寫入操作，所以有最新的資料，目前在 Exclusive state
- **倒楣的 x1 也就因為這樣進到了 invalid state**
- 第五時刻，P1 想要 read x2，因為 P1 該 block 目前是 invalid，可知 P1 會向 Bus 發送「read miss」
- 這時有趣了，**這個 miss 是因為剛剛 write x2 而引起的**，加上現在要 read x2
- **所以現在是屬於True (sharing) miss**
- 然後 P1 跟 P2 的該 block 就都進入了 shared state，倒楣的 x1 又....

---

# Roofline model

## 1. 多處理器效能基準測試 (Benchmarks)

在介紹模型之前，投影片列出了幾種常見的平行處理效能測試標準：
* **Linpack：** 矩陣線性代數運算（常用於 Top500 超級電腦排名）。
* **SPECrate：** 平行執行 SPEC CPU 程式，測試任務級 (Job-level) 平行度。
* **SPLASH / PARSEC：** 針對共享記憶體 (Shared Memory) 的應用程式基準測試，包含多種核心運算與應用場景。

---

## 2. Roofline Model (屋頂模型) 核心概念

這個模型將硬體極限與軟體特性結合在一張圖表上，幫助開發者判斷瓶頸所在。


## **A. 兩個關鍵參數**

模型主要由以下兩個參數構成座標軸：
1. **X 軸 - 運算強度 (Arithmetic Intensity)：**
* 定義：每存取一個 Byte 的記憶體，進行了多少次浮點運算 (FLOPs)。
* 公式：$\frac{\text{Floating-Point Ops}}{\text{Bytes Accessed}}$
* 意義：反映演算法對資料的重複利用率。強度越高，代表對記憶體頻寬的需求相對越低。
2. **Y 軸 - 可達到的效能 (Attainable GFLOPs/sec)：**
* 系統實際能跑出的運算速度。

## **B. 「屋頂」的組成 (The Roof)**

圖表中的「屋頂」形狀由兩條線組成，代表硬體的物理極限：
1. **斜線部分 (Memory Bandwidth Limited)：**
* 受限於 **Peak Memory Bandwidth (記憶體頻寬峰值)**。
* 當運算強度較低時，效能卡在==記憶體傳輸速度==，CPU 運算單元在等待資料。
2. **水平線部分 (Computation Limited)：**
* 受限於 **Peak Floating-Point Performance (浮點運算峰值)**。
* 當運算強度夠高（資料讀進來後被重複運算很多次），效能瓶頸就會轉移到 ==CPU 的運算速度==上。

## **C. 效能公式**

系統能達到的效能是兩者的最小值：
$$
\displaylines{
Attainable\ GFLOPs/sec = \\
\min(\text{Peak Memory BW} \times \text{Arithmetic Intensity},\ \text{Peak FP Performance})
}
$$

- 對照上圖的話，$\text{Peak FP Performance}$ 就是 16 GFlops/sec
- 意思就是 ==CPU 的運算速度上限==是 16 GFlops/sec
- $\text{Peak Memory BW} \times \text{Arithmetic Intensity}$ 得到的就是斜線上的 y 值
- 從 x = 1 的位置我們可以知道 $\text{Peak Memory BW}$ 就是 16 bytes / sec
- 意思就是 ==記憶體傳輸速度上限是== 16 bytes / sec
- 所以 x = $\frac{1}{4}$ 的位置，剛好乘上 16 就會得到 4 GFlops/sec

:::warning
根據公式我們可以知道：
- 斜直線區域的公式就是 **運算效能=記憶體最大帶寬×運算強度**
- 在這區域內，**對於某個運算強度 $x$，你的上限受記憶體最大帶寬影響**
- 最大帶寬越高，**$x$ 強度下**的運算效能越高
- 因此才說是受記憶體帶寬影響
- 水平線區域就是 **最大運算效能**
- 在這區域內，**對於某個運算強度 $y$，你的上限受最大運算效能影響**
- 最大運算效能越高，**$y$ 強度下**的運算效能越高
- 因此才說是受最大運算效能影響
:::

## 3. 演算法的運算強度光譜


不同類型演算法的運算強度，決定了它們落在 Roofline Model 的哪個位置：
* **低強度 (容易受限於記憶體)：** 稀疏矩陣 (Sparse Matrix)、結構化網格 (Structured Grids)。
* **中強度：** 頻譜方法 (FFTs)。
* **高強度 (容易受限於運算能力)：** 稠密矩陣 (Dense Matrix, 如 BLAS3)、N-body 粒子模擬。

---

### 4. 系統比較範例 (Opteron X2 vs. X4)

投影片最後用 AMD Opteron X2 (雙核) 與 X4 (四核) 的比較來說明模型價值：


* **情境：** X4 的核心數是 X2 的兩倍（理論運算峰值倍增），但兩者共用相同的記憶體系統（頻寬相同）。
* **圖表分析：**
* **左側 (低運算強度)：** 兩條線重疊。因為瓶頸是記憶體頻寬，增加核心數（X4）無法提升效能。
* **右側 (高運算強度)：** X4 的「屋頂」比較高。只有當程式的運算強度夠高，或者工作集 (Working Set) 能塞進 Cache (避免存取主記憶體) 時，X4 才能發揮出比 X2 更高的效能。

### 總結

這個模型告訴我們：**單純增加 CPU 核心數或時脈不一定能變快**。如果你的程式落在 Roofline 的左側斜坡（記憶體受限），你應該優化記憶體存取（提升運算強度）；如果落在右側平頂（運算受限），你才需要考慮向量化指令或更多核心。

# Bisection Bandwidth

---

CMP chip multi processor = multicore

透過 router 來做資料溝通(packet switch)，每個核心就好像一個節點

又叫做 network on chip

L1 屬於 private 的 cache， L2 雖然物理上是分布的，但是實際上是屬於 shared 的 cache

老師說現在核心很多的多半是用這種

大小核 for energy efficiency，因為有時候大核能力太強了，比較耗電

---

# Hardware Multithreading

這是加速具有超純量技術的 CPU 的一個技巧，讓 CPU 可以在多個 thread 之間切換，甚至並行。


上圖是 4 stage 的 pipeline，一個 row 代表一個 cycle

- 可以看到 Superscalar 有些時候是空白的，代表該時候資源是沒有被利用的，會造成浪費；這些空白可能是因為 branch 導致的 NoOP 或是某些 hazard 的 stall。
- 所以我們希望不要有空白，也就是空白的時候就換別的 thread 去執行。
- Fine-Grained 就是大家輪流執行一個 stage，這樣就很難會有空白了
- 又叫做 Round robin
- Coarse-Grained 是直到 CPU 發現有空白的時候才換 thread 執行

但是要注意，超純量是指令級的並行，你可以發現一個 cycle 內就只有一個 thread 的指令。
最右邊是多核心處理器，一個處理器內有多個核心，自然就可以同時執行不同的 thread。

此外還有一個更著名的，Intel 稱作超執行緒，在有超純量的指令級並行的情況下，同時達成執行緒級並行：


就是最右邊的 SMT (Simultaneous-Multithreading)，讓一個 cycle 可以運行不同 thread 的指令
>很像 OFDMA

---

SIMD 像是矩陣相乘，一次需要很多資料
並且由於一次只需要一次 fetch ，所以比較節能，因為 fetching 其實很耗電的，所以 SIMD 效能會比 MIMD 會比較好
而且也可以讓寫 code 的人不需要用平行化的方式去思考演算法(比較好想)，物理層面都做好了

SIMD 隨著趨勢演進，就是讓一個暫存器內可以一次攜帶更多 Data 進來，前提是要保持這些資料是連續的且 aligned 的，才可以進行辨識。

Vector Architectures

好像是專門用來矩陣運算的架構?

總之就是我們設計一種很酷的暫存器，他可以存放 n 個 m bit 的值，每個 m bit 之間是獨立的。

這種暫存器需要配套的指令支援，像是 RISCV 的 V 擴展。

其用法就是可以一次性的將 2 個 n 個 m bit 的值，每個 row 各自相加等等的操作；也算是簡化了平行演算法，並且因為省去了 loop，還可以避免 control hazard

但相對的，硬體也要做出調整， ALU 必須要修改成很多個 ALU 協同運作，例如某個 ALU 負責計算第 0, 4, 8... 個 row 的值

interleaved 是之前提到過的 memory bank，也就是記憶體中的資料會分成不同的 bank 來存放，可能第一個 bank 放第餘數是 0 byte 的資料等等

MLPerf 是個專門用來比較 ML 的 Benchmark

---

這幾個章節（第 51 頁至 58 頁）主要在介紹如何利用 **Data-Level Parallelism（資料級平行化）** 來提升效能，也就是「一個指令同時處理多筆資料」。

這裡將技術分成了兩大類來探討：**SIMD 多媒體擴充指令集** 與 **向量架構 (Vector Architectures)**。

以下是詳細的章節重點說明：

### 1. 運算分類與 SIMD 概念 (Page 51-52)
* **分類 (Flynn's Taxonomy)：**
* [cite_start]投影片首先釐清了電腦架構的分類。傳統單核心是 **SISD** (單一指令單一資料)，而這裡要講的是 **SIMD** (單一指令多重資料) [cite: 739]。
* **SIMD 的核心精神：**
* [cite_start]**效率：** 只需要讀取一次指令 (Fetch)，就能對一整排資料進行運算，這比 MIMD (多指令多資料) 更省電 [cite: 755-756]。
* [cite_start]**應用場景：** 非常適合處理矩陣運算、影像處理或聲音訊號，因為這些資料通常都是一整塊且需要進行相同的運算 [cite: 744-746]。

### 2. SIMD 多媒體擴充指令集 (Multimedia Extensions) (Page 53)
這是現代 CPU（如 Intel/AMD x86）常見的實作方式。
* **背景：** 許多媒體資料（如像素的 R、G、B）只需要 8-bit 或 16-bit，但 CPU 暫存器通常是 64-bit。
* [cite_start]**作法：** 將長暫存器切分，例如一個 64-bit 暫存器可以同時裝 8 個 8-bit 的數字，一次加法就能算完 8 個像素的亮度調整 [cite: 765-767]。
* **演進歷史：**
* **Intel MMX (1996)：** 64-bit 運算。
* **SSE (1999)：** 128-bit 運算，支援浮點數。
* [cite_start]**AVX (2010)：** 256-bit 運算 [cite: 768-774]。
* [cite_start]**限制：** 資料在記憶體中必須是**連續且對齊 (Aligned)** 的，否則無法有效率讀取 [cite: 775]。

### 3. 向量架構 (Vector Architectures) (Page 54-57)
這是一種比上述 SIMD 擴充指令更進階、更靈活的架構（投影片以 RISC-V Vector 為例）。
* **運作方式：**
* [cite_start]使用專門的「向量暫存器」(Vector Registers)，可以一次讀入大量的資料元素 [cite: 779]。
* [cite_start]**Gather / Scatter：** 這是向量架構的一大特點。它支援從記憶體中「收集 (Gather)」分散的資料到暫存器，運算完再「分散 (Scatter)」寫回，不像傳統 SIMD 被限制在連續記憶體 [cite: 780-783]。
* **程式碼比較 (DAXPY 範例)：**
* 投影片比較了 $Y = a \times X + Y$ 的程式碼。
* [cite_start]**傳統 RISC-V：** 需要寫迴圈 (Loop)，每次只算一個數，還要處理索引增加與跳轉指令，指令數多 [cite: 819-846]。
* [cite_start]**向量 RISC-V：** 幾乎沒有迴圈，幾個指令 (`fld.v`, `fmul.d.vs`, `fadd.d.v`) 就能算完一整排資料，大幅減少了指令讀取的頻寬需求 [cite: 847-862]。
* [cite_start]**優勢：** 編譯器更容易優化，因為它明確告訴硬體「這裡沒有迴圈相依性 (Loop-carried dependences)」，且比 MMX/SSE 這種特定擴充指令更通用 [cite: 867-872]。

### 4. 硬體實作：多通道 (Multiple Lanes) (Page 58)

* **概念：** 為了讓向量運算更快，硬體內部會將運算單元切分成多個 **Lanes (通道)**。
* **運作：**
* 假設有 4 個通道 (Lane 0 ~ Lane 3)。
* Lane 0 負責計算第 0, 4, 8... 個元素。
* Lane 1 負責計算第 1, 5, 9... 個元素。
* [cite_start]這樣可以讓硬體資源利用率最大化，同時並行處理多個資料點 [cite: 875-910]。

### 總結
這幾頁是從**軟體概念**到**硬體實作**的推進：
1. **SIMD 概念：** 一個指令算多筆資料。
2. **Multimedia Extensions (如 AVX)：** x86 CPU 上的實作，要求資料連續。
3. **Vector Architectures：** 更高階的架構，支援 Gather/Scatter，程式碼更精簡。
4. **Lanes：** 硬體如何透過多通道並行來實現上述架構。