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

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

12A~12B Parallel Sorting and Pipelined Computations

今日大綱
**Parallel Merge Sort**
**Parallel Quick Sort**
**Bitonic Merge Sort / BicSort**
**Rank Sort**
**Counting Sort**
**N體問題模擬與優化 (Barnes-Hut 演算法)**

### **Parallel Merge Sort**

**基本概念：**

- 與循序 (sequential) 的合併排序寫法幾乎一模一樣。
- 核心思想是**分而治之**：將資料不斷分割，然後再將排序好的小塊資料合併。

**平行化挑戰與瓶頸：**

- 在分割 (divide) 之後，每次進行合併 (merge) 動作時，在**同一個層級 (level) 裡**的合併操作，可以由多個處理器來執行。例如，有四個要合併的陣列，就可以由四個處理器同時進行。
- **問題出在最後一步**：當你需要將兩個非常大的陣列合併在一起時，如果用傳統的循序合併做法，你可能只能用一個處理器來做所有事情。所以，**最後一個步驟其實並沒有被有效地平行化**，它成為了整個計算的主要瓶頸。
- **Communication & Computation**：
- **通訊 (Communication)**：主要發生在資料傳遞，特別是每次傳遞訊息 (message) 的時候。通訊的數量和大小會隨層級變化。
- **計算 (Computation)**：在分割階段，其實沒有真正的計算（因為不看數字內容）。真正的計算發生在合併階段，需要比較和對換數字。但平行化時，我們只統計負載最重的那個處理器的計算量。

**總結：**

- 雖然初期階段可以很好地平行化，#但最後的合併步驟是個大問題，會卡住整個演算法。

## **Parallel Quick Sort**

**基本概念：**

- 與循序快速排序非常相似。
- 運作方式：選擇一個**基準點 (pivot)**，然後將比基準點大的數字放一邊，小的放另一邊，然後遞迴 (recursive) 執行這個動作。
- **最終結果：** 每個處理器手上拿到的數字，與其處理器 ID (processid) 順序會吻合。數字不是集中在某個處理器，而是分佈在各個處理器上，但它們的整體順序是正確的。

**平行化挑戰：**
- **不平衡 (Unbalance)**：快速排序在循序執行時通常是最快的，但在平行環境下卻**很不理想**。原因就是它**不一定平衡**。
- 如果資料分佈不平衡，最壞情況下的計算時間甚至可能比其他排序算法還要差。只有在非常平衡的情況下才能達到較好的效能。
- 因此，將快速排序寫成平行版本，**反而是比較困難的一種做法**。

---
### **Bitonic Merge Sort / BicSort**

**改良動機：**

- 旨在解決傳統合併排序的瓶頸，也就是**合併動作的平行化問題**。傳統合併排序的處理器使用數量與層級有關，最後一層只剩一個處理器能用於合併。

**核心概念：位元序列 (Bitonic Sequence)**

- **定義**：一個序列中的數字，只會先往上再往下，或先往下再往上，像一個山峰或山谷一樣。例如：3, 5, 8, 9 然後 7, 4, 2, 1。
- **重要特性**：一個位元序列可以被**分成兩半**，經過比較和交換後，較小的數字會全部集中在一半，較大的數字集中在另一半。
- **更神奇的是**：分割後的這兩半，**仍然是位元序列**。這個特性讓它能持續進行平行處理。

**如何實現平行合併：**

- 利用位元序列的特性，我們可以**同時**進行比較 (compare) 和交換 (swap) 的動作。
- 透過不斷遞迴地應用這個比較和交換的過程，我們可以將一個位元序列在 **O(log N)** 的時間內排序好，前提是有足夠的處理器。
- 在合併排序的過程中，每當要合併兩個已排序的子序列時，它們合併後的序列會是一個位元序列。因此，我們可以利用上述方法，在 O(log N) 的時間內完成這一層的合併。

**複雜度：**

- 如果使用一個處理器，循序合併的時間複雜度是 O(N)。
- 但在位元合併排序中，每次合併的動作，從 O(N) 降到了 **O(log N)**，因為它能充分利用多個處理器。
- 整個位元排序演算法的總時間複雜度，從傳統合併排序的 O(N log N) 降到了 **O(log N)^2 (log 平方 N)**。
- **優勢**：在每一步中，你都可以充分利用一半的處理器 (如果總共有 N 個數字，二分之 N 個處理器)。這讓它比傳統的平行合併排序效率高非常多。

---
### **Rank Sort**

**概念：**
- 非常簡單直接：對於每一個數字，**計算有多少個其他數字比它小**，這個數量就是它的最終排名 。
- 然後，直接將這個數字搬到它排名所對應的位置。

