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

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

9A~9B Synchronization Construct

今日大綱
OpenMP Directives Data scope attribute clauses
Section directive
Parallel Section with I/O
Synchronization Constructs
平行計算的方法介紹
Data Partitioning

### OpenMP Directives Data scope attribute clauses

#### Section directive
* **用途**：處理完全不同類型的工作共享方式，讓每個執行緒 (thread) 執行完全不同的程式碼。
* **語法**：使用 `#pragma omp sections`，後面可接一些 **子句 (clause)**。在其內部，需要定義每個獨立的 **section 區塊**，每個區塊都以一個結構化的程式碼區塊 (structured block) 標示。
* **執行限制**：
* 只能在 **parallel region** 內使用，即必須在 `#pragma omp parallel` 指令之後。
* 每個 `section` 只會被一個執行緒執行，且只執行一次。
* 由執行緒決定哪個可用的執行緒會被分配到哪個 `section`，程式員無法控制執行緒與 `section` 之間的分配 (不像排程機制)。
* 通常用於少量的區塊 (例如三到四個)，不適用於上百個區塊的場景。
* **例子**：若一個平行區域內有兩個執行緒和兩個 `section`，則通常一個執行緒做一個 `section`。一個執行緒會完全執行完它負責的 `section`，無法由多個執行緒分工一個 `section`。

#### Parallel Section with I/O
* **使用情境**：
* `#pragma omp parallel num_threads(10) shared(input)`：建立 10 個執行緒並共享 `input` 變數。
* 在平行區段內，`#pragma omp single` 確保只有 **單一執行緒** 執行 `scanf("%d", &input);` 操作。這是為了序列化 I/O，避免多個執行緒同時讀取造成問題。
* 該輸入隨後可在平行區段內進行處理，並印出結果。
* **`single` 指令**：
* 指定程式碼區塊只由一個執行緒執行，其他執行緒會跳過。
* 預設在程式碼區塊結束時會存在一個 **隱式屏障 (implicit barrier)**，所有其他執行緒會等待該單一執行緒完成後才能繼續。
* 若不希望等待，可加入 `nowait` 子句 (例如：`#pragma omp single nowait`)，則未執行此區塊的執行緒會繼續往下執行，移除隱式屏障。
* 主要目的通常是用於執行簡單的序列化操作，特別是 I/O。

#### Synchronization Constructs
這些指令用於在平行程式中控制執行緒的協調與資料的存取：
* **`master`**：
* 與 `single` 指令非常相似，指定程式碼區塊只由一個執行緒執行。
* **不同點**：明確指定執行該區塊的執行緒是 **主執行緒 (master thread)**。
* **優勢**：由於是主執行緒執行，不需額外協調來選擇執行緒，因此效率可能比 `single` 更高。
* **應用情境**：當需要確保特定程式碼區塊（例如有先後順序的序列化操作）總是由同一個執行緒來執行時，使用 `master` 比 `single` 更合適。
* **`critical`**：
* 目的：確保一個特定的程式碼區塊在任何時間點都 **只被一個執行緒執行**。
* 概念：類似於作業系統中的 **critical section**，用於解決共享資料同時被存取及修改的問題。
* 機制：像是在程式碼區塊的前後加上鎖和解鎖 (lock/unlock) 的操作。所有執行緒都必須執行這個區塊，但會被序列化，一個接一個地進入。
* **`barrier`**：
* 用途：作為一個明確的同步點。所有執行緒到達此點後會 **停止等待**，直到所有參與的執行緒都到達 `barrier` 點後，才能一起繼續往下執行。
* **`atomic`**：
* 與 `critical` 類似，也是為了解決共享資料在同時被存取和修改時的問題。
* **不同點**：`atomic` 的鎖定範圍是 **fine-grained**，它針對的是特定區域內的 **共享變數或記憶體引用** 進行即時檢查，以確保沒有競爭存取。
* 比較：`critical` 像 Java 的 `synchronized method`，將整個區塊包起來；`atomic` 則像 `synchronized statement`，只保護特定變數的操作。`atomic` 在對單一共享變數執行簡單操作時，通常比 `critical` 更有效率。

