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

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

4A~4B IO Parallel IO and Program Analysis

今日大綱
超級電腦系統的 IO 與儲存優化
為什麼 IO 變得如此重要?
IO 解決方案：儲存層次結構的優化
新型非揮發性記憶體
平行 IO 概念
為什麼需要 Burst Buffering?
平行程式的效能評估指標: Speedup、System Efficiency
平行程式的兩種擴展方式：Strong Scaling 與 Weak Scaling
平行演算法的複雜度分析

### **超級電腦系統的 IO 與儲存優化**

首先，我們來談談 IO 和儲存。大家應該都還記得，資料存取在現今的計算中變得越來越重要，因為大部分的計算都是資料驅動的，特別是深度學習等熱門領域更是如此。

#### **為什麼 IO 變得如此重要？**

這是因為多年來計算效能，尤其是像 GPU 這樣的技術出現後，提升得非常快。然而，**IO 的效能進步卻相對有限，幾乎呈現平坦的趨勢**。這導致了**計算與 IO 之間的效能差距越來越大**，如果沒有好的 IO 解決方案，我們根本無法實現 **Exascale Computing** 這樣的大規模計算。所以，一個高效能的計算系統，不僅需要快的計算節點，更需要**網路和 IO 的全面配合**才能發揮其應有的效能。

#### **IO 解決方案：儲存層次結構的優化**

在我們的電腦系統中，資料讀取一直都有一個做法，就是利用 **IO Hierarchy**。這個階層從底層到上層，空間越大速度越慢，反之亦然。最上層的記憶體（像是暫存器、快取、主記憶體）雖然速度快但昂貴且空間有限，甚至可能是揮發性（volatile）的，斷電後資料會消失。底層的硬碟或磁帶系統則相反，容量大但速度慢。

機會在哪裡呢？就是這個階層中不斷出現的**新儲存技術**。

1. **新型非揮發性記憶體（Non-Volatile Memory, NVM）**：