**循序與平行差異：**
- **循序版本**：這是一個很「笨」的方法，循序計算的時間複雜度是 **O(N^2)**。
- **平行版本**：雖然笨，但它**非常容易平行化**。
- 每個數字的排名都可以獨立計算，所以如果你有 N 個處理器，每個處理器負責計算一個數字的排名，那麼時間複雜度可以達到 **O(N)**。
- **進階平行化**：如果你不計成本，可以使用更多的處理器來加速。例如，用 N^2 個處理器，讓每個數字的排名計算過程本身也平行化。
- 每個處理器會比較自己的數字和所有其他數字，標記比自己大的或小的。
- 然後，透過樹狀結構進行**求和 (summation)**，在 **O(log N)** 的時間內就能知道每個數字的排名。
- **效能與效率的權衡 (Trade-off)**：
- 雖然可以達到 O(log N) 的極快時間複雜度，但因為使用了 N^2 個處理器，總的工作量 (efficiency) 實際上是 N^2 * log N，比之前的演算法可能更差。
- **適用場景**：如果你追求極致的速度，不介意消耗更多的處理器資源，那麼排名排序是一種非常好的平行化方法。

---

### **5. Counting Sort**

**概念：**

- **建構直方圖 (Histogram)**：首先，建立一個計數陣列 (count array)，記錄每個數值（在一個預設範圍內，例如從 1 到 C）出現的次數。這就像是一個分佈圖。
- **累積求和 (Cumulative Sum)**：然後，對這個計數陣列進行累積求和 (prefix sum)。這會告訴你，如果一個數值是 X，那麼在新陣列中，所有小於或等於 X 的數字應該放在哪個位置之前。
- **放置元素 (Placement)**：最後，根據累積求和的結果，將原始陣列中的數字搬到新陣列的正確位置。

**循序與平行差異：**

- **循序版本**：循序建構直方圖和累積求和都至少是 O(N) 或 O(Range)，找到每個數字的位置則可能達到 O(N^2)。所以循序版本不是很好。
- **平行版本**：這個演算法非常容易平行化，每個步驟大部分都可以完美平行執行。
- **建構直方圖**：每個處理器可以自己計算它手上資料的計數。
- **累積求和**：可以透過平行化的前綴和演算法在 **O(log N)** 的時間內完成。
- **放置元素**：每個處理器負責將一個元素搬到其最終位置，也是 O(1) 的時間。
- **總體複雜度**：在理想情況下，可以達到 **O(log N)** 的時間複雜度，且僅使用 N 個處理器。

**限制：**

- 計數排序的性能與你數據的**數值範圍 (range)** 息息相關，而不是絕對與數字數量 (N) 有關。
- **問題**：如果你的數值範圍非常大（例如 1 到 10000），但實際有值的數字只有 10 個，那麼你的計數陣列長度仍然是 10000。這會導致計算效率下降，無法達到理想的 O(log N) 表現。
- **適用場景**：它在理想情況下（即數值範圍不大，或數字分佈均勻覆蓋範圍）表現極佳。

---
### **N體問題模擬與優化 (Barnes-Hut 演算法)**

#### **N體問題基本概念**

- **目的**：這是一個很常見也很重要的應用問題，就是要**模擬多個物體（比如說像星星、粒子）在重力作用下的運動**。
- **牛頓萬有引力**: 我們用的呢，就是非常簡單的基本定律，也就是高中學過會忘記的沒關係。基本上，我們知道**兩個物體之間的力 會等於它們的引力常數乘上它們的質量乘積，再除以它們距離的平方**。所以，A、B兩個物體之間的力，就是$F = G * (mA * mB) / r^2$。

- **計算流程**:

1. 有了這個力，我們就可以根據它來計算出物體的**加速度 (Acceleration)**。
2. 有了加速度，我們就可以更新物體的**速度 (Velocity)**。
3. 有了新的速度，我們就能更新物體的**位置 (Position)**。

- 這是一個**模擬過程**，所以我們會在每個時間點 (T) 來更新所有物體的速度和位置。
- **維度處理**: 這個計算其實可以在不同維度（2D、3D）獨立進行。你只要稍微調整一下距離的計算方式，把它變成像我們說的X、Y軸中心位置，每個軸的距離平方和開根號。然後X跟Y的計算一樣是單獨進行，根據它們個別的X、Y位置來計算，你就能得到不同維度的力。有了這些力，當然就能更新X、Y、Z坐標和速度。
- **循序計算的挑戰**:
- 如果你用最簡單的循序程式碼去寫，根據剛剛的定律計算，你就會發現，對於每個時間點，我們要去計算每個物體所受的力。這個計算力的地方，**每一個物體都要跟所有其他的物體都去計算一次交互作用的力**。
- 所以，光是計算力這個部分，就已經是 **O(N^2) 的時間複雜度**了。
- 當物體數量非常龐大時，比如說上萬、上億顆星星，那循序計算就會**非常耗時**，需要用平行程式去加速它。

#### **優化方法：近似計算 (Approximation)**

- **核心思想**: N體問題加速的第一個方式就是用**近似計算 (Approximation)**。因為點太多了，所以我們想辦法把這個N的數量縮小，讓計算變快。
- 概念就是，當我們在計算一個物體所受到的力時，如果**對它產生影響的這群物體，它離目標物體非常遠，而且這群物體彼此之間的距離又非常小**。
- 在這種情況下，我們就可以把這**一群遙遠的物體視為一個單一的物體 (一個 Cluster)** 來計算它對目標物體的引力。
- 這樣做的原因很簡單，因為它們彼此都非常近，所以它們的**質心 (Center of Mass)** 就相當於它們的作用點，作用效果其實會非常接近。

