---
# System prepended metadata

title: 平行程式 10C~10D Synchronization Tools & Open Multi-Processing(OpenMP)Synchronization Construct
tags: [平行程式]

---

教材: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)