- 最明顯的例子就是 **Flash 或固態硬碟（SSD）**。這類儲存裝置具備 **隨機存取（random access）** 能力，但卻是**非揮發性**的，即使斷電資料也不會消失。
- 它們的出現為 IO 帶來了極大的彈性，因為可以根據其特性在儲存階層中扮演新的角色，從而加速 IO 處理。
- NVMe ( Non-Volatile Memory Express )是其中一種新型技術，在超級電腦系統的 IO 優化中扮演關鍵角色。
2. **平行 IO (Parallel IO)**：
- 顧名思義，就是**同時對資料或檔案進行讀寫操作**。
- 如果計算可以平行化，但 IO 層卻無法平行，那麼計算最終還是會卡在 IO 上。
- 這就需要探索 **平行 IO 的解決方案**，特別是在檔案系統這一層。
- **平行檔案系統 (Parallel File Systems)**：
- 檔案系統本身必須是**分散式系統**，才能提供平行 IO 能力。
- 著名的例子是 **Lustre**。它是一個開源的平行檔案系統，有著不錯的 scalability ，可以支援大量的儲存節點，不斷擴展儲存空間並透過增加儲存節點來提升 IO 速度和傳輸頻寬。
- **Lustre 的基本概念**：
- 它包含多個**儲存資料的電腦（儲存節點 )**，這些節點只負責處理檔案。
- 這些儲存節點可以**獨立連接到計算節點**，建立獨立的實體連結，從而增加傳輸量。
- Lustre 有兩個核心元素：
- **儲存資料的目標 (Object Storage Targets, OSTs)**：實際儲存資料的地方。
- **中繼資料伺服器 (Metadata Server, MDS)**：儲存檔案的中繼資料 (metadata) 和資料映射 (data mapping) 的地方，就像目錄一樣，用於查找檔案位置。
- 每個儲存節點內的硬碟甚至可以透過 **RAID 技術**進一步加速單一節點的 IO 效能。
- **MPI-IO 函式庫**：
- 為了讓 **MPI 平行程式**能夠與平行檔案系統溝通，讓每個 process 都能與儲存節點互動，需要額外的函式庫支援，例如 MPI-IO。
- 如果底層的檔案系統不是平行檔案系統，即使使用 MPI-IO，也可能因為卡在單一檔案系統層而無法顯著加速 IO 效能。這再次強調了**系統每一層都需要平行化**的重要性。
3. **Burst Buffering**：
- 這是一種在檔案系統和計算系統之間增加 **buffering** 的機制，以加速資料傳輸速度。
- **Buffering** 的一般概念：在 IO 過程中，由於速度差異，我們將資料暫存在記憶體空間中，然後再慢慢寫出去。
- **為什麼需要 Burst Buffering**
- 傳統 IO 的量通常**不穩定（bursty）**，例如程式執行完畢後瞬間輸出大量資料，然後又停止寫入。這種不穩定的 IO 模式導致難以預測所需的頻寬，如果按照峰值（peak load）來保留頻寬，成本又太高，因此系統通常會保留遠低於峰值的頻寬，導致在高峰負載時 IO 卡住。
- **Burst Buffering 如何解決問題？**
- 它在 **IO 節點** 上增加了 buffer，資料會先暫時寫入 IO 節點的記憶體中。
- **優勢一**：對於計算節點來說，資料只需寫入 IO 節點的記憶體即可回傳，速度遠快於直接寫入後端儲存系統，顯著提升了計算節點的IO速度。
- **優勢二**：IO 節點可以將不穩定的突發流量轉換為更平穩的資料流，再寫入後端儲存節點。這樣可以更有效率地利用頻寬，簡化系統管理（如排程和資源預留）。
- **NVMe 在 Burst Buffering 中的關鍵作用**：
- 傳統記憶體作為 Buffer 有兩個限制：**空間有限且是揮發性**的。
- 由於 **非揮發性記憶體（NVMe）** 的出現，它提供更大的容量，且資料在斷電後不會消失。這使得 NVMe 非常適合在 **Burst Buffering** 中扮演 Buffer 的角色，確保資料的持久性，也因此，Burst Buffering 這種想法才真正在 201X 年的超級電腦系統中被實作和廣泛應用。
- **NVMe 的另一個常見應用**：
- 將 NVMe 用作檔案系統中**中繼資料（metadata )**的儲存空間。由於每次開檔、讀檔、寫檔都需要讀取中繼資料，且中繼資料的量通常遠小於實際資料，NVMe 的高速存取能力可以大幅提升檔案系統的中繼資料處理速度。

---

### **平行程式的效能評估指標**

在評估平行程式的效能時，我們有一些必須知道的指標。

#### **加速比 (Speedup, S)**
- 這是衡量平行程式最主要的目標：**加快計算速度**。
- **定義**：加速比 S = (最快循序執行時間 Ts) / (平行執行時間 Tp)。
- Ts：指的是**最佳的循序程式碼**所得到的執行時間。
- **理想情況 (Linear Speedup)**：
- 如果你的程式擁有 **線性加速（Linear Speedup）** 的特性，表示當你有 P 個計算核心時，你的加速比就應該是 P。例如，用兩台電腦就應該比一台電腦快兩倍。
- 在圖表上，它會呈現一條**直線（slope = 1）**。
- **常見情況**：
- 實際情況下，加速比曲線通常會**先上升，然後逐漸趨緩，甚至可能往下掉**。這代表隨著計算資源的增加，加速效果會越來越少。
- 主要原因是**通訊（communication）和同步化（synchronization）的開銷**。當節點越多時，通訊流量可能會呈平方級增長，最終吞噬掉計算帶來的效益。
- **超線性加速 (Superlinear Speedup)**：
- 在少數情況下，你可能會觀察到加速比**大於線性加速**（S > P）。這在理論上是不可能發生的，因為它違反了一些基本定理。
- 然而，在現實世界中確實可能發生，原因在於**複雜的電腦系統存在許多優化機制**。
- **最常見的例子就是快取或記憶體**：
- 當你增加更多的電腦或計算資源時，它們累積的快取或記憶體容量會變大。
- 如果你的整個輸入資料集能夠因此完全塞進記憶體甚至快取中，那麼程式的執行速度將會大幅提升，因為避免了訪問較慢的儲存層（如硬碟）。記憶體比硬碟快上百倍，快取又比記憶體快數倍。

