教材:10710周志遠教授平行程式
https://www.youtube.com/playlist?list=PLS0SUwlYe8cxqw70UHOE5n4Lm-mXFXbZT

20250913 筆記
內容可能有錯僅供參考

21A~21B Parallel Reduction / Distributed Computing Framework

今日大綱
1.範例應用：Reduction 函式
2.GPU 上的全域同步問題
3.解決全域同步問題：核心分解
4.區塊內優化策略
5.優化 1：減少 Warp Divergence
6.優化 2：解決 Shared Memory Bank Conflicts
7.優化 3：提升執行緒利用率 / 縮小區塊大小 (Thread Utilization / Block Size

1. **問題根源與優化方向**
* **記憶體存取是瓶頸**：CUDA 優化的核心在於解決記憶體存取瓶頸。
* **多層次的記憶體存取**：記憶體存取有多個層次，從主機 (host) 與設備 (device) 間的資料傳輸 (data transfer)，到全域記憶體 (global memory access) 和共用記憶體 (shared memory access)，每一層都有其適合的優化方式。
* **存取模式的重要性**：大部分的優化方法都與存取模式 (access pattern) 有關。若採用 **線性化位址 (linearized addressing)** 或 **連續記憶體存取 (sequential memory access)**，無論是在全域記憶體還是共用記憶體，通常都能獲得更好的效能 (better performance)。
* **CUDA 程式挑戰**：將程式碼移植到 GPU (透過 CUDA、OpenACC、OpenCL) 相當容易，因為它適合迭代計算 (iteration) 和大量資料平行 (data parallel) 的應用。然而，**要讓程式碼跑得快卻非常困難**，可能需要許多技巧，且常與硬體綁定，利用新的函式庫或硬體堆疊能帶來顯著的效能提升。
* **效能改善潛力**：真正的 CUDA 優化能帶來驚人的效能提升，可能達到 **2-3 倍，甚至 10 倍以上**。本次範例最終可達到 **30 倍的效能提升**。

2. **範例應用：Reduction 函式**
* **應用描述**：一個非常簡單且基本的 **reduction 或 reduce 函式**，目標是計算大量數字的總和。
* **演算法**：使用遞迴的樹狀結構 (recursive tree) 進行reduction ，複雜度為 logN。這種演算法具備平行化能力，適合 GPU 加速。
* **GPU 上的注意事項**：由於 GPU 硬體運作原理，即使是簡單的概念也需注意重要細節。Reduction 是一種同步計算 (synchronous computation)，每個迭代之間需要 **屏障 (barrier)** 以避免同步問題。

3. **GPU 上的全域同步問題 (Global Synchronization Problem)**
* **問題的產生**：當問題規模 (problem size) 變大時，GPU 會出現問題。所需的屏障必須是全域的 (global barrier)。
* **區塊間無法同步**：由於 GPU 的記憶體限制 (如共享記憶體有限)，當資料元素過多無法全部放入一個區塊 (block) 內時，會被迫使用多個區塊。**GPU 的區塊 (blocks) 之間無法直接進行同步 (沒有 barriers 存在)**。
* **範例說明**：如果一個區塊只能處理 4 個資料元素，處理 8 個元素就需要 2 個區塊。若最後一層的計算 (例如 11 + 14 = 25) 涉及不同區塊的結果，由於沒有屏障，計算 25 可能在 14 還未算完時就進行，導致錯誤的結果 (如答案變成 11)。

4. **解決全域同步問題：核心分解 (Kernel Decomposition)**
* **概念**：將計算拆解成**多個核心 (multiple kernels)**。
* **同步原理**：當多個核心提交 (submit) 到同一個串流 (stream) 時，它們會被序列化 (serialize)。這表示前一個核心必須完全執行完畢，後一個核心才能開始執行。
* **提供同步點**：**核心之間存在同步點 (synchronization point)**。前一個核心的所有區塊必須先完成，後一個核心的區塊才能開始執行。因此，核心分解可以作為一種全域同步的機制。
* **範例應用於 Reduction**：
* 將整個計算拆解成多個層次 (e.g., Level 0, Level 1)，而不是一次在一個核心中完成所有層次。
* **拆解原則**：同一層次內的所有區塊都是獨立的，它們之間沒有資料依賴關係，不需同步。
* 例如，一個區塊處理 8 個資料元素，Level 0 核心只執行其局部的迭代 (e.g., 3 個迭代)，將 64 個元素約減成 8 個元素。
* 問題規模被縮小 (problem is reduced)，然後這 8 個結果作為輸入，由**第二個核心 (second kernel)** 執行後續計算。
* 如果第二個核心仍需多個區塊，則繼續分解成第三個核心，以此類推，直到問題解決。核心分解能提供所需的全域同步。
* **替代解決方案 (不建議)**：
* 在全域記憶體中設定一個旗標 (flag) 或計數器 (counter)。每個區塊完成後對其進行原子遞增 (atomic increment)，當計數達到所有區塊完成的條件時，再進行後續操作。
* **缺點**：這種方法會有較高的額外開銷 (overhead)，因為原子操作會強制區塊序列化，且持續檢查變數會引入競爭條件 (race condition) 和額外延遲，效能不理想。
* **結論**：核心分解是最單純且有效率的方案。後續的優化將聚焦於單一區塊內，因為核心分解已使區塊間彼此獨立。

5. **區塊內優化策略**
* **效能測量基準**：
* **時間 (milliseconds)**：值越小越好，但難以判斷是否達到極限。
* **記憶體頻寬 (Memory Bandwidth, GB/second)**：這是 GPU 測量效能時更好的基準。
* 計算方式：(資料量 * 4 Bytes) / 時間。
* **優點**：頻寬越大越好，且有**全域記憶體頻寬的硬體上限** 可供參考，能得知還有多少優化空間。
* **基準效能**：初始程式碼僅達到 **2 GB/s**，而該 GPU 硬體規範為 **80 GB/s** (僅用到 1/40)，顯示效能極差。

* **優化 1：減少 Warp Divergence**
* **問題描述**：一個 warp 內的執行緒 (threads) 執行不同的指令。
* **原始程式碼問題**：在 Reduction 的第一個步驟，雖然需要 8 個執行緒，但由於其存取模式是跳躍式的 (e.g., thread ID 0, 2, 4, 6...，中間有空缺)，造成同一 warp 內部分執行緒閒置。若 warp size 為 4，8 個執行緒卻使用了 4 個 warp (共 16 個執行緒空間)，一半的執行緒被浪費，運算利用率僅 50%。隨著迭代次數增加，有效執行緒數量減少，但使用的 warp 數量可能維持不變，導致 GPU 運算資源的利用率更低。
* **檢測難度**：GPU 利用率的監測工具可能顯示高利用率 (例如 100%)，但實際上許多運算並無意義，因此 Warp Divergence 問題難以透過工具直接察覺，需解析程式碼。
* **優化方法**：**改寫執行緒索引 (thread ID) 的邏輯**，使其連續執行，關閉閒置的執行緒，讓每個 warp 內的執行緒都能有效工作。
* **優化結果**：效能提升 **2.3 倍**，頻寬約 5 GB/s。

* **優化 2：解決 Shared Memory Bank Conflicts**
* **問題描述**：共用記憶體被劃分為多個 bank，當同一 warp 內的執行緒同時存取位於同一 bank 的資料時，會發生 bank 衝突，導致存取序列化，降低效能。
* **原始程式碼問題**：執行緒的資料存取是跳躍式的 (striped)，例如 thread 0 存取 index 0，thread 1 存取 index 2，thread 2 存取 index 4。如果這些位址剛好是 2 的倍數，很容易產生 bank 衝突。
* **解決方案**：
* 記憶體填充 (Memory Padding)：增加記憶體空間以錯開 bank 位置。
* **連續位址存取 (Sequential Addressing / Linear Addressing)**：讓執行緒存取連續的記憶體位置。
* **優化方法**：修改寫入共用記憶體的位址索引，使其結果寫入連續的記憶體位置，避免跳躍式的寫入。通常建議使用連續位址存取，因記憶體填充可能增加記憶體存取量。
* **優化結果**：效能再提升 **2 倍**，總加速達到 **4.68 倍**。

* **優化 3：提升執行緒利用率 / 縮小區塊大小 (Thread Utilization / Block Size)**
* **問題描述**：原始程式碼在從全域記憶體載入資料到共用記憶體時，為 16 個資料元素建立了 16 個執行緒 (一個執行緒搬運一個資料元素)。但載入完畢後，只有一半的執行緒需要進行實際的 reduction 計算，導致許多執行緒閒置。
* **影響**：對於大規模問題，需要大量區塊輪流執行，若區塊大小不必要地大，會佔用更多串流處理器 (stream processor) 資源，降低整體平行度。
* **優化方法**：讓**一個執行緒負責搬運兩個資料元素**，並在搬運時順便進行初步的加法運算。這減少了所需的執行緒數量和區塊大小，提高執行緒的有效利用率。
* **優化結果**：效能再提升 **1.78 倍** (接近 2 倍)，總加速約 **8.3 倍**。

6. **其他優化方法**
* **主機-設備資料傳輸優化**：
* 使用串流 (stream) 進行管線化 (pipelining)。
* 重疊 (overlap) 計算與通訊 (communication)。
* 減少資料傳輸量。
* **以計算取代記憶體搬移 (compute instead of memory movement)**：有些資料可透過計算推導出來，只傳輸少量資料，讓 GPU 執行推導計算，減少實際搬移的資料量。
* **計算密集型 (Compute-bound) 應用**：
* **以記憶體換取計算**：當記憶體不是瓶頸時，可以將部分計算轉移到記憶體存取。
* **CPU 預計算與查表 (Lookup Table)**：將一些 GPU 不擅長或執行緩慢的計算 (例如分支多的操作 `branch`) 在 CPU 上預先計算好，建立查找表 (table) 並載入到 GPU 記憶體。GPU 執行時直接查表獲取結果，加速其擅長的部分。
* **應用範例**：iratal coding 演算法，其編碼過程涉及分支計算，可透過 CPU 預計算並建立查表來優化。
* **迴圈展開 (Loop Unrolling)**：
* 減少迴圈終止條件的檢查 (iteration termination branch)，可提升效能。
* 僅展開最後一個 warp 的迴圈可加速近 2 倍，完全展開可額外加速 1.4 倍。

7. **總體效能與結論**
* **最終效能**：所有優化方法應用後，資料處理速度達到 **62.67 GB/s**。
* **接近硬體上限**：該 GPU 的全域記憶體頻寬上限為 73 GB/s，達到 62.67 GB/s 意味著已達到約 **76% 的硬體效能**，是非常優異的結果。
* **總加速倍數**：所有技巧結合起來，總共達到約 **30 倍的加速**。
* **優化程式碼的複雜性**：高度優化的 CUDA 程式碼通常會變得難以閱讀，且可能涉及各種奇特甚至針對特定硬體和編譯器的技巧，但這是為了追求極致效能的必要犧牲。
* **建議**：鼓勵學生多參考線上資源和範例，並儘早開始作業實作，將所學優化方法應用於實際問題，因為「聽可能大家就是有個概念而已」。

---
其他課程連結

[平行程式1C~2B Introduction parallel programming](https://hackmd.io/@6FOC2dvARe-Vz0kVSyajew/Syxh3H7Kxe)
[平行程式3A~3D The Latest Developments and Applications Using Parallel Programming](https://hackmd.io/@6FOC2dvARe-Vz0kVSyajew/HJh7QFVKle)
[平行程式4A~4B IO Parallel IO and Program Analysis](https://hackmd.io/@6FOC2dvARe-Vz0kVSyajew/HJLMsuHFgg)
[平行程式5A~5B The Latest Developments and Applications Using Parallel Programming](https://hackmd.io/@6FOC2dvARe-Vz0kVSyajew/SJh57hIFle)
[平行程式6A~6B Communication Routines and Parallel Function Code](https://hackmd.io/@6FOC2dvARe-Vz0kVSyajew/r1X9kX_Fle)
[平行程式 6C~6D Communication Routines and Parallel Function Code](https://hackmd.io/@6FOC2dvARe-Vz0kVSyajew/S1DPjoYFlx)
[平行程式 7A~8A Pthread:Synchronization Problem & Tools](https://hackmd.io/@6FOC2dvARe-Vz0kVSyajew/HJu-_0tKge)
[平行程式 8B~8D Synchronization Tools & Open Multi-Processing(OpenMP)](https://hackmd.io/@6FOC2dvARe-Vz0kVSyajew/H1ki4E2Fee)
[平行程式 9A~9B Synchronization Construct](https://hackmd.io/@6FOC2dvARe-Vz0kVSyajew/BJTYMrpKlx)
[平行程式 10A~10B Synchronization Tools & Open Multi-Processing Synchronization Construct](https://hackmd.io/@6FOC2dvARe-Vz0kVSyajew/B1cY6M1qee)
[平行程式 10C~10D Synchronization Tools & Open Multi-Processing Synchronization Construct](https://hackmd.io/@6FOC2dvARe-Vz0kVSyajew/BkgFaNg5gg)
[平行程式 11A~11B Parallel Work Pool and Termination / Parallel Sorting](https://hackmd.io/@6FOC2dvARe-Vz0kVSyajew/H1hfOw-5xl)
[平行程式 12A~12B Parallel Sorting and Pipelined Computations](https://hackmd.io/@6FOC2dvARe-Vz0kVSyajew/Symo-zQ9eg)
[平行程式 12C~12D Parallel Sorting and Pipelined Computations](https://hackmd.io/@6FOC2dvARe-Vz0kVSyajew/BJYNKDVceg)
[平行程式 13A-13B Sychronous Parallelism](https://hackmd.io/@6FOC2dvARe-Vz0kVSyajew/HJ2UJ2Bqex)
[平行程式 14A~14B Heterogeneous Computing](https://hackmd.io/@6FOC2dvARe-Vz0kVSyajew/BksS4yP5eg)
[平行程式 14C~14D Heterogeneous Computing](https://hackmd.io/@6FOC2dvARe-Vz0kVSyajew/BJrfTUd9xx)
[平行程式 15A~15B Parallel Programming Model on GPU](https://hackmd.io/@6FOC2dvARe-Vz0kVSyajew/ByWnl-t5gg)
[平行程式 16A~16B What is Compute Unified Device Architecture(CUDA)?](https://hackmd.io/@6FOC2dvARe-Vz0kVSyajew/HyYpsjcqgl)
[平行程式 17A~18A 平行運算的CUDA](https://hackmd.io/@6FOC2dvARe-Vz0kVSyajew/H1dUeBT5lg)
[平行程式 18B~19A 記憶體層級 / CUDA的優化](https://hackmd.io/@JuitingChen/HyF44e1jge)
[平行程式 19B~19D 記憶體層級 / CUDA的優化 ](https://hackmd.io/@JuitingChen/ryPEu4lieg)
[平行程式 20A~20B CUDA優化全域和區域記憶體/共享記憶體](https://hackmd.io/@JuitingChen/r1X659Zoxl)
[平行程式 21A~21B Parallel Reduction / Distributed Computing Framework](https://hackmd.io/@JuitingChen/HyiOpozjxl)
[平行程式 NTHU-PP-Chap10-Big Data-Part1 ](https://hackmd.io/@JuitingChen/Hyc-e3Golx)
[平行程式 NTHU-PP-Chap10-Big Data-Part2 ](https://hackmd.io/@JuitingChen/ryC_QTXoxl)
[平行程式 NTHU-PP-Chap11-MapReduce](https://hackmd.io/@JuitingChen/HJgBXJOsge)
[平行程式 NTHU-PP-Chap12-Distributed Training-Part1](https://hackmd.io/@JuitingChen/ryh5hBtsge)
[平行程式 NTHU-PP-Chap12-Distributed Training-Part2](https://hackmd.io/@JuitingChen/rJ2G7kdjxg)
[平行程式 NTHU-PP-Chap12-Distributed Training-Part3](https://hackmd.io/@JuitingChen/HkA471dilx)
[平行程式 NTHU-PP-Chap13-UCX-Part1](https://hackmd.io/@JuitingChen/rJbq103ieg)
[平行程式 NTHU-PP-Chap13-UCX-Part2](https://hackmd.io/@JuitingChen/SJpNmk_ixl)
[平行程式 NTHU-PP-Chap13-UCX-Part3](https://hackmd.io/@JuitingChen/HkIUYa13xe)