平行程式 10C~10D Synchronization Tools & Open Multi-Processing(OpenMP)Synchronization Construct

教材:10710周志遠教授平行程式 https://www.youtube.com/playlist?list=PLS0SUwlYe8cxqw70UHOE5n4Lm-mXFXbZT 20250830 筆記內容可能有錯僅供參考 10C~10D Synchronization Tools & Open Multi-Processing(OpenMP)Synchronization Construct 今日大綱 Load balancing and termination Static Load balancing Dynamic Load balancing Centralized Work Pool Decentralized Work Pool Fully Distributed Work Pool ### **Load balancing and termination** **負載平衡的重要性**： - 對於平行程式而言，**整個程式的執行時間是由最慢的任務結束時間所決定**，而非平均時間。 - 如果負載不平衡，某些處理器會被分配到大量或計算複雜的任務，而其他處理器則閒置，這會顯著**加長整體執行時間**。 - 因此，**優化平行程式最基本的第一點就是希望負載是平衡的**，以實現最短的執行時間。 **中止偵測的重要性**： - 在平行程式中，**所有的工作者都需要知道何時可以結束其程式**。 - 如果採用分散式寫法且沒有單一的「primary」存在，中止偵測會變得非常複雜。 - MPI 等程式模型中，每個處理 process 必須能知道何時終止，否則整個任務將無法正確結束。必須有辦法偵測所有計算何時完成。 ### **靜態負載平衡 (Static Load-Balancing)** - **定義**：靜態負載平衡是指在**程式執行前**，就根據預先確定的分配規則 (predetermined assignment) 來決定任務 (task) 與處理 process 之間的映射關係。 - **決策與執行時間無關**：無論採用哪種預先確定的演算法或策略，其決策都與實際的執行時間無關。 - **例子**： - **輪流分配 (Round-robin)**：任務依序分派給各處理 process 。 - **隨機分配 (Randomized)**：任務依據隨機結果分派，但在執行前已決定好，與執行狀態無關。 - **加權分配 (Weighted)**：基於事先的估計，將不同權重的任務分派給處理 process ，但估計的準確性是個問題。 - **缺點**： - **不考慮真實執行時間**：靜態方法無法考慮到每個任務實際的計算時間。 - **估計困難**：預估每個任務的執行時間非常困難且不準確，特別是通信延遲等因素難以預估。 - **Mandelbrot 集合的計算量不可預知**：Mandelbrot 集合中每個像素的計算量在執行前根本無法得知，因為它取決於該點多快發散。黑色的區域（屬於 Mandelbrot 集合的點）需要進行最大次數的迭代才能判斷，計算量遠大於淺色區域。如果單純按像素數量分配任務，會導致負載嚴重不平衡。 - 因此，除非計算非常規律，否則靜態負載平衡難以有效解決負載平衡問題。 ### **動態負載平衡 (Dynamic Load-Balancing)** - **定義**：動態負載平衡是指**在程式運行時 (run time)**，根據任務的實際執行時間來決定排程決策。 - **機制**：其核心概念是「**先完成者先搶** (first-finished, first-served)」——任何一個處理 process 只要完成當前任務，就立即領取下一個可用任務。 - **優點**： - **適用於計算量不一的任務**：特別適合那些任務計算量長短不一的情況。 - **實現良好平衡**：如果任務或資料區塊 (data partition chunks) 夠小，動態排程最終會使得所有處理器的負載趨於平衡。 - **實作方式**：可分為三種類型：**集中式 (centralized)**、**去中心化 (decentralized)** 和**完全分散式 (fully distributed)**。 ### **Centralized Work Pool** 在集中式工作池模型中，有一個**主導者**負責分派任務和收集結果。根據您的要求，我們將其稱為「Primary」**，而其他執行計算的處理 process 稱為**「Secondary Process」。 **核心概念**：一個「Primary」負責管理所有待計算的任務，並在執行時才決定將任務分派給哪一個「Secondary Process」，從而實現動態排程。這種方法尤其適合像 MPI 這種處理 process 數量固定的程式模型。 **Primary 的程式碼邏輯** ： ``` // Primary Process 程式碼 count = 0; // 目前手上有任務的 Secondary Processes 數量 row = 0; // 已經發送的任務編號 // 步驟一：向每個 Secondary Process 發送初始任務 (row) for (k=0; k<num_proc; k++) { // 遍歷所有 Secondary Processes send(row, P_i, data_tag); // 向 P_i (這裡應該是 P_k) 發送一個 row 任務 count++; // 活躍的 Secondary Processes 數量加一 row++; // 準備發送下一 row } // 步驟二：主迴圈，接收結果並發送新任務或終止訊號 do { // 接收來自任意 Secondary Process 的結果 recv(&slave, &r, color, P_ANY, result_tag); // 接收來自任何 Secondary Process (P_ANY) 的結果 count--; // 一個 Secondary Process 完成任務，活躍數量減一 // 判斷是否還有新任務可發送 if (row < num_row) { // 如果還有未發送的 row 任務 send(row, P_slave, data_tag); // 向剛完成任務的 Secondary Process (P_slave) 發送下一 row 任務 count++; // 活躍數量加一 row++; // 準備發送再下一 row } else { // 如果所有 row 任務都已發送完畢 send(row, P_slave, terminate_tag); // 向 Secondary Process (P_slave) 發送終訊號 } display(r, color); // 顯示已完成的 row 結果 } while(count > 0); // 迴圈條件：當前仍有活躍的 Secondary Processes ``` - **`count` 變數**：代表目前手頭上還有工作、尚未傳回結果的 **Secondary Processes 數量**。這個變數對於**正確的中止偵測**至關重要，Primary 會持續接收訊息直到 `count` 歸零，確保所有 Secondary Process 的結果都被接收，並且所有訊息交換都已完成。 - **`row` 變數**：代表 Primary 已經分派出去的 row 數編號。 - **初始分派**：Primary 會先向每個可用的 Secondary Process 發送一個初始任務（一 row 圖像計算），以啟動它們。 - **主迴圈 (Work-Stealing / Dynamic Assignment)**：Primary 在一個 `do-while` 迴圈中運作。它會不斷地接收來自任何 Secondary Process 的計算結果 (`recv(&slave, ..., P_ANY, result_tag)`) 。 - 每當收到一個結果，`count` 就會減一。 - Primary 會檢查是否還有未分配的 row (`row < num_row`)。如果還有，它會將下一 row 任務 (`data_tag`) 分配給剛完成任務的 Secondary Process，並將 `count` 加一、`row` 加一。 - 如果所有 row 都已分配完畢，Primary 則會向該 Secondary Process 發送一個**終止訊號 (`terminate_tag`)**，告知它沒有更多工作了。 - `display(r, color)` 則用於將計算出的 row 顯示出來。 - **終止條件**：Primary 的 `do-while` 迴圈會持續進行，直到 `count` 變為 0 。這表示所有 Secondary Processes 都已經完成了他們的工作，並已將結果傳回給 Primary，或者已經收到了終止訊號。這種集中式的架構使得**中止偵測變得相對簡單和明確**。 **Secondary Process 的程式碼邏輯** ： ``` // Secondary Process P(i) 程式碼 recv(&row, P_primary, source_tag); // 從 Primary 接收初始任務 while (source_tag == data_tag) { // 只要接收到的是數據任務 (非終止訊號)，就持續執行 c.imag = min_imag + (row * scale_imag); for (x=0; x<640; x++) { c.real = min_real + (x * scale_real); color[x] = cal_pixel(c); // 計算單一 row 的像素顏色 } send(i, row, color, P_primary, result_tag); // 將處理 process ID、 row 和結果發送回 Primary recv(&row, P_primary, source_tag); // 請求下一個任務 } // 當 source_tag 不再是 data_tag (即收到 terminate_tag) 時，迴圈結束，Secondary Process 終止 ``` - **接收任務**：每個 Secondary Process 會首先從 Primary 接收一個任務 (`recv(&row, P_primary, source_tag)`) 。 - **任務迴圈**：Secondary Process 進入一個 `while` 迴圈，只要收到的 `source_tag` 是 `data_tag`（表示是一個計算任務），它就會持續執行。 - 在迴圈內部，它會遍歷一 row 中的所有像素，為每個像素計算其複數 `c`，然後呼叫 `cal_pixel(c)` 函數來決定該像素的顏色。 - 完成一 row 的計算後，Secondary Process 會將其自身的 ID、計算完成的 row 號以及該 row 的所有像素顏色，透過 `send()` 函數回傳給 Primary (`send(i, row, color, P_primary, result_tag)`) 。 - 接著，它會再次呼叫 `recv()` 函數，**請求 Primary 分派下一個任務** 。 - **終止**：當 Secondary Process 接收到的 `source_tag` 不再是 `data_tag`（表示收到了 Primary 發出的 `terminate_tag` 終止訊號）時，`while` 迴圈就會結束，該 Secondary Process 便會正確終止。這種集中式工作池的方法確保了任務的動態分配，使得計算量不均勻的 Mandelbrot 集合能夠實現良好的負載平衡，同時透過 Primary 的 `count` 變數和終止訊號，有效地管理了所有處理 process 的中止狀態。 ### Decentralized Work Pool - **與 Centralized 的關係**：Decentralized 其實可以看作是 Centralized 的一種變形，其基本架構與 Centralized 相似，主要目的是透過特定方式來減輕 single point of failure 的問題。 - **核心理念**：仍然是 **primary/secondary 架構**，但 **不再只有一個 single primary**，而是有多個 **primary**。 - **多個 primary 的角色可能性**： - **階層式 (Hierarchical)**： - 系統中會有一個 **主要的 primary (main primary)**，下面則有多個 **次要的 primary (secondary primary / mini-primary)**。 - 工作分配是階層式的：**worker** 會先向其 **局部的 primary** 請求工作；如果局部工作耗盡，該 **次要 primary** 才會再向 **上層的主要 primary** 請求工作，如此一層一層往上要。 - 這種方式在實際系統中是有效且簡單的解決方案。 - **潛在問題**：在分配過程中，仍可能出現某些 **次要 primary** 被分配到較多計算工作，導致不平衡。 - **地位對等 (Peer-to-peer primaries)**： - 這些 **primary** 之間的地位完全相同，每個 **primary** 都在做相同的事情。 - **worker** 可以任意找任何一個 **primary** 請求工作。 - **優點**：相較於階層式，可能更平衡，因為每個 **primary** 都可以做任何事情。 - **缺點**：**primary** 之間因為地位對等，會有較多的 **同步化 (synchronization) 開銷**，溝通量會大一點。 - **優缺點權衡**：越 Centralized，single point of failure 和 bottleneck 狀況越嚴重；越分散（接近 Distributed），這些問題會越少，但實作會越複雜，且終止條件判斷會越困難。 ### **Fully Distributed** Work Pool - **核心定義**：完全對等，沒有誰是 **primary**、誰是 **secondary** 的概念，所有參與者都是對等的 **peer-to-peer (P2P)** 關係。 - **架構特點**： - 每個 **worker** 都會有自己的 **本地工作池 (local work pool, WP)** 和 **queue** 來處理工作。 - **最重要的一點**：**worker** 之間可以 **主動地請求 (request) 或分配 (push) 工作**，以達成負載平衡 (load balance)。 - 工作池中的任務是散落的，需要透過各個處理器之間的溝通來達成平衡。 - **負載平衡的兩種實作方式**： - **接收者主動式 (Receiver-initiated / Work Stealing)**： - 由工作量較輕 (lighter loaded) 的 **worker (接收者)** 主動發出請求，從工作量較重 (heavily loaded) 的 **worker** 那裡「偷取」工作來做。 - **適用情境**：當整個系統的平均負載較高，只有少數 **worker** 負載很低時。這樣只有少數需要工作的 **worker** 會產生請求流量。 - 這種方式有時在文獻中被稱為 **"Work Stealing" (工作竊取)**。 - **發送者主動式 (Sender-initiated / Work Pushing)**： - 由工作量較重 (heavily loaded) 的 **worker (發送者)** 主動觸發負載平衡的動作，將工作「推」給其他 **worker**。 - **適用情境**：當整個系統的平均負載較輕，大部分 **worker** 都很輕時。這樣只有少數負載重的 **worker** 會產生請求流量。 - **選擇考量**：通常只會實作其中一種，選擇取決於整個系統的平均負載狀況。 - **挑戰與複雜性**： - **額外的溝通開銷**：為了達到平衡，**worker** 之間需要大量的溝通，這會增加網路流量 (network traffic)。 - **判斷負載狀況**：**process** 本身並不知道自己是輕載還是重載，除非它有 **全域視圖 (global view)**，否則難以判斷應向誰請求或把工作推給誰。這可能需要採取 **sampling** 等方法來近似判斷（例如隨機詢問幾個 **worker**，找最重的來「偷」工作）。 - **非立即性效果**：負載平衡往往需要多次迭代 (iterations) 和溝通才能達到平衡狀態，效果不是立即顯現。 - **優點**： - **沒有 bottleneck**：不會卡在特定的 **primary** 或 **secondary** 身上。 - **高擴展性 (Scalability)**：當系統規模非常大時，Fully Distributed 是一個很好的解決方案。 - **最短路徑演算法的 Fully Distributed 實作：** - **演算法原理**： - 基於迭代更新，每個 **vertex (頂點)** 都會不斷判斷其最短路徑值是否被更新。 - 如果一個 **vertex (vi)** 的最短路徑值被更新，它就會通知其鄰居 (neighbor) **(vj)**，讓鄰居也檢查自己的最短路徑值是否需要更新。 - **更新方式**：將從 source 到 **vi** 的最短路徑值，加上 **vi** 到 **vj** 邊的權重 (weight)，如果這個新值比 **vj** 目前記錄的最短路徑值還小，就更新 **vj** 的值。 - 這個過程會一直重複，直到沒有任何 **vertex** 的值再被更新，也就不再產生新的訊息，演算法便結束。 - **平行化實作**： - 每個 **vertex** 都在做相同的事情，因此非常適合平行化。 - 每個 **worker**（對應一個或多個 **vertex**）可以獨立執行這個邏輯，接收訊息、更新自己的狀態，並傳播給鄰居。 - **記憶體管理**： - 原本由 **primary** 統一管理的 **vertex queue** 和 **minimum distance array** 會被分散到每個 **worker** 內部。 - 邏輯上，仍然有工作池和距離陣列，但物理上，距離陣列的每個元素可能由不同的 **worker** 儲存，而每個 **worker** 也有自己的本地 **vertex queue**，只包含自己需要計算的任務。 - **worker** 只需要更新本地的 queue 和距離陣列值。 - 最後，需要將所有 **worker** 的結果收集起來，才能得到完整的最短路徑陣列。 - **工作池動態產生任務**：這個演算法的特殊之處在於，工作池中的任務 (task) 是在 **run-time** 根據計算過程動態產生的，而不是一開始就已知所有任務。當一個 **vertex** 的距離被更新，它就會被加入工作池中，等待後續處理。 --- 其他課程連結 [平行程式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)