--- # System prepended metadata title: 第 8 講 平行化 Parallelization tags: [計算機結構] --- # 平行處理 有分為兩種層面： - 工作層面 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 是各自擁有的，例如下圖： 所以必須要維持 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 是最新的。 下面是個流程的範例： 可以看到 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 發起人 我們一個一個的來看各個狀態： - 當前 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 接收者 我們一個一個的來看各個狀態： - 當前 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 ## 下面是模擬 ) --- # 四個 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，例如下圖 這圖的假設是一開始 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 (屋頂模型) 核心概念 這個模型將硬體極限與軟體特性結合在一張圖表上，幫助開發者判斷瓶頸所在。 ![image](https://hackmd.io/_uploads/By0Tu4XfZx.png) ## **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. 演算法的運算強度光譜 ![image](https://hackmd.io/_uploads/r1199N7GZx.png) 不同類型演算法的運算強度，決定了它們落在 Roofline Model 的哪個位置： * **低強度 (容易受限於記憶體)：** 稀疏矩陣 (Sparse Matrix)、結構化網格 (Structured Grids)。 * **中強度：** 頻譜方法 (FFTs)。 * **高強度 (容易受限於運算能力)：** 稠密矩陣 (Dense Matrix, 如 BLAS3)、N-body 粒子模擬。 --- ### 4. 系統比較範例 (Opteron X2 vs. X4) 投影片最後用 AMD Opteron X2 (雙核) 與 X4 (四核) 的比較來說明模型價值： ![image](https://hackmd.io/_uploads/Byvo_4mGZe.png) * **情境：** 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 之間切換，甚至並行。 ![image](https://hackmd.io/_uploads/rkoOaNQz-e.png) 上圖是 4 stage 的 pipeline，一個 row 代表一個 cycle - 可以看到 Superscalar 有些時候是空白的，代表該時候資源是沒有被利用的，會造成浪費；這些空白可能是因為 branch 導致的 NoOP 或是某些 hazard 的 stall。 - 所以我們希望不要有空白，也就是空白的時候就換別的 thread 去執行。 - Fine-Grained 就是大家輪流執行一個 stage，這樣就很難會有空白了 - 又叫做 Round robin - Coarse-Grained 是直到 CPU 發現有空白的時候才換 thread 執行 但是要注意，超純量是指令級的並行，你可以發現一個 cycle 內就只有一個 thread 的指令。 最右邊是多核心處理器，一個處理器內有多個核心，自然就可以同時執行不同的 thread。 此外還有一個更著名的，Intel 稱作超執行緒，在有超純量的指令級並行的情況下，同時達成執行緒級並行： ![image](https://hackmd.io/_uploads/S19N8F0zbl.png) 就是最右邊的 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：** 硬體如何透過多通道並行來實現上述架構。