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

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

12C~12D Parallel Sorting and Pipelined Computations

今日大綱
空間資料結構 (例如：KD-Tree)
KD-Tree 的兩種建構方法
Pipeline (管線化)
Pipeline 的三種類型
Synchronous Computation (同步計算)
屏障 (Barrier) 的實作方式

### **1. 空間資料結構 (例如：KD-Tree)**

- **目的**：用於加速空間查詢，例如尋找最近的物體。
- **演算法來源**：假設每個物體都處於最佳位置，並且只需沿一條路徑找到目標，中間遇到的其他點都可以被忽略。最終，總會有一個物體需要被處理到「最底層」，變成單獨的個體。
- **時間複雜度**：
- **搜尋**：由於是平衡的樹，其深度為 `log N`，所以每個物體只需要走 `log N` 的路徑即可。
- **建構/更新**：
- 原先可能是 `N^2` (例如每個物體都要被查詢 N 次)。
- 透過優化，假設每個物體只需要處理一次，並且每個物體都可能需要查詢 `T` 次，則其時間複雜度為 `T * N log N`。
- **需要重新調整**：由於物體的位置會改變，T 樹必須重新調整或重建。雖然只是輕微的位置改變，但 T 樹仍需調整。
- **平衡的重要性**：
- 如果樹是不平衡的，則查詢路徑深度可能很高，導致計算時間增加。
- 物體在空間中均勻分佈時，不平衡的情況很常見。

#### **1.1 KD-Tree 的兩種建構方法**

1. **第一種方法：簡單空間切割 (Spatial Position Based Cutting)**

- **優點**：切割方式非常簡單，不論物體位置如何，都直接切割空間。
- **缺點**：如果物體在空間中不是均勻分佈，這種方法很難確保樹是平衡的。除非物體的分佈本身就很均勻 (例如宇宙中的物體分佈)。
- **近似度 (Approximation)**：相較於第二種方法，這種方法的近似度較好，因為它考慮了空間位置。
- **效率**：計算速度較慢。
2. **第二種方法：基於物體數量分佈切割 (Object Distribution Based Cutting)**

- **目的**：確保建構出來的樹**絕對平衡 (absolutely balanced)**。
- **機制**：
- 切割空間時，不是根據空間的絕對位置，而是根據切割後物體的數量分佈來決定切割位置。
- 例如，在 M 維空間中，它會沿著一個維度進行切割 (如先 X 再 Y)，並選擇一個位置，使切割線兩邊的物體數量相同。
- 透過遞迴方式不斷切割，直到每個節點代表一個單獨的物體。
- **優點**：**確保絕對平衡**，使得查詢時更容易保證平衡性。
- **缺點**：
- **近似度較差**：由於只考慮物體數量，不考慮空間概念，可能導致空間上非常接近的兩個物體被分到不同的分支，無法被視為單一物件或聚合，降低了近似的準確度。
- 切割模式不規則。
- **效率**：計算速度會比較快，特別是平行計算時。

#### **1.2 N-body 問題與平行化考量**

- N-body 問題是如何近似並減少計算量的一個基本應用。
- **平行化方式**：
- 每個人（或處理器）只處理一個 `t` 到 `N` 的路徑。
- 也可以多個處理器同時進行。
- **共享資料結構**：T 樹是一個共享的資料結構。在遞迴切割 (recursive partition) 時，當多個處理器同時讀寫節點範圍時，需要使用 **鎖定 (lock)** 機制來保護共享資源，以避免存取問題。

---

### **2. Pipeline (管線化)**

- **基本概念**：
- 將一個複雜的計算過程拆分成多個階段。
- 每個階段由一個處理器負責計算。
- 整個計算過程是從第一個階段到最後一個階段依序進行，最終得到結果。
- **主要優點**：當計算過程複雜且計算量大時，可以讓不同的處理器同時處理不同階段的工作，實現平行化，從而加速計算並減少計算時間。
- **常見應用**：大量製造業、CPU 指令處理。

