平行程式 8B~8D Synchronization Tools & Open Multi-Processing(OpenMP)

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