#### **系統效率 (System Efficiency)**

- 系統效率是將加速比標準化的指標，讓不同規模的系統能夠公平比較。
- **定義**：系統效率 = 加速比 S / 處理器數量 P。
- **解讀**：
- 如果實現線性加速，系統效率將是 **100% (或 1)**。
- 一般情況下，效率會低於 100% (例如 80% 或 90%)。
- 如果超過 100%，則表示發生了超線性加速。
- **優勢**：它提供了一個共同的衡量標準，可以更客觀地比較不同平行程式的效能。

#### **非理想加速比的原因 (Amdahl's Law)**

為什麼平行程式難以達到理想的線性加速呢？主要有三個原因：

1. **程式部分無法平行化 (Non-Parallelizable Portion)**：並不是所有程式碼都能被平行化，例如初始化操作。
2. **額外計算開銷 (Additional Computation Overhead)**：為了實現平行化，有時會引入額外的計算，例如同步化（synchronization）機制（如鎖定, locking）和額外的溝通傳輸動作。
3. **通訊開銷 (Communication Overhead)**：平行化通常假設計算量可以被平均分攤，但卻忽略了資料傳輸所需的時間。通訊時間會隨著處理器數量的增加而顯著增加，成為瓶頸。

**Amdahl's Law** 透過數學公式清晰地展示了程式中**不可平行化部分 (F)** 對加速比的影響。即使只有一小部分程式無法平行化（例如 20-30%），當處理器數量增加到一定程度時，加速比就會趨於平坦，難以再提升。

---

### **平行程式的兩種擴展方式：Strong Scaling 與 Weak Scaling**

在分析平行程式的效能時，我們通常會用到兩種不同的擴展（scaling）方式來繪製加速比圖：

#### **Strong Scaling**

- **定義**：在 **Strong Scaling** 測試中，**問題的規模（problem size）是固定不變的**。
- **目標**：透過不斷增加計算資源（處理器數量）來解決同一個問題，目的是**找出解決該問題的最佳機器數量**。
- **特性**：
- 通常**很難達到線性加速**。
- 原因：問題規模不變，但計算節點越多，每個節點分到的計算量就越少，而通 **Strong Scaling**時間卻會不斷增加，導致通訊開銷佔比越來越高。
- **圖表**：執行時間曲線通常會隨著處理器數量的增加而下降，但會逐漸趨緩。
- **應用**：當你想要知道用多少台機器來解決一個**特定大小的問題**時，強擴展是很好的評估方式。

#### **Weak Scaling**

- **定義**：在 Weak Scaling 測試中，當你增加計算資源（處理器數量）時，**問題的規模也會成比例地增加**。
- 例如，如果用兩台電腦，處理的資料量就是一台電腦的兩倍。
- **目標**：評估當計算資源和問題規模同步成長時，程式的效能表現。
- **特性**：
- 相對於 Strong Scaling，**更容易達到理想的擴展結果**（例如，執行時間維持不變或加速比維持常數）。
- 原因：因為計算量隨著處理器數量增加而增加，所以**計算與通訊的比例能夠維持大致不變**。通訊開銷雖然增加，但由於計算量的增加，它不會像強擴展那樣容易成為瓶頸。
- **圖表**：理想情況下，執行時間曲線會呈現一條水平線（常數時間），或加速比曲線呈現一條常數線。
- **應用**：
- 在 **Strong Scaling** 難以達到理想結果時， **Weak Scaling** 可能更容易展示良好的擴展性。
- 當處理的問題規模非常龐大，單一或少數節點無法處理，或者需要耗費極長時間才能運行時，**Weak Scaling** 能讓你**透過同步縮小問題規模來在有限的資源下進行測試**。

**總結這兩種擴展**：強擴展更著重於在固定問題下，如何優化資源利用以獲得最大加速；
**Weak Scaling** 則著重於在資源與問題同步增長時，程式能否保持良好的效能效率。

---

### **平行演算法的複雜度分析**

就像循序演算法一樣，平行演算法也需要進行**複雜度分析**，在實作前評估其好壞。

