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

20250919 筆記
內容可能有錯僅供參考
在這個章節開始投影片和10710周志遠教授平行程式有差異，接下來以
NTHU-PP-2021 (Chinese) 為主

[NTHU-PP-Chap12-Distributed Training-Part2](https://www.youtube.com/watch?v=yOZYl_hVnvM&list=PLQTDfc8kgjhMKtgumyK0gmEelnTtqJGsp&index=28&t=1564s)

進入到分散式深度學習部分，這部分是新的並沒有包含在 2018 年的影片

今日大綱
1.善用平行計算資源的策略
2.模型平行
3.資料平行
4.分散式訓練的平行化類型
5.效能優化策略

### 一、 深度學習計算基礎

2. **深度學習計算方法**
* 深度學習的計算方法是相當重要的。
* 核心演算法是 **梯度下降法 (gradient descent algorithm)**。
* 計算過程通常涉及：
1. **前向傳播 (forward propagation)**。
2. 計算梯度 (gradient)。
3. 使用 **後向傳播 (backward propagation)** 更新模型權重 (model weight)。
* 這是一個不斷重複的迭代計算過程，原則上是 **同步** 的。

### 二、 善用平行計算資源的策略

面對大型平行計算系統或叢集 (cluster)，有幾種方式可利用這些資源：

1. **多使用者資源共享 (Multi-user sharing)**
* 大型系統通常由多人共用。
* 不同的使用者會有不同的計算工作（訓練自己的模型）。
* 資源可以透過多人的共享方式分配出去。
* 每個 Job 可以在獨立的 GPU 或 Node 上執行。
* **優點**：在計算上不需要做任何變動或平行化。

2. **超參數調校 (Hyperparameter Tuning)**
* 模型訓練時有許多訓練參數（如學習率 (learning rate)、dropout、層數 (layer)）可以調整。
* 這些參數會影響最終訓練結果，且其取值範圍和可選擇的值非常多。
* 為了找到最佳參數設定，可能需要反覆進行相同的模型訓練。
* 每次使用不同參數設定去重複訓練模型，這是一個獨立的計算工作。
* **利用平行資源**：可以一次將多組參數設定撒下去，讓它們同時訓練。
* **優點**：訓練的核心程式碼本身不需要做任何平行化。

3. **分散式訓練 (Distributed Training)**
* 這是指使用多個 GPU 或 Node 去訓練 **單一模型**。
* 此訓練過程必須被 **平行化**。
* 通常目的是為了減少執行時間，在時間限制內完成模型訓練。
* 分散式訓練是一種平行計算的方式，探討如何將特定的運算 (演算法) 平行化，來利用平行計算能力。

### 三、 分散式訓練的平行化類型 (Distributed Training Parallelism)

分散式訓練主要分為兩大類型：模型平行 (Model Parallelism) 和資料平行 (Data Parallelism)。

#### 1. 模型平行 (Model Parallelism)

* **定義**：將神經網路模型 (計算圖/graph) 本身進行 **切分 (partition)**。
* **分配方式**：將圖切成數塊，每塊分配給一個機器/GPU。每塊包含圖上的一些節點（通常稱為 operator，例如 convolution、filter 等 function）。
* **計算負擔**：每台機器只需負責部分的計算。
* **優點**：可減少單機的計算量和計算時間。
* **資料流動**：所有資料必須流經所有機器，以完成前向和後向傳播的計算。

* **限制與挑戰**：
* **資料依賴性 (Data Dependency)**：機器之間存在資料依賴性，取決於資料的流動。例如，Machine 1 的輸出需要餵給 Machine 2 和 Machine 3。
* **管線化 (Pipelining)**：雖然存在資料依賴，但深度學習可以透過 **管線化** 的方式（一筆一筆處理資料），讓機器之間仍能重疊計算時間。
* **溝通成本 (Communication Cost)**：完全取決於如何切分計算圖。切邊 (cutting edge) 的地方代表資料傳輸。若圖的邊 (edge) 太多、太複雜，或切得太零碎，會增加溝通的開銷。
* **程式碼複雜度**：需要插入溝通程式碼，插入位置取決於圖的切分方式，缺乏固定的規律。因此，寫出 Model Parallelism 的平行化程式碼相對複雜，不易自動化。

* **適用情境**：
* **共享記憶體環境 (Shared Memory)**：Model Parallelism 較常見於共享記憶體環境（如單一節點，多張 GPU）。在這種情況下，溝通可透過記憶體參考 (memory reference) 實現，不需要額外插入 Send/Receive API。
* **溝通成本**：在單節點內，溝通成本較低（頂多是 Main memory 或 GPU-to-GPU 的 Peer-to-Peer 傳輸）。
* **模型過大 (Over-sized Model)**：當模型過大，無法載入單張 GPU 的記憶體時（GPU 記憶體有限，約 8G~32G），必須使用 Model Parallelism 將大模型切分，塞入個別 GPU 以完成訓練。

#### 2. 資料平行 (Data Parallelism)
* **定義**：與 Model Parallelism 相反。
* **模型複製 (Replication)**：每個機器/GPU 都複製了一份完整的模型。
* **資料切分 (Partition)**：整個資料集被切分成多份，每台機器負責訓練其區域資料集。
* **計算過程**：機器使用其區域資料集訓練其區域模型。
* **溝通需求**：為了訓練出單一的模型，不能完全獨立訓練。在每次前向/後向傳播結束後，機器之間必須對梯度執行 **Reduce** 的動作。
* **模型同步**：機器獲得平均梯度後，各自獨立地根據此平均梯度更新其區域模型。由於是同步計算，最終所有機器的模型權重會是一致的。
* **溝通發生時機**：僅發生在梯度交換的部分，即在前向和後向傳播之間。

* **優點**：
* 符合標準的 **Divide and Conquer** 平行計算方法。
* 非常適合 **跨 Node** 執行，因為溝通與計算可以完全切開，溝通的複雜度不會隨模型複雜度增加。
* 實作程式碼相對容易，只需在 Forward 之後呼叫一個 Communication API 即可。

* **限制**：
* **模型大小限制**：模型必須能夠 **裝入單卡或單機的記憶體**。由於模型是複製的，它累積的記憶體大小會比 Model Parallelism 高。
* **溝通瓶頸**：溝通成本（由模型大小決定）仍然容易成為性能瓶頸。模型越大，要交換的參數越多，資料傳輸越大，開銷越高。
* 在模型很大但計算量相對少時，難以達到理想的加速比。

#### 3. 混合使用原則

* **單節點內 (Single Node)**：通常使用 **Model Parallelism**，因為共享記憶體環境有利於框架調度 (schedule) 任務到不同 GPU 上。
* **跨節點間 (Cross Node)**：通常使用 **Data Parallelism**。框架會提供 API 讓使用者/程式設計師呼叫，以實現跨機器的分散式訓練。

### 四、 Data Parallelism 的實作與溝通優化

Data Parallelism 核心是處理參數交換 (parameter swap)，即取得平均梯度並通知所有 Worker。

#### 1. 集中式 (Centralized) 溝通：參數伺服器 (Parameter Server)

* **架構**：存在一個集中式的伺服器，通常在一個獨立的 Node 上，不參與訓練計算。
* **伺服器職責**：唯一的職責是維護權重/梯度。
* **流程**：
1. 計算 Worker 將其梯度交給 Parameter Server。
2. Server 收集所有梯度後取平均值，並更新模型權重。
3. Server 將更新好的權重廣播回到所有 Worker。
4. Worker 拿到相同的值後，更新區域權重，進行下一輪訓練。
* **缺點**：Parameter Server 容易成為性能瓶頸 (hotspot)，尤其當 Worker 數量太多時。
* **去中心化 (Decentralization) 解決方案**：可以設立多個 Parameter Server。由於深度學習中每個參數的更新是完全獨立的，可以讓不同 Server 負責不同的參數子集。
* **去中心化挑戰**：
* **數量控制**：Server 數量太少會導致平行度不足，過多則溝通成本可能超過平行化優勢。Worker 須送出的訊息數量與 Server 數量成正比，Server 越多，溝通效率越低。
* **負載平衡 (Load Balancing)**：很難做到完美的負載平衡。雖然可以確保每個 Server 負責相同數量的參數或 Tensor，但這些 Tensor 的大小 (dimension/size) 可能不同，導致資料傳輸量和網路頻寬使用不均，造成某些 Server 負載過高。
* **應用場景**：Parameter Server 架構具有支持 **非同步 (Asynchronous)** 溝通的優勢。在性能不穩定、資源異質性高或機器可能故障 (fail) 的計算環境（如雲端、AP device）下，Parameter Server 具有較大優勢。

#### 2. P2P 溝通：AllReduce

* **架構**：完全分散式的做法，旨在確保每個 Worker 的工作負載完全相同，且不需額外的 Server。
* **機制**：使用 P2P 溝通模式實現集體溝通程式碼 (collective code)。
* **Ring AllReduce**：一種常見的實現方式。
* 將所有 Worker 或參與訓練的 Node 串成一個 **環 (Ring)**。
* 每個 Worker 同時將資訊（區域參數/梯度）單一方向傳輸給下一個 Worker。
* 資料遍歷環一圈後，基本上所有 Worker 都能得到所有人的資料，然後更新區域權重，完成參數交換。
* **優點**：
* 每輪傳輸量完全相同，無熱點 (HP) 問題。
* 使用 pairwise 的頻寬，可利用所有 Worker 的連線 (link)，因此性能和穩定性可能比 Server 更好。
* 目前 AllReduce 是分散式訓練中的 **主流** 方式，尤其在高頻寬、高性能的叢集系統中。

* **限制**：
* **必須是同步 (Synchronous) 計算**：AllReduce 是一種集體程式碼，如果一個 Worker 計算速度太慢，會拖累所有人。
* **適用環境**：最適合高性能、穩定的 Supercomputer 或 HPC 叢集環境，確保機器效能和網路一致。

### 五、 效能優化策略

除了溝通方式的選擇外，還有多種優化方法可以應用。

#### 1. Batch Size 控制 (Batch SGD)

* **基礎概念**：標準 SGD 是一筆一筆處理資料，無法充分利用 GPU 的平行計算能力。Batch SGD 或 Mini-Batch SGD 是一次餵入一批 (batch) 記錄，讓 GPU 平行處理。
* **效能影響**：Batch Size 對效能有很大影響。
* **Batch Size 過小**：平行度低，硬體利用率下降，訓練時間變長。
* **Batch Size 過大**：收斂 (convergence) 效果變差。這是因為同一個 Batch 內計算出的梯度會被平均，重要的特徵點信號可能被平均掉。結果是需要更多的迭代次數才能達到收斂。
* **實務選擇**：Batch Size 的選擇通常是 **越大越好**，但會受到 GPU 記憶體大小的限制。

#### 2. 非同步 SGD (Asynchronous SGD, A-SGD)

* **目的**：當 Worker 計算速度有差異時，避免被最慢的 Worker 拖累。
* **機制**：Worker 算完梯度後，立即根據其梯度更新權重，不需要等待其他 Worker 或取平均梯度。
* **後果**：訓練過程中，每個 Worker 區域模型 (local model) 的 **版本是不一致的**。
* **收斂影響**：版本不一致會導致錯誤的判斷，當 Worker 根據舊版本 (stale version) 算出的梯度進行更新時，可能覆寫 (overwrite) 掉前面版本的影響，造成不準確性。這會導致需要更多的迭代次數才能收斂。
* **優勢**：若同步延遲嚴重，A-SGD 可以縮短單次迭代時間，雖然總體需要更多迭代，但可能在最短時間內達到收斂。
* **適用性**：Parameter Server 支持 A-SGD。

#### 3. 延遲同步 SGD (Stale Synchronous SGD, S-SGD)

* **定義**：實際應用中比純 A-SGD 更常見的折衷方案。
* **機制**：限制最快與最慢 Worker 之間的 **不一致程度（延遲/staleness）**。
* 不一致程度的定義是：最快 Worker 跑的步驟數 (step number) 與最慢 Worker 執行的步驟數之間的差距，必須被限制在一個範圍內。
* 若最快 Worker 達到差距上限，它必須停止下來等待慢速 Worker 追上。
* **實作**：S-SGD 較常被實現在現有的框架中，使用者可以調整參數來控制最大的容忍範圍。

#### 4. 資料壓縮與量化 (Quantization and Compression)

* **目的**：減少傳輸資料量，直接降低溝通時間和網路頻寬消耗。
* **量化 (Quantization)**：使用更少的位元數 (bit) 來描述一個值，但希望計算結果不變。
* **One-bit compression)**：利用深度學習是迭代演算法，適合回饋控制迴路 (feedback control loop) 的特性。將要傳輸的數值（如梯度或權重）壓縮成 0 或 1，表示該值是比平均值小或大。
* 例如，將 32 bit 的 double precision 數值壓縮成 1 bit，可達到 32 倍壓縮，大幅減少傳輸量。
* **壓縮 (Compression)**：不同於量化，壓縮是針對一整筆資料（如影像壓縮技巧），減少資料冗餘。

