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

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

20A~20B CUDA優化全域和區域記憶體/共享記憶體

今日大綱
1.Device Memory 優化總覽
2.Global Memory 存取優化
3.減少 Global Memory 存取次數
4.Shared Memory 存取優化
5.記憶體存取模式優化 (Data Layout)

**一、 Device Memory 優化總覽**

* GPU 優化第二部分著重在記憶體架構。
* 記憶體傳輸涉及 **host memory 到 device memory**。
* GPU 裝置記憶體最外層包括 **Global Memory 和 Local Memory**。
* **Local Memory** 實際上是 register spill (暫存器溢出)，即 local variable 放置於 device 上時的區域，其效能通常較差，因此優化相對重要。
* **優化目標**：配合硬體裝置的優化，讓程式效能發揮出來。

**二、 Global Memory 存取優化**

1. **Coalesced Memory Access (合併記憶體存取)**
* **定義**：硬體會自動檢查 Warp 中所有執行緒讀取資料的位置。如果這些資料在 Global Memory 上是**連續的**，硬體會將這些獨立的存取請求組合成一個 **batch 或 group**，一次讀取出來，從而提高速度。
* **原理**：減少 I/O 請求的延遲 (request latency) 和 overhead，避免因多次獨立請求造成的慢速問題。
* **優化條件**：
* **資料連續性**：Warp 內各執行緒讀取的資料在實體記憶體上是連續的。
* **對齊快取行 (Cache Line Alignment)**：讀取位置必須對齊記憶體的 cache line 邊界。
* **cache line 特性**
* Global Memory (尤其是 L1 cache) 內部有 cache line 設計。
* 如果讀取資料的範圍**橫跨多個cache line**，即使資料量不大，也可能因為讀取多個 cache line 而導致總體時間增加。
* **cache line 大小**：
* L1 快取通常為 128 位元組 (bytes)。
* 上層 (更快速) 的快取對大小更敏感，設計上可能較小，例如第二層可能為 32 位元組。
* **資料類型影響**：浮點數 (F32F) 是常見單位；整數 (integer) 通常更容易對齊。
* **重點**：確保連續的資料能夠被合併存取。如果資料不連續，則無法實現合併存取。

2. **範例：矩陣轉置 (Matrix Transposition) 優化**
* **問題描述**：
* 一個 2D 陣列進行轉置 (row major 變 column major)。
* 從 Global Memory 讀取輸入資料 (通常是 row major，連續存取，速度快)。
* 將轉置後的結果寫回 Global Memory。如果直接寫入 column major 格式，則寫入位置會是非連續的 (例如每四個元素才寫一個，稱為 "strided" 或 "scatter" 存取)，導致寫入速度變慢。
* **解決方案：使用 Shared Memory (共享記憶體)**
* **原理**：Shared Memory 位於 Global Memory 和 Register 之間，可以作為一個高速緩衝區。Global Memory 讀取時需要合併存取 (coalesced)，但 Shared Memory 不一定需要。
* **優化步驟**：
1. 將資料從 Global Memory **連續地 (coalesced)** 讀取到 Shared Memory 中。
2. 在 Shared Memory 中進行轉置操作 (此時讀寫模式可能非連續，但因為 Shared Memory 速度快，影響較小)。
3. 將 Shared Memory 中的轉置結果**連續地 (coalesced)** 寫回 Global Memory (按照 Global Memory 的 row major 方式寫入)。
* **效益**：儘管增加了從 Shared Memory 寫回 Global Memory 的額外步驟，但由於 Global Memory 的讀寫都變成連續的，整體效能會大幅提升。Shared Memory 的速度優勢彌補了額外操作的開銷 (僅約 1% 的差異，但帶來的 Global Memory 提速遠超此開銷)。
* **原則**：Global Memory 的讀寫盡量讓其保持連續。可以透過 Shared Memory 來改變資料存取模式，確保 Global Memory 存取是連續的。

**三、 減少 Global Memory 存取次數 (資料重用)**