- **如何減少計算量**: 透過這樣的方式，你就可以**減少計算的量**。原本可能九個點要計算九次，現在把它們看成一個質心後，對這個質心只計算一次，計算量就大幅減少了。

#### **2.3 空間劃分與樹狀結構 (Quadtree/Octree)**

- **目的**：那剛剛這種想法，怎麼樣套用到我們的計算裡面呢？主要就是透過**遞迴 (recursive) 的方式**。我們要判斷哪些物體可以被當做一個 Cluster。所以我們需要對空間做**分割 (partition)**。
- **方法：均勻劃分 (Uniform Partition)**:
- 一種比較單純的切割方法是**不管這些星星的位置在哪裡，我就是對空間進行對切 (Space Partition)**。
- 根據維度，在2D是X、Y軸都對切，就形成**四個子區域 (Quadtree)**。在3D也是一樣，就形成**八個子區域 (Octree)**。
- 我們在切割的同時，也會建立一個**資料結構 (data structure)**，通常是樹狀結構。
- **樹的建立與節點資訊**:
- 樹的**每個節點 (node) 都代表一個空間區域**。
- 如果一個區域裡面有多個物體，我們就**繼續向下遞迴切割**。
- **每個節點都會儲存其所包含物體的總質量 (total mass) 和質心位置 (center of mass)**。這些資訊代表如果將該節點所代表的區域視為一個 Cluster 時，它的總質量和質心在哪裡。
- 樹的**葉節點 (leaf node)** 通常就是代表單一個實體星星，或是已經不再需要劃分的最小區域。
- **建樹過程**: 整個建樹的過程 (Pre-computation) 就是在做空間的分割，並建立起所有未來可能可以近似的 Cluster。

#### **2.4 力計算與近似條件**

- **計算流程**: 切割完樹之後，就開始計算了。
- 這棵樹代表所有點的狀況，但我們要計算的是**每個物體所受的合力**。
- 當我們計算一個特定物體 (例如 A) 所受的力時，我們會從樹的**根節點 (root node) 開始往下遍歷 (traverse)**。
- **近似判斷 (Approximation Condition)**:
- 對於樹中的每個節點（代表一個 Cluster），我們都要判斷是否可以將它視為單一物體。
- **判斷標準 (θ)**: 我們會計算一個比率 **`θ_ratio = (Cluster 的邊寬 R) / (物體 A 到 Cluster 質心的距離 D)`**。
- `R` 就是這個 Cluster 所在 Box 的邊寬。
- `D` 是物體 A 到這個 Cluster 質心的距離。
- **原則**: 這個 `θ_ratio` 的值要**越小越好**。越小代表物體A離這個 Cluster 非常非常遠，而且這個Cluster內部物體的範圍半徑非常非常小，這樣才符合近似的條件。
- **閾值判斷**: 我們會設定一個預設的閾值 `θ` (例如 0.5)。
- **如果 `θ_ratio < θ`**，就表示物體 A 離這個 Cluster 夠遠，可以將整個 Cluster 視為一個單一的質點，直接計算它對物體A的引力。
- **否則 (`θ_ratio >= θ`)**，就表示不能近似，需要繼續往這個節點的**子節點 (下一層)** 遞迴遍歷。
- **遍歷過程**: 這樣遞迴地遍歷樹，對於每個物體，最終會得到一個由個別物體和可以近似的 Cluster 所組成的列表，用於計算合力。這個過程是針對**每一個要計算力的物體**獨立進行的。
- **結果**: 透過這種方式，原本需要與所有N個物體計算的力，就可以減少到只與少數個別物體和近似的Cluster進行計算，顯著降低計算量。

#### **2.5 θ 值的影響與平衡問題**

- **θ 值的選擇**:
- **`θ` 越小 (例如趨近於 0)**：近似的條件就越嚴格，越不容易近似。計算結果越精確，但計算量越大，甚至會趨近於 O(N^2)。
- **`θ` 越大**：越容易達到近似的條件，計算量越小，速度越快。但準確度會降低。
- 通常 `θ` 的值會**小於 1**。因為如果等於1，就表示你的點到對方的距離跟你的Box的邊長一樣長，這太近了，近似會非常不準確。
- **不平衡分佈的挑戰**:
- 如果物體在空間中的分佈**不均勻**，透過均勻劃分建立的樹會變得不平衡。
- 不平衡的樹會影響平行化效率，因為在遍歷樹時，有些路徑可能非常深，導致處理器負載不均。
- **樹的重建**: 由於物體的位置在每個時間步 (Time Step) 都會更新，**整個樹結構需要為每個時間步重新建立**。因為每個時間點大家的位置不一樣，所以你要重新建樹，然後再對每個點去計算它所受的力。

---
其他課程連結

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