---
# System prepended metadata

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

---

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

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

8B~8D  Synchronization Tools & Open Multi-Processing(OpenMP)

今日大綱
1.Semaphore 是什麼?
2.Monitors  是什麼?
3.OpenMP (Open Specification for Multi-Processing) 介紹
4.OpenMP 指令詳述
5. parallel 指令
6.工作分配建構子 (Work-Sharing Constructs)


### Semaphore 是什麼?

- **定義與目的**:
    - Semaphore 主要是為了**解決同步化問題**。
    - 與 Lock 不同，Semaphore 是一個 **counter**。
    - 它代表在 Critical Section 裡面，到底有多少個執行緒 (thread) 可以進入，或是還有多少資源可以被存取。
- **與 Lock 的差異**:
    - **Lock** 是 **binary**，只能表示「有人在裡面」或「完全沒有人」，像是 0 或 1。
    - **Semaphore** 可以是一個**大於一的數字**，因此可以控制多個執行緒同時存取資源。
    - 如果將 Semaphore 的數量限制在 1，它就等同於 Lock，這種情況下我們稱之為 **Binary Semaphore**，但較少這樣使用，通常直接用 Lock 即可。
    - 當數量大於 1 時，則稱為 **Counting Semaphore**。
- **操作方式**:
    - Semaphore 變數本身就是一個數字，你只能對它做**increment** 和 **decrement**。
    - 當有執行緒使用或進入 Critical Section 時，這個數字會 **減一 (wait)**，表示可用的資源變少。
    - 當有執行緒離開或釋放資源時，這個 **counter** 會 **加一 (signal)**，表示可用的資源變多。
- **對應函式 (API)**:
    - `sem_wait` (或 `p`): 用來獲取 (acquire) 資源，執行「減」的動作。如果計數器小於等於 0 (沒有資源)，執行緒會被 **阻塞 (block)** 在此，直到有資源可用。
    - `sem_post` (或 `signal`): 用來釋放 (release) 資源，執行「加」的動作。
    - `sem_init`: 初始化 Semaphore 的值。這個初始值可以是任意大於零的整數，代表一開始有多少資源可用。
    - `sem_destroy`: 銷毀 Semaphore。
    - `sem_getvalue`: 取得目前計數器的值，得知還剩下多少資源.
- **實作與使用**:
    - Semaphore 不包含在 `pthread.h` 裡面，而是由 **作業系統 (OS)** 直接提供，通常包含在 **POSIX API** (例如 `semaphore.h`) 中。
    - 它主要用來同步化 **Process**，但也可以拿來同步化 **Thread。
    - 其用法與 Condition Variable 類似，但功能不同。
    - **使用者需要確保正確的邏輯**：例如，如果沒有使用資源卻呼叫了 `signal`，可用資源的計數會一直往上加，不會被初始值限制。如果連續呼叫兩次 Lock 但沒有 Unlock，也會造成問題。這表示這些工具雖然好用，但很容易因為程式設計錯誤導致難以偵測的 bug。

### Monitors  是什麼?

- **目的**:
    - Monitor 是一種 higher-level 的同步化工具，**簡化程式設計師的負擔**，讓他們不再需要手動編寫 `wait` 和 `signal` (或 Lock/Unlock) 等操作。
- **核心概念**:
    - Monitor 其實就是一個特殊的類別 。
    - 在這個類別中，有 **私有變數 (private variables)** (即我們要保護的共享資料 shared data) 和定義存取這些資料的 **方法 (methods)**.
    - Monitor 的內建功能會保證在任何時間點，只有一個執行緒可以在這個類別內部執行它的方法 。這其實就是 Critical Section 的概念，但由 Monitor 自動處理。
    - 只要是被 Monitor 類別包裝的資料，**絕對不會有同步化問題**，因為存取會自動序列化 。
- **Java 中的實作例子**:
    - Java 提供了 Monitor 的功能，主要有兩種方式：
        1. **方法層級的 `synchronized` 關鍵字 (Method-level `synchronized`)**:
            - 在方法定義前面加上 `synchronized` 關鍵字，就能保證一次只有一個執行緒可以執行這個類別中任何被 `synchronized` 修飾的方法。
            - 如果某些方法與共享資料無關，可以不加 `synchronized`，它們的行為就和一般的函式一樣。
        2. **陳述句區塊的 `synchronized` 陳述句 (Statement-block level `synchronized`)**:
            - 你可以將一段程式碼包裝在 `synchronized (object)` 區塊中。
            - `object` 是一個變數或記憶體參考 (memory reference)，告訴編譯器這個記憶體內容可能有同步化問題。
            - Java Runtime 會自動在執行時偵測並加上 Lock 和 Unlock 的陳述句，保護這個區塊內的記憶體存取。
            - 這提供了更 **fine-grained** 的同步化控制。
- **優缺點**:
    - **優點**: 極大地減少了程式設計錯誤 ，因為同步邏輯由語言層級自動處理，簡化了複雜的偵錯過程。
    - **缺點**: 相對來說，其執行效率可能較差，因為它可能會在內部加入一些不一定必要的 Lock，導致程式效能下降。Monitor 是一種高階模式，雖然易於描述，但內部實現可能較複雜。

### OpenMP (Open Specification for Multi-Processing) 介紹

- **基本概念**:
    - OpenMP 是一種用於**共享記憶體 (shared memory) 程式**的函式庫，它透過 **編譯器指令 (compiler directives)** 的方式來實現平行化。
    - 它的全名「Open Specification for Multi-Processing」代表著它是一個 open specification，只是一個介面，具體實作可能有多種版本。
    - **不要與 OpenMPI 混淆**: OpenMPI 是一個用於訊息傳遞 (Message Passing Interface, MPI) 的庫，與 OpenMP 完全不同。
    - OpenMP 是 **可移植的 (portable)**，因為它只是一個規範，程式碼在不同系統環境下只需重新編譯即可運行。
- **程式設計模型：Fork-and-Join**:
    - 這是 OpenMP 最核心且固定的模型。
    - 在 OpenMP 程式中，一開始有一個主執行緒 (master thread)。
    - 當遇到 OpenMP 的平行指令時，主執行緒會 fork 出多個執行緒 (類似 Pthread 的 `pthread_create`)。
    - 這些被 fork 出的執行緒會執行同一段程式碼區塊。
    - 當這段程式碼區塊執行完畢後，所有 fork 出的執行緒會 join 回主執行緒 (類似 Pthread 的 `pthread_join`)。
    - 與 Pthread 相比，OpenMP 的彈性較小，因為它必須遵循 Fork-and-Join 模型，不能隨意在任何時間點建立任意的執行緒。但它在處理大部分平行化問題時非常方便。
- **編譯器指令 (Compiler Directives)**:
    - OpenMP 的主要工作方式是透過編譯器指令。程式設計師只需在程式碼中添加特定的 `#pragma omp` 指令。
    - 編譯器會根據這些指令自動產生低階的平行程式碼 (類似 Pthread 程式碼)。
    - OpenMP 幾乎沒有直接與程式執行邏輯相關的函式，大部分是查詢系統資訊的函式 。
- **指令語法結構**:
    - `#pragma omp directive_name [clause(parameter), ...]`
    - `#pragma omp`: 固定語法，讓編譯器辨識 OpenMP 指令。
    - `directive_name`: 指定要使用的平行化方式 (例如 `parallel`, `do`,`for`)。
    - `clauses`: 可選的參數設定，用來控制指令的行為。不同的指令會有不同的 clause 選項，例如 `if`, `num_threads`, `schedule`, `private`, `shared` 等。
        - **資料範圍 (Data Scope)**: 這是編寫 OpenMP 程式時最棘手的地方之一。透過 `private`, `shared` 等 clause 來告訴編譯器變數是私有的 (local) 還是共享的 (global)，編譯器會據此產生程式碼。
- **程式語言與大小寫**:
    - OpenMP 支援 C, C++, Fortran。
    - OpenMP 指令是**大小寫敏感 (case-sensitive)** 的。
    - 原則上一個指令中只能有一個 `directive_name` ( `parallel` 是唯一的特例，可以與其他工作分配指令結合)。
    - 指令作用於一個 **陳述句區塊 (statement block)**，通常是一個用 `{}` 包起來的程式碼區塊。

### OpenMP 指令詳述

#### `parallel` 指令

- **功能**:
    - **唯一會建立執行緒 (create threads) 的指令**。
    - 建立一組執行緒 (a team of threads)
    - 這些建立的執行緒會執行**完全相同的**程式碼區塊，這個區塊稱為 **Parallel Region (平行區域)**。
    - 在 Parallel Region 結束時，有一個**隱含的屏障 (implicit barrier)**。所有執行緒必須完成其工作才能進入下一個陳述句。這符合 Fork-and-Join 模型，執行緒會「結合」回主執行緒。
    - 如果其中一個執行緒 crash，所有執行緒都會 crash，整個程式結束。
- **Parallel Region 的限制**:
    - 不能包含跳出 (branch out) 平行區域的跳轉指令 (例如 `goto`)。
    - 不能跨越不同的檔案 (cross different files)。
    - 可以呼叫其他函式，但不建議讓流程變得混亂。
- **決定執行緒數量 (Number of Threads)**: 依優先順序決定
    1. **`if(condition)` clause**:
        - 如果 `condition` 為 `false`，則該平行區域會以**一個執行緒**執行，就好像 OpenMP 指令不存在一樣。
        - 如果為 `true`，則繼續判斷後面的選項。
    2. **`num_threads(N)` clause**:
        - 直接在 `#pragma omp parallel` 指令中指定要建立的執行緒數量 `N`。
        - 這是最直接和明確的方式。
    3. **`omp_set_num_threads(N)` API**:
        - 透過 OpenMP 函式呼叫設定一個**預設值 (default value)**。
        - 必須在進入平行區域之前呼叫。
        - 會影響所有後續未指定 `num_threads` 的平行區域。
    4. **`OMP_NUM_THREADS` 環境變數 (Environment Variable)**:
        - 在系統環境中設定這個變數的值。
        - 編譯器會在執行時偵測此變數來決定執行緒數量。
    5. **系統 CPU 核心數**:
        - 如果以上都沒有設定，OpenMP 會使用目前系統的 CPU 核心數作為預設值。
- **巢狀平行 (Nested Parallelism)**:
    - 允許在一個平行區域內再包含另一個平行區域 (巢狀平行區域)。
    - 巢狀平行是否被支援取決於 OpenMP 函式庫的實作和是否啟用 (`omp_set_nested()` 函式)。
    - 如果巢狀功能被禁用，內層的平行區域會被忽略，並以一個執行緒執行。

### 工作分配建構子 (Work-Sharing Constructs)

- 這些指令的目的是**分配工作給已經存在的執行緒**，它們**不會建立新的執行緒**。
- 因此，它們**必須被包含在一個 `parallel` 區域內部**才有意義。通常你會看到 `parallel` 搭配這些指令，甚至簡寫成一個指令 (例如 `#pragma omp parallel for`)。
- 這些指令的末尾通常也有 implied barrier (隱含的屏障)，所有被分配工作的執行緒必須完成才能進入下一個程式碼區塊 (除非使用 `nowait` clause)。
    
- 主要有三種類型:
    
    1. **`#pragma omp for` (或 `do`)**:
        
        - **資料平行 (Data Parallelism)**: 專門用於將 `for` 迴圈的**迭代 (iterations)** 分配給不同的執行緒來平行執行。
        - 前提是迴圈的迭代之間**不能有資料相依性 (data dependency)**。
        - **常用 Clauses**:
            - **`nowait`**: 移除迴圈結束時的隱含屏障。
                - 正常情況下，所有執行緒必須完成迴圈的所有迭代，才能一起進入下一個陳述句。
                - 使用 `nowait` 後，一旦執行緒完成了它被分配的迭代，就可以立即繼續執行平行區域中的後續程式碼，無需等待其他執行緒。
            - **`schedule(type [, chunk_size])`**: 定義迴圈迭代如何分配給執行緒。
                - `type`:
                    - **`static`**: 迭代在**運行前**被靜態分配。執行緒會以固定大小的區塊 (`chunk_size`) 輪流分配迭代。
                        - **`chunk_size`**: 每次分配給一個執行緒的迭代數量。
                        - 優點: 調度開銷 (scheduling overhead) 小。
                        - 缺點: 如果各迭代工作量不均，可能導致負載不平衡。
                    - **`dynamic`**: 迭代在**運行時**動態分配。執行緒完成當前工作後，會向調度器 (scheduler) 請求下一個工作區塊。
                        - 優點: 確保**負載高度平衡 (highly balanced)**，適合工作量不均的迭代。
                        - 缺點: 調度開銷較大，因為需要頻繁地請求工作。
                    - **`guided`**: `dynamic` 的變種。起始的 `chunk_size` 較大，隨著剩餘工作量的減少而逐步減小，最終可能減至 1。
                        - 優點: 兼顧負載平衡和減少調度開銷。
                    - **`runtime`**: 在**運行時**根據 `OMP_SCHEDULE` 環境變數的值來決定調度類型。
                    - **`auto`**: 由編譯器自動選擇調度類型。**不建議使用**，通常效果不佳。
                - 選擇調度類型: 如果每個任務的工作量相似且可預期，選 `static`。如果工作量難以預期且有差異，選 `dynamic` 或 `guided`。
            - **`ordered`**: 確保平行迴圈的結果以**循序執行 (sequential order)** 的順序產生。
                - **不建議使用**，因為會引入大量的同步化機制 (synchronization locks)，導致平行效率非常低。
            - **`collapse(N)`**: 將巢狀 `for` 迴圈的 `N` 層扁平化 (flatten) 為一個單層迴圈，然後對其迭代進行調度。
                - **增加平行度 (degree of parallelism)**。
                - **限制**: 巢狀迴圈之間不能有任何陳述句。
                - **注意**: 必須確保扁平化後的迭代之間**沒有資料相依性**，否則會導致錯誤的結果。
    2. **`#pragma omp sections`**:
        - **任務平行 (Task Parallelism)**: 讓不同的執行緒執行**完全不同的程式碼區塊 (sections)**
        - 每個 `section` 會被一個執行緒執行。
        - 你手動定義要分配給執行緒的特定程式碼段。
    3. **`#pragma omp single`**:
        - 保證在該平行區域中，被此指令包裝的程式碼區塊**只會被一個執行緒執行**。
        - 其他執行緒會等待此區塊完成 (因為有隱含屏障)。
        - **應用場景**: 適合執行不適合平行化的任務，例如 **I/O 操作**，因為通常一個 process 或 thread 寫資料就足夠，避免競爭存取問題。
- **平行與工作分配指令的結合**:
    - `parallel` 指令可以與 `for`, `sections` 或 `single` 結合使用，例如 `#pragma omp parallel for`。
    - 此時，`parallel` 的 clause (如 `num_threads`) 和工作分配指令的 clause (如 `schedule`) 會一起列在指令後面。

---
其他課程連結

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