1. **計算強度 (Computational Intensity - CI) 分析**
* **目標**：避免記憶體成為計算瓶頸 (memory bound)。
* **定義**：計算操作次數與 Global Memory 存取次數的比率。
* **判斷基準**：透過查詢 GPU 硬體規格，例如計算能力 (FLOPs) 與 Global Memory 頻寬 (bytes/s) 的比值。若某 GPU 的 CI 基準為 64 (例如 4000 FLOPs / 250 bytes)，表示每讀取一次資料，需要執行 64 次計算才能充分利用計算資源。
* **若程式 CI 低於基準**：表示記憶體存取時間大於計算時間，成為記憶體瓶頸。
* **範例分析**：
* 一個簡單的迴圈運算 (`C = A + B`)。
* 每次迭代執行 2 次計算 (1 次乘法，1 次加法)。
* 每次迭代執行 2 次 Global Memory 讀取 (A 和 B 的元素)。
* CI = 2 (計算) / 2 (讀取) = 1:1。
* **結果**：1:1 的 CI 遠低於目標 64，因此存在嚴重的記憶體瓶頸。
* **目標**：提高 CI 到接近硬體基準值，例如將記憶體存取次數減少 6 倍或將計算次數增加 6 倍。

2. **透過 Shared Memory 提高資料重用**
* **原理**：許多程式存在資料重複使用 (data reuse) 行為。將 Global Memory 中會重複使用的資料載入到速度更快的 Shared Memory 中，然後在 Shared Memory 中進行計算。
* **優化步驟**：
1. 先將輸入資料 (A 和 B) 從 Global Memory 複製到 Shared Memory。
2. 之後的計算完全從 Shared Memory 讀取資料。
* **效益分析** (以 N x N 矩陣乘法為例)：
* 每個執行緒完成一次計算只進行 2 次 Global Memory 讀取 (複製到 Shared Memory 時)。
* 每個執行緒進行 2 * N 次計算 (對於 N 次迭代的迴圈)。
* **CI = (2 * N) / 2 = N**。
* **結論**：CI 與矩陣大小 N 成正比。N 越大，CI 越高，加速效果越顯著，因為資料重用量越大。
* 若 N > 64，即可有效解決記憶體瓶頸問題。
* **Shared Memory 大小限制**
* Shared Memory 的容量有限 (例如 48KB)。
* 若 N=1024，三個 N x N 的矩陣 (A, B, C) 需要 12MB 的 Shared Memory 空間，遠超過一個 Block 可用的 Shared Memory 容量，導致無法一次載入所有資料。

3. **分塊 (Tiling / Blocking) 優化**
* **目的**：解決 Shared Memory 容量不足的問題，同時維持高資料重用率。
* **原理**：將大型矩陣分割成適合 Shared Memory 大小的「塊」(tile/block)，每次只載入一個塊到 Shared Memory 進行計算，然後再處理下一個塊。
* **資料重用**：這種方法確保了被載入的塊在 Shared Memory 中能被充分重用，提高計算效率。
* **決定分塊大小 (W)**
* `W` 代表每個分塊的長寬。`W` 越大，資料重用率越高。
* 根據可用的 Shared Memory 大小來決定 `W` 的最大值。
* **範例**：若有 48KB 的 Shared Memory，用於存放 A, B, C 三個矩陣塊，則最大的 `W` 可以達到 64 (即 64x64 的塊)。
* **目標**：在有限的記憶體容量下增加資料重用次數，減少 Global Memory 存取次數，提升效能。
* **注意事項**
* 過度優化 CI (例如遠超 64:1) 可能不見得帶來最佳效能，因為可能導致執行緒過多、競爭計算資源，或產生過多的小塊，反而降低效率。
* GPU 是以 Warp 為單位進行排程。

**四、 Shared Memory 存取優化**