#### **2.1 Pipeline 的三種類型**

1. **Type 1: 實例級管線 (Instance-Level Pipelining)**

- **特性**：處理**一個問題的多個實例 (multiple instances)**。
- **例子**：
- 生產大量汽車：每個階段處理不同輛車的生產。
- CPU 處理大量指令：不同階段處理不同指令。
- 計算多個陣列的總和 (summing number in an array)：當有多個陣列 A1, A2, A3... N 時，可以將每個陣列透過管線處理。
- **運作方式**：
- 每個階段 (P0, P1, ..., Pn) 負責一個處理步驟。
- 第一個實例 (Instance 0) 先進入 P0，完成後進入 P1。
- 當 Instance 0 進入 P1 時，Instance 1 可以進入 P0，依此類推。
- 這樣不同階段就可以同時處理不同實例。
- **適用條件**：必須有一個以上的實例 (instance) 才能啟用管線化。如果只有一個實例，則與序列執行 (serial code) 無異，沒有任何好處。
- **缺點**：存在**開銷 (overhead)**。需要一段時間來「填充 (fill)」管線，前 P-1 個週期是空的。同樣，管線清空也需要時間。因此，只有當實例數量遠大於處理器數量時，才能顯著降低執行時間（接近除以 P 而非減半）。
- **MPI 實現**：可透過 send/receive 操作，讓每個處理器接收值、相加、再發送出去，形成管線。
2. **Type 2: 資料級管線 (Data-Level Pipelining)**

- **特性**：處理**一個單一問題實例 (single instance)**，但該實例包含一系列資料項目。
- **運作方式**：問題的計算過程中包含許多操作，這些操作可以應用在不同的資料項目上，從而在資料層面實現加速。
- **適用條件**：資料項目的數量遠大於處理器數量，才能達到加速效果。
- **例子**：
- **插入排序 (Insertion Sort)**：雖然它是一個單一排序問題，但每個數字在插入時都需要與已排序的數字比較並推移。
- **管線化插入排序機制**：
- 假設有 P 個處理器，每個處理器負責比較一個新來的數字。
- 每個處理器收到一個數字後，與自己手上的數字比較：
- 如果新數字較小，將新數字推給下一個處理器，自己保留原來的較大數字。
- 如果手頭沒有數字，則保留新數字。
- 不同數字可以同時在不同的處理器中進行比較和推移，實現平行工作。
- **時間複雜度優化**：插入排序的序列時間複雜度為 `O(N^2)`。透過管線化實作，可將時間複雜度降低到 `O(N)` (N 為資料項目數量，P 為處理器數量，最差情況下，最後一個數字可能需要經過 2N 個步驟才能到位，因此是 `O(2N)` 或 `O(N)`)。
3. **Type 3: 重疊式管線 (Overlapping Pipelining / Interdependent Stages)**

- **特性**：比 Type 2 更特殊，階段之間可以**重疊執行**。即前一個階段還未完全完成時，只要有足夠的資訊或資料，下一個階段就可以開始計算。
- **好處**：讓不同階段的計算時間可以**重疊 (overlap)**，從而實現更快的計算速度。即使每個階段的結束時間可能不同，只要結果不受影響，這種重疊是允許的。
- **例子**：
- **解線性方程組 (Solving Linear Equations)**：特別是像上/下三角矩陣 (upper/lower triangular matrix) 形式的方程組。
- **背向代入法 (Back Substitution)**：
- 對於 `Ax = B` 形式的方程組，如果 `A` 是下三角矩陣，可以從最底層的 `X0` 開始解 (因為該列只包含 `X0`)。
- 解出 `X0` 後，將其代入上一項解 `X1`，依此類推，逐步解出所有 `Xn`。
- **管線化應用**：
- 可以將每個 `Xi` 的計算分配給一個專門的處理器。
- **關鍵點**：當 `X0` 計算完成後，即使其所在的階段還未完全結束，`X0` 的值就可以立即推送到後面的所有處理器。
- 後面的處理器在收到 `X0` 的值後，可以立即開始計算其方程中涉及 `X0` 的部分，而無需等待前一個階段完全完成所有計算。
- 這樣，不同階段的計算就可以重疊，傳遞的資訊 (例如 `X0`) 可以向前傳播，讓後面的處理器提前開始計算，提高效率。
- **程式碼結構**：每個處理器 `Pi` 負責計算 `Xi`，它會累加其前面所有 `Xj` (j < i) 乘以對應係數的結果，然後進行減法和除法以得到 `Xi`。
- **時間複雜度優化**：如果能充分重疊，其時間複雜度可以降到 `O(N)`。
- **一般性考量**：每個階段的計算量應盡量平均，因為最慢的階段會成為瓶頸。