#### **與循序演算法複雜度的差異**
平行演算法的複雜度分析與循序演算法有兩個主要不同點：
1. **必須考慮通訊 (Communication)**：除了計算（computation）之外，**資料傳輸（communication）的部分也必須被考量進去**，因為它會佔用大量的時間。
2. **時間維度 (Time Dimension)**：計算可以同時在多個處理器上發生，因此我們不應該將所有處理器的計算時間累積起來。我們只需要**分析單一計算機或處理器執行所需的數量**即可，從時間維度來看它們是同時發生的。

#### 時間複雜度分析

$$ T_p = T_{comp} + T_{comm} $$

( $T_p$ ): 平行演算法的總執行時間
( $T_{comp}$ ): 計算部分
( $T_{comm}$ ): 通訊部分

$$ T_{comm} = q (T_{startup} + n T_{data}) $$

( $T_{startup}$ ): 訊息延遲（假設為常數）
( $T_{data}$ ): 傳送單一資料項的時間
( $n$ ): 訊息中的資料項數量
( $q$ ): 訊息數量

#### 時間複雜度範例 1

演算法階段：

1.電腦 1 將 ( n/2 ) 個數字傳送給電腦 2
2.兩台電腦同時對 ( n/2 ) 個數字進行加法
3.電腦 2 將其部分結果傳回電腦 1
4.電腦 1 將部分總和相加以產生最終結果

複雜度分析：

計算（針對步驟 2 與 4）：$$ T_{comp} = n/2 + 1 = O(n) $$
通訊（針對步驟 1 與 3）：$$ T_{comm} = (T_{startup} + n/2 \times T_{data}) + (T_{startup} + T_{data}) $$$$ = 2T_{startup} + (n/2 + 1) T_{data} = O(n) $$
整體複雜度： $O(n)$

#### 時間複雜度範例 2

使用 ( m ) 個處理器相加 ( n ) 個數字

均勻分配數字到處理器

循序： $O(n)$

平行：

階段 1：將數字傳送給從屬處理器$$ t_{comm1} = m (T_{startup} + (n/m) T_{data}) $$
階段 2：計算部分總和$$ t_{comp1} = n/m - 1 $$
階段 3：將結果傳送給主處理器$$ t_{comm2} = m (T_{startup} + t_{data}) $$
階段 4：計算最終累加$$ t_{comp2} = m - 1 $$
整體： $$ t_p = 2m T_{startup} + (n + m) t_{data} + m + \frac{n}{m} - 2 $$

通訊複雜度公式

通訊複雜度的簡化模型通常表示為：$$ Q \times Start + N \times T $$
( Q ): 訊息數量（演算法執行過程中傳送和接收訊息的次數）
( Start ): 每個訊息的啟動延遲（通常為常數）
( N ): 傳輸的資料元素數量（例如整數或位元組）
( T ): 每個資料單位所需的傳輸時間，取決於網路頻寬

#### **Cost-Optimal 平行演算法**

- 平行演算法的成本定義為：$O(t_{p})*N=O(t_{s})$

- **定義**：一個平行演算法是**成本最佳化**的，如果它的成本與**最佳循序演算法的複雜度漸近相等**。
- **重要性**：我們需要比較平行演算法的「總工作量」與循序演算法的工作量。如果平行演算法雖然速度快，但總工作量（成本）遠高於循序演算法，那麼它可能不是一個高效的設計。
- **例子 (排序演算法)**：
- 最佳循序排序演算法：$O(N log N)$。
- 若設計一個使用 N 個處理器，達到 O(log N) 時間複雜度的平行排序演算法。
- 計算其成本：$O(log N) * N = O(N log N)$。
- 由於其成本與最佳循序演算法的複雜度相同，這個平行排序演算法就是**成本最佳化**的。
- 但如果另一個平行演算法使用 $N^2$ 個處理器，達到 $O(1)$ 的時間複雜度。雖然看起來速度很快 $O(1)$，但其成本是 $O(1) * N^2 = O(N^2)$。由於 $O(N^2)$ 大於 $O(N log N)$，這個演算法就**不是成本最佳化**的，雖然它可能在某些情境下被採用（因為我們有時願意用更多資源來換取更快的速度）。

---
其他課程連結

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