1. **Bank Conflicts**
* **架構**：Shared Memory 被分成多個記憶體庫 (banks)，例如每個 bank 約 4 位元組。資料在 bank 間以循環 (round-robin) 方式存放 (bank 0, bank 1, bank 2, bank 3, 然後回到 bank 0 等)。
* **問題**：如果同一個 Warp 中的多個執行緒同時存取**同一個記憶體庫**中的不同資料，就會發生 Bank Conflict。這些存取會被序列化 (serialize)，導致等待，降低效能。
* **最佳存取模式**：
* 每個執行緒存取不同的記憶體庫 (例如線性連續位址存取)。
* 即使是非連續位址，只要每個執行緒在同一時間只存取一個獨特的記憶體庫，效能也會很好。
* **特殊情況：Broadcast (廣播)**
* 如果同一個 Warp 中，多個執行緒（尤其是半個 Warp 的執行緒，例如 16 個）同時存取**同一個記憶體位置**的資料，Shared Memory 可以將該資料廣播給這些執行緒，不會產生衝突。
* 這不適用於寫入操作。

2. **解決 Bank Conflicts (Padding / Strading)**
* **原理**：在 Shared Memory 陣列中加入「填充」元素 (padding)，以改變資料的記憶體佈局，確保同時被存取的資料落入不同的記憶體庫。
* **範例**：
* 如果矩陣維度剛好等於記憶體庫的數量 (例如 32x32 矩陣和 32 個記憶體庫)，直接存取可能會導致嚴重的 Bank Conflict (所有執行緒都存取同一個 bank)。
* 透過在每行末尾增加一個無意義的填充元素，可以將資料位址錯開，使得原本會衝突的存取分散到不同的記憶體庫中，大幅提升效能。
* **重點**：記憶體佈局 (data layout) 非常重要。避免同時被讀取的資料以 32 (或其他 bank 數量) 為單位進行存取，可以透過增加一些無用的元素來錯開記憶體佈局。

**五、 記憶體存取模式優化 (Data Layout)**

1. **總體原則**：無論 Global Memory 還是 Shared Memory，核心原則都是讓記憶體存取模式盡量**連續 (coalesced)**，以實現最高效能。
* 對於一維陣列，執行緒的索引如果連續，通常能實現連續存取。

2. **Array of Structures (AoS) 與 Structure of Arrays (SoA) 的選擇**
* **問題情境**：當處理「結構體陣列」(Array of Structures, AoS)，例如 `struct Point { float x, y, z; }; Point points;`。
* **AoS 的缺點**：如果計算通常針對某個特定分量 (例如所有點的 `x` 座標)，那麼 `points.x`, `points.x`, `points.x` 在記憶體中是非連續的 (中間夾雜著 `y` 和 `z` 座標)，導致存取分散，效能不佳。
* **SoA 的解決方案**：將資料重新組織為「陣列的結構體」(Structure of Arrays, SoA)，例如 `struct Points_SoA { float x, y, z; };`。
* **SoA 的優勢**：當資料以 SoA 形式存放時，所有 `x` 座標是連續的，所有 `y` 座標是連續的，所有 `z` 座標也是連續的。這樣當執行緒對單一分量 (例如所有 `x` 座標) 進行操作時，記憶體存取會是連續的 (coalesced)，大幅提升效能。
* **結論**：SoA 雖然可能不那麼直觀，但在硬體層面的記憶體佈局和效能上通常優於 AoS。

**六、 總結與展望**

* GPU 優化需要深入理解硬體架構，並配合修改程式碼，即使這些修改可能不直觀、看起來「醜陋」，甚至引入額外步驟 (如 Shared Memory 緩衝)，但最終能帶來顯著的效能提升。
* **兩個最重要優化原則**：
1. **減少記憶體存取次數**。
2. **優化記憶體存取模式**：確保存取是連續的 (coalesced)。
* 後續將透過一個具體的 **Reduce 運算實例**，逐步展示如何應用所有優化技術，以實現顯著的計算時間加速 (例如在舊 GPU 上達到 30 倍加速)。

---
其他課程連結

[平行程式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)