#### 5. 任務放置與排程 (Task Placement and Scheduling)

* **問題核心**：Scheduler 如何決定分散式訓練工作應放在哪一個 Node 上的哪一張 GPU 上運行。
* **溝通影響**：如果 Worker 距離太遠，傳輸延遲會變長，網路擁塞的風險會增加。
* **資源競爭**：分散式計算工作會競爭共用的傳輸頻寬，例如網路頻寬、Node 內部的 PCI bus 等，導致額外的資源競爭和性能干擾。
* **Trade-off**：在強調近距離放置 (減少溝通時間) 與利用率 (使用遠處閒置資源) 之間取得平衡。
* **深度學習特性**：分散式深度學習計算是規律的、迭代的固定行為，其傳輸量、溝通模式是可預測的。排程器可利用這些應用領域的資訊來設計更佳的決策方法。
* **主要排程策略**：
* **集中放置 (Packing)**：強迫集中在同一個 Node 或非常鄰近的 Node 上。這會犧牲資源可用性，可能造成資源浪費和等待時間過長。
* **分散放置 (Spreading)**：故意盡量散落在不同的 GPU/Node 上。資源競爭問題較少，但溝通成本可能較高。
* 目前大多數系統傾向於使用 **集中放置 (Packing)** 策略。

---
其他課程連結

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