---

### **3. Synchronous Computation (同步計算)**

- **定義**：指某些平行計算過程中，需要所有處理器在**某個特定點進行同步 (synchronization point)** 的行為。
- **非互斥性**：同步計算並非獨立於其他計算類型，一個計算方法可能同時屬於多種類型。
- **原因**：主要由於資料依賴性 (data dependence) 的存在，需要同步點來避免資料不一致問題。
- **實作機制**：透過**屏障 (barrier)** 或**鎖定 (locking)** 機制來實現。
- **例子**：
- 作業中的 Jacobi 迭代法：在每次迭代完成後需要同步所有結果，否則結果會錯誤。
- 許多平行演算法，只要在計算過程中需要處理器同步，都屬於同步計算。
- **注意事項**：
- 要小心鎖定問題，如果屏障或鎖定使用不當，可能會導致處理器互相等待，形成**死結 (deadlock)**。
- 需要仔細判斷同步點的位置，通常是基於資料依賴性需求。

#### **3.1 屏障 (Barrier) 的實作方式**

1. **計數器屏障 (Counter Barrier / Centralized Barrier)**

- **機制**：
- 有一個**主控 (main) 處理器**或共享計數器。
- 每個處理器到達屏障時，向主控發送訊息 (send message) 並等待回覆。
- 主控處理器接收所有處理器的訊息並計數。
- 當所有處理器都到達 (計數達到總處理器數量) 後，主控會發送一個通知訊息 (notify message) 給所有處理器，告知它們可以繼續執行。
- **階段**：分為**抵達階段 (arrival face)** 和**離開階段 (departure face)**。
- **缺點**：
- **中心化 (centralized)**：主控處理器會成為**瓶頸 (bottleneck)**。
- **訊息量大**：由於有抵達和離開兩個階段，需要傳遞的訊息數量相對較多。
2. **蝴蝶屏障 (Butterfly Barrier / Decentralized Barrier)**

- **機制**：
- 採用**分散式 (decentralized)** 的同步方式。
- 通訊模式像蝴蝶一樣，從密集的通訊變得稀疏。
- 每個處理器在到達屏障時，會與其夥伴進行訊息交換。
- 對於每個處理器，它會接收兩個訊息。當它收到這兩個訊息時，就表示所有相關處理器都已到達，它可以從屏障回傳。
- 這種方法類似於遞迴地合併 (merge) 操作，最終讓所有處理器繼續執行。
- **優點**：
- **無主控瓶頸 (no main bottleneck)**：每個處理器處理的訊息數量很平均。
- 每個處理器只需處理兩個訊息。
- 迭代次數為 `log N`。
- 雖然總訊息量可能較多，但由於訊息分散在不同處理器上，且每個處理器只處理少量訊息，不易產生瓶頸問題。

#### **3.2 Deadlock**

- 在同步計算中，如果不小心打亂了執行順序，可能會導致所有處理器互相等待，形成 Deadlock。這是需要特別小心的問題。

---
其他課程連結

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