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

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

11A~11B Parallel Work Pool and Termination / Parallel Sorting

今日大綱
distributed pool parallel code
distributed termination detection
single-pass ring termination algorithm
dual-pass ring termination algorithm
Divide and conquer
Furher parallelized bucket sort

### Distributed Dijkstra Parallel Code

首先，我們來回顧一下 Dijkstra 演算法的定義。它主要是在一個給定圖中，找到從一個指定起點（source）到任何其他節點（vertex）的**最短路徑**，也就是加總成本最低的路徑。

**核心概念** Dijkstra 演算法最核心的概念是從**單一節點的角度**出發。

- 任何一個節點如果發現了它有更短的路徑，它就會主動地將這個距離資訊（加上其位置）傳播（propagate ) 給它的所有鄰居（neighbor）。
- 鄰居收到這個資訊後，會檢查這是否提供了一個更短的路徑。如果發現了，就會更新自己的最短距離並繼續傳播；如果沒有，就不會再傳播訊息。
- 最終，所有可能的路徑都會被探索到，每個節點上剩餘的值就是到該點的最短距離。

**分散式做法的實作** 分散式做法更貼近上述的描述方式。

- 在分散式計算中，**每個節點（vertex）都會被視為一個獨立的 process**，專門處理自己的事務，也就是管理一個單一節點的運作。
- 每個 process需要維護兩個主要資訊：
1. **自己的最短距離**：每個節點只需記錄到自己為止的最短路徑即可，因此原本的距離陣列會被「拆散」到每個節點上。
2. **拓撲資訊（topology）**：即該節點的所有出站鄰居（outgoing neighbor）及其連結（link）的長度或權重（weight）。在分散式計算中，原本描述拓撲的鄰接矩陣（adjacency matrix）會被拆成「一列一列」，變成一個**一維的列表**，包含該節點所有出站連結的權重。

**運作流程**

1. **初始化**：所有節點的距離預設為無限大。一個初始訊息會從任何地方發送到**源節點（source vertex）**，告知其距離為 0。
2. **源節點動作**：源節點將自己的距離設為 0，然後開始查看其鄰居的位置和連結權重，產生對應的訊息，並將其發送給鄰居。
3. **節點處理**：每個節點收到訊息後，會根據演算法重新計算自己的最短路徑。
- 如果它發現了新的、更短的路徑，就會將這個新的距離（加上自己的位置）發送給其所有出站鄰居，讓他們檢查是否需要更新。
- 這個過程會不斷重複，直到沒有訊息在系統中傳遞。**訊息的傳遞是根據拓撲結構進行的**，一個傳入的訊息就代表該節點需要進行計算。

**集中式與分散式的對比**

- **集中式（Centralized）**：由一個主節點統一管理所有資料（例如需要檢查的節點 queue 和最終結果陣列），並將計算工作分配給從屬節點。從屬節點計算完成後，結果回傳給主節點，由主節點更新最短路徑及產生新的待處理節點。主節點透過判斷 queue是否為空來決定終止。
- **分散式（Distributed）**：每個節點都是獨立的，沒有中央管理員。每個節點都執行相同的邏輯，並透過訊息傳遞進行協調。**所有計算都是從一個節點的角度去設計**，非常適合平行計算。

### Distributed Termination Detection

在完全分散式的計算中，判斷程式何時終止並不是一件簡單的事情。

**終止的兩個條件** 一個分散式計算要真正終止，必須滿足兩個條件：

1. **局部終止（Local Termination）**：每個 process 的 local queue 都是空的，即它自己判斷已無工作可做。
2. **沒有訊息在傳輸中（No Messages in Transit）**：在目前這個時間點，網路上沒有任何訊息正在傳遞。

**問題所在**

- 如果只根據第一個條件（局部終止）來結束，很可能會**過早終止**。因為可能有一個訊息還在網路中傳遞，一旦抵達目標節點，就可能重新啟動（reactivate）該節點，產生新的計算工作。
- 偵測網路中是否有訊息正在傳輸是困難的，因為 process本身無法知道是否有訊息正要傳來，而且網路傳輸時間不確定。等待時間太長會降低效率，等待時間太短又可能導致錯誤偵測。

**解決方法**

1. **Single-Pass Ring Termination Algorithm**

- **概念**：這是一種最基本的想法，只考慮了局部終止條件，因此並不是最正確的做法。它使用一個 token，從一個起始 process（例如 P0）開始傳遞。
- **運作**：當一個 process 判斷自己局部終止後，它會將 token 傳遞給下一個 process。當 token 最終回到起始 process P0 時，表示所有 process 都已進入局部終止狀態。
- **限制**：這種方法無法解決「重新啟動（reactivate）」的問題。如果一個 process 傳遞了 token 後，又收到了一個訊息被重新啟動，那麼 token 已經傳遞，就會導致錯誤判斷。

2. **Dual-Pass Ring Termination Algorithm / Dijkstra-Scholten Style**

- **概念**：這種方法是單次傳遞的延伸，旨在解決訊息可能重新啟動 process 的問題。
- **核心機制**：它透過顏色標記(黑色/白色)來追蹤潛在的重新啟動。
- 當一個 process 傳遞訊息時，如果它向一個「編號較小」的 process 傳送訊息（即使該訊息是往回傳），它就會將自己的狀態設為**黑色**。
- token 一開始是**白色**的。
- 如果 token 經過一個「黑色」的 process，token 本身也會變成**黑色**。
- **終止判斷**：只有當 token 以**白色**狀態回到起始 process P0 時，P0 才能確定目前在整個傳遞過程中沒有任何訊息導致 process 重新啟動。
- 如果 P0 收到**黑色** token ，它就知道這次檢查無效，必須將 token 重設為白色，並重新啟動一輪檢查。**只有 P0 能夠將黑色 token 變回白色**。
- **目標**：透過這種方式，它能夠偵測到因「向前傳遞的訊息」（往編號較小的 process 傳遞）而可能重新啟動已傳遞過 token 的 process，從而避免錯誤終止。
- **缺點**：這種做法是比較激進，只要有任何一次往編號較小 process 傳遞的訊息發生，那一輪的檢查就作廢。這可能導致需要進行多輪傳遞才能真正判斷終止，尤其在最壞情況下，會花費更多時間在等待與重啟上，影響效率。

### Divide and Conquer

分治法（Divide and Conquer）是平行計算中常用的一種方法。它的概念是將一個大問題遞迴地分解成更小的子問題，直到子問題足夠簡單可以解決，然後再將子問題的結果組合起來。

- 在平行計算中，這種分解提供了**平行計算的機會**，因為切分之後，每一層都有平行的機會。
- 它透過減少重複計算量，對於平行計算尤其適合。

**目標** 理想的平行化目標是達到 `O(N log N) / P` 的時間複雜度，其中 N 是資料量，P 是處理器數量。然而，實際問題通常很難完美達到這個目標。
### Further Parallelized Bucket Sort

桶子排序法（Bucket Sort）是一種常用的排序方法，它將資料的數值範圍（range）切割成多個「桶子」（bucket），每個桶子對應一個範圍，並通常分配給一個處理器（process）來處理。

**初始版本（非完全平行化）**

1. **資料分配**：一個主 process 負責將所有資料根據其值分配到正確的桶子中。這個步驟的時間複雜度是 `O(N)`，**不是平行化**的。
2. **局部排序**：每個 process將其負責的桶子內的數字使用 sequential 排序演算法進行排序。此步驟可平行化，每個 process處理的工作量為 `O((N/P) log (N/P))`。
3. **組合**：由於是根據範圍分桶，局部排序完成後，結果已經是整體有序的，因此**不需要額外的組合步驟**。

**缺點**

- 需要事先了解資料的**均勻分佈（uniform distribution）**，才能確保每個桶子的資料量大致相等，達到負載平衡（load balance）。
- 需要知道資料的**值域範圍**，否則若分佈不均，會導致某些 process 無事可做，而另一些 process 負擔過重。
- 改善方法：在分桶之前，可以先進行 **sample** 來估計資料的分佈和值域。

**完全平行化的桶子排序法** 為了解決初始版本中第一步非平行化的問題，可以對其進行修正。

1. **步驟一（資料分塊）**：每個 process 先分取一部分原始資料（例如，按索引分 N/P 個數字），**不需檢查數字值**。這部分是 `O(1)` 或 `O(N/P)` 時間，實現了數據的初步分散，因為它只涉及索引操作，不涉及數值檢查。
2. **步驟二（局部分桶）**：每個 process 將自己分到的那部分資料，根據其值，**在本地**放入對應的桶子（顏色）中。
3. **步驟三（資料重分配/通訊）**： process 之間透過訊息傳遞，將每個桶子的資料（例如，所有紅色資料）發送給負責該桶子的目標 process。這是主要的通訊步驟。
4. **步驟四（最終局部排序）**：每個 process 收到其負責桶子的所有資料後，再使用序列式排序法對其進行局部排序。

**優點** 透過修正第一步，將 `O(N)` 的工作量分散到所有 process 上，使得整體效率大幅提升，達到更接近完全平行的效果。

---
其他課程連結

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