#### Lock OpenMP routine
* **功能**：OpenMP 提供了與 Pthreads 類似的低階鎖定函式，讓程式員可以手動管理鎖。
* `omp_init_lock()`：初始化鎖。
* `omp_set_lock()`：獲取鎖。
* `omp_unset_lock()`：釋放鎖。
* `omp_destroy_lock()`：銷毀鎖。
* `omp_test_lock()`：測試鎖的狀態。
* **`critical` 相較於手動鎖的優勢**：
* **無需宣告、初始化或銷毀鎖**：`critical` 指令由編譯器自動處理底層的鎖定機制。
* **明確控制 Critical section 的結束**：透過區塊語法，程式碼結束即鎖定解除。
* **編譯器輔助，降低錯誤**：減少忘記釋放鎖 (例如忘記 `omp_unset_lock`) 導致程式錯誤的機會。
* **程式碼更清晰**：直接使用指令標註，比手動呼叫函式更簡潔易懂。
* **功能等同**：兩者最終實現的功能是相同的，只是 `critical` 提供更高級、更安全、更易用的抽象。
* **程式碼**：
* **使用 `critical`**：在 `#pragma omp critical` 區塊內直接遞增 `count`。

        #pragma omp critical
        {
            count++;
        }

* **使用手動鎖**：需要 `omp_init_lock`、`omp_set_lock`、`omp_unset_lock` 和 `omp_destroy_lock` 進行手動鎖管理。

        omp_lock_t my_lock;
        omp_init_lock(&my_lock);
        // ...
        omp_set_lock(&my_lock);
        count++;
        omp_unset_lock(&my_lock);
        // ...
        omp_destroy_lock(&my_lock);

#### Data scope attribute clauses

**OpenMP 資料範圍的重要性**：
* 定義平行區域內變數的 **作用域 (scope)**，即變數是私有的 (private) 還是共享的 (shared)。
* 由於 OpenMP 指令會將結構化程式碼區塊轉換為函式程式碼，變數的真實樣貌與程式碼中看見的不同，因此明確指定資料範圍非常關鍵。

**Default Data Scope**：
* **全域共享變數 (Global shared variable)**：
* **基本原則**：在平行區域內的變數，**預設情況下 都是共享的**。
* **範疇**：這包括在檔案層級宣告的變數，以及在平行區域外部定義的變數（即全域變數或函式外部的變數）。
* **特性**：所有執行緒存取這些變數時，都指向相同的記憶體位址和相同的指標。
* **私有非共享變數 (Private non-shared variable)**：
* 只有在 **少數特定情況下**，變數預設會是私有的。
* **情況一：迴圈索引**：在平行化 `for` 迴圈或 `while` 迴圈中，迴圈的迭代器 (iterator) 變數（例如 `i` 或 `j`）預設是 **私有的**。每個執行緒會有自己獨立的 `i` 或 `j` 值。
* **情況二：在平行區域內宣告的堆疊變數**：在平行區域的程式碼區塊內部才宣告的變數，會被視為該函式內部的區域變數，因此也是 **私有的**。

**`private` 與 `shared` 子句**：
* 這些子句允許程式員 **override** 變數的預設資料範圍設定。
* `private(var_list)`：
* 明確指定變數列表中的變數為 **local variable**。
* 編譯器會在每個執行緒對應的函式程式碼中 **重新宣告** 該變數，使其擁有相同的變數名稱但 **不同的記憶體位址**，因此每個執行緒都有自己的私有副本。
* `shared(var_list)`：
* 明確指定變數列表中的變數為 **global variable**。
* 編譯器會確保這些變數在全域範圍被宣告，並將其指標傳遞給每個執行緒使用的函式，使所有執行緒共用同一個記憶體參考。

**`firstprivate` 與 `lastprivate` 子句**：
這些都是 `private` 變數的變形，主要處理進入和離開平行區域時私有變數的初始化和最終值。
* **`firstprivate(var_list)`**：
* **作用**：在將變數宣告為 `private` 的同時，**自動進行初始化**。
* **初始化方式**：每個執行緒的私有副本會以該變數在**進入平行區域之** 所持有的值進行初始化。
* **範例**：若 `v1` 在進入平行區域前被宣告並初始化為 10，使用 `#pragma omp parallel firstprivate(v1)` 後，每個執行緒的私有 `v1` 都會被初始化為 10。如果只用 `private`，則其初始值將是未定義的亂數。
* **`lastprivate(var_list)`**：
* **作用**：決定一個私有變數在 **離開平行區域之後** 的值。
* **值來源**：在平行區域結束時，**最後一個完成其工作 (例如最後一個迭代或區段) 的執行緒** 所持有的該私有變數的值，會被複製回（覆寫）原始的（在平行區域外部的）該變數。
* **範例**：在一個有 10 個執行緒的平行區域中，若每個執行緒根據其 ID 設定 `v1` 的值並睡眠不同時間（模擬不同完成時間），則使用 `lastprivate(v1)` 後，在平行區域之外的 `v1` 將會是 **最後完成的那個執行緒** 的 `v1` 值。

#### Other Data scope attribute clauses (Default, copyin, copyprivate, reduction)
* **`default(private | shared | none)`**：
* **用途**：將指定的資料範圍設定直接應用於 **平行區域內所有未明確宣告的變數**。
* **好處**：當平行區域中有很多變數時，避免逐一列出每個變數的資料範圍，簡化程式碼。
* **`copyin(var_list)`**：
* **用途**：當一個執行緒（特別是主執行緒）改變了它自己的私有變數值時，將這個改變 **傳播 (propagate)** 到所有其他執行緒的私有副本上。
* **機制**：所有執行緒都有變數的私有副本，但如果主執行緒修改了它的副本，這個新值會自動複製給所有其他執行緒的副本。
* **使用情境**：通常與 `master` 指令搭配使用。例如，當主執行緒讀取或處理資料，並希望其結果立即反映到所有其他執行緒的私有副本時。
* **`copyprivate(var_list)`**：
* **用途**：與 `copyin` 類似，但它旨在與 **`single` 指令** 搭配使用。
* **機制**：執行 `single` 區塊的那個單一執行緒所修改的變數值，會被複製到所有其他執行緒的私有副本上。
* **使用情境**：當 `single` 區塊由一個非主執行緒執行，且其結果需要被其他執行緒共享時。
* **`reduction(operator: var_list)`**：
* **用途**：在離開平行區域時，將多個執行緒的私有變數值進行 **聚合 (aggregation)**，然後將聚合後的結果複製到外部的共享變數。
* **概念**：類似於 MPI (Message Passing Interface) 中的 `reduce` 函式。
* **機制**：
1. 每個執行緒會擁有 `var_list` 中變數的 **私有副本**。
2. 每個執行緒在其私有副本上進行各自的計算（例如，計算部分和 partial sum）。
3. 當所有執行緒完成其計算並退出平行區域時，OpenMP 會使用指定的 `operator`（例如 `+`, `*`, `min`, `max` 等）將所有執行緒的私有結果 **合併 (combine)** 成一個最終結果，然後將這個結果存回原始的（全域的）共享變數中。
* **範例 (向量內積的累加)**：

        int result = 0; // Global variable
        #pragma omp parallel for reduction(+:result) private(i) // i是迴圈索引，預設是private
        for (i = 0; i < N; i++) {
            result += A[i] * B[i]; // Each thread updates its private 'result'
        }
        // After the loop, all private 'result's are summed into the global 'result'

* 在這個範例中，`result` 在迴圈內部會被視為 **私有變數**，每個執行緒計算自己的部分和 `partial sum`。
* `reduction(+:result)` 確保這些部分和在迴圈結束後會被 **累加 (aggregated)** 到外部的全域 `result` 變數中。
* 這樣做 **避免了同步問題 (synchronization issues)**，如多個執行緒同時對共享 `result` 進行加法操作導致的 race condition，從而提高了效能，因為無需使用 `critical` 指令。

#### Run-time Library Routines
OpenMP 執行時程式庫提供了一系列函式，主要用於查詢和設定 OpenMP 環境資訊，而非直接控制平行行為。
* **`omp_set_num_threads(num)`**：設定預設的執行緒數量，用於後續的平行區域。
* **`omp_get_num_threads()`**：在平行區域內呼叫時，回傳當前平行區域中實際建立的執行緒總數。
* **`omp_get_thread_num()`**：回傳當前呼叫此函式的執行緒的 ID 號碼。主執行緒的 ID 為 0。
* **`omp_get_thread_limit()`**：回傳系統或環境允許的最大執行緒數量。
* **`omp_get_num_procs()`**：回傳系統中可用的處理器核心數量。
* **`omp_in_parallel()`**：檢查當前執行點是否在一個平行區域內部。這對於判斷平行區域是否因 `if` 子句而真正被啟用很有用。

---

### 平行計算的方法 (Methods of Parallel Computation)

課程將介紹四種主要的平行計算方法，以及兩個重要的附帶問題：
1. **Embarrassingly Parallel**
2. **Load Balance Termination**
3. **Divide and Conquer**
4. **Pipeline**
5. **Synchronous Computation**

#### 1. Embarrassingly Parallel
* **定義**：這類計算問題中的每個運算任務都是 **完全獨立的**，彼此之間幾乎沒有或沒有資料依賴關係，也無需在核心計算階段進行通訊或同步。
* **特性**：
* **最容易平行化**：因為任務獨立，可以簡單地分配給不同的處理器或執行緒執行。
* **良好可擴展性**：增加計算資源通常能直接提高效能。
* **通訊/同步點**：只在 **輸入資料分配** 和 **輸出結果收集/聚合** 階段需要協調。
* **範例應用**：
* **Image Transformations**：這是 GPU 最常處理的任務之一，因為每個像素可以獨立處理。
* **Shifting (平移)**：透過對每個像素的 X 和 Y 座標進行加減運算來實現，每個像素的操作都是獨立的。
* **Scaling (縮放)**：對每個像素的 X 和 Y 座標乘以一個縮放因子來實現，每個像素的操作都是獨立的。
* **Rotation (旋轉)**：對每個像素的 X 和 Y 座標進行涉及三角函式的運算來實現，儘管公式較複雜，但每個像素的操作仍是獨立的。
* **Monte Carlo simulations (蒙地卡羅模擬)**：透過大量獨立的採樣點來近似複雜問題的結果。每個採樣點的計算是獨立的，非常適合平行處理，能加快近似速度 (例如計算圓周率 Pi)。
* **Mandelbrot set (曼德博集合)**：這是一個繪圖應用，圖中每個像素的計算都是獨立的。
* **特殊之處**：儘管計算獨立，但每個像素的 **計算量是不可預測且差異巨大** 的。這使得它成為一個絕佳的範例，用於探討 **負載平衡 (load balancing)** 的重要性，並比較靜態和動態排程對效能的影響。

#### 2. Load Balance & Termination (負載平衡與終止)
* **Load Balancing**：
* **重要性**：在平行程式中，整個工作的執行時間由 **最慢的那個任務或執行緒** 完成時間決定。
* **目標**：希望盡量平均分配計算量，讓所有執行緒能同時結束，避免資源浪費和延長總執行時間。
* **Termination Detection**：
* **問題**：在有許多執行緒或進程的平行環境中，特別是在完全分散式且沒有中央協調者的演算法中，如何判斷所有工作都已完成並安全終止是一個基本但非顯而易見的問題。
* **挑戰**：因為沒有單一的控制點來告知所有執行緒何時結束，需要設計特定的分散式演算法來解決。

#### 3. Divide and Conquer
* **概念**：將一個大問題分解成若干個獨立的子問題，分別解決這些子問題（通常在不同的處理器上平行執行），然後將子問題的解組合起來，形成原問題的解。
* **優勢**：
* 可以減少重複計算。
* 平行執行時，子問題的執行時間可以**重疊**，從而顯著加速。

#### 4. Pipeline
* **概念**：將一個工作分解成一系列順序的階段，每個階段負責處理一個特定的子任務。不同階段可以同時對不同的資料元素進行操作。
* **常見應用**：製造業生產線、CPU 指令處理等。
* **類型**：管線化不僅限於一種形式，實際上可以分為三種不同類型。

#### 5. Synchronous Computation
* **概念**：這類計算通常涉及 **iterative algorithms**，其中不同 iteratation 之間存在 **資料依賴關係 (data dependency)**。
* **需求**：由於資料依賴，必須在這些迭代之間加入特定的 **同步點 (synchronization point)**，以確保資料的一致性和正確性。
* **重要性**：在許多實際應用中（尤其是在 GPU 程式中），平行迴圈往往無法完全獨立，需要顯式同步來處理這些依賴。

---

### Data Partitioning
* **目的**：為了實現平行化，必須將輸入資料（例如影像的像素）有效地劃分並分配給不同的處理器或執行緒進行計算。
* **分區方式的影響**：不同的劃分方式（例如水平切割、垂直切割或區塊切割）會對 **load balancing** 和 **通訊量 (communication volume)** 產生顯著影響。
* **範例 (Mandelbrot set)**：
* 簡單的數據量劃分（如平均分配行數）可能導致 **計算量的不平均**。例如，在 Mandelbrot 集中，某些區域的像素計算量遠大於其他區域，導致部分執行緒需要執行更多工作。
* 一個好的 Partition 策略不僅要考慮數據量的平均，更要考慮 **計算量的平均**。
* **通訊量考量**：
* 在需要通訊的平行計算中（尤其是在同步計算中），通訊量往往與不同執行緒或處理器之間的 **交界資料數量 (amount of boundary data)** 成正比。
* 數據如何被切割，會直接影響到資料通訊和訊息傳遞的開銷。

---
其他課程連結

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