---
# System prepended metadata

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

---

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

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

10A~10B Synchronization Tools & Open Multi-Processing(OpenMP)Synchronization Construct

今日大綱
Embarrassingly Parallel Computation 
影像平移（Image Shift )
**蒙地卡羅方法 (Monte Carlo Method)**
Mandelbrot 集合 (Mandelbrot Set)


### Embarrassingly Parallel Computation 

**平行計算的第一種形式：Embarrassingly Parallel Computation (EPC)**

我們今天要進入第一種平行計算，它叫做 **embarrassingly parallel computation**，這是最簡單的形式。

**1. 定義與核心特性**

• 在計算過程中，**所有任務 (tasks) 之間是完全獨立的**。
• 因此，**只有在資料一開始被分割 (partition) 到這些任務上，以及最後將計算結果收集回來時，才需要溝通**。
• **中間的計算過程完全不需要任何溝通**。這表示您幾乎不需要擔心溝通的問題。
• 當您在處理不同資料區塊時，不需要考慮它們之間是否需要溝通，因為在 Embarrassingly Parallel Computation 中，任務彼此獨立，不需要進row 資料交換。

#### **應用範例一：影像平移（Image Shift）**

在此類計算中，各個任務（tasks）之間是**完全獨立**的。因此，僅在資料的初步分割（partition）分配給這些任務，以及最終收集結果時，才需要溝通；**中間的計算過程無需任何溝通**。影像處理，特別是像素層級的轉換操作（如平移、縮放、旋轉），是這種平行計算的常見應用，因為每個像素的計算都是獨立的任務。

**一、 整體架構：primary-secondary 模型**

此實作採用了 primary-secondary 架構：

- **primary process**：主要負責資料的分割、任務的分配，以及最終結果的收集和更新。
- **secondary  process**：接收資料分割後，對其內部每個像素執行轉換操作。

二、 資料分割與任務分配  primary process

- Primary  決定資料分割方式。在這個例子中，影像（假設為 480x640 像素）被**按列（row）分割**。
- **分割寬度為 10 列 (rows)**：每個資料區塊包含 10 列。
- **分派給 48 個 secondary  process**  **：由於總共有 480 列 (480 = 48 * 10)，每個 secondary  process** 剛好會分到一個 10 列的區塊。
    
    ```
    // primary  Process
    for(i=0, row=0; i<48; i++, row+=10) // 迭代 48 次，為每個 secondary  process 分配任務
        send(row, P_i); // 將起始列號 (row number) 傳送給第 i 個 secondary  process  (P_i)
    ```
    
- **僅傳送起始列號**：假設所有 process 都能從共享資料空間或檔案中存取完整的影像資料，Primary 只需告知每個 secondary  process 其負責處理的起始列 ID。
- **靜態負載平衡 (Static Load Balancing)**：由於每個 secondary  process 被分配了相同數量的列（10 列），且每個像素的計算量假定相同，這是一種**靜態的負載平衡**方式。這種方式假設每個任務的工作量是均勻的，只確保每個 process 獲得相同數量的資料即可實現平衡。

**三、 影像處理與結果回傳 secondary  process**

- **secondary  process 接收任務**：每個 secondary  process 會從 primary 接收其負責處理的起始列號。
    
    ```
    // secondary  process
    recv(row, Pmaster); // 接收 Primary 傳來的起始列號
    ```
    
- **執行平移操作**： secondary  process 在其被分配的 10 列範圍內，遍歷每個像素，執行影像平移的轉換操作。
    
    - 平移操作是針對每個像素獨立進行的，透過增加 `delta_x` 和 `delta_y` 來計算新的坐標。
    
    ```
    for(oldrow = row; oldrow < (row+10); oldrow++) // 遍歷分配到的 10 列
        for(oldcol = 0; oldcol < 640; oldcol++) { // 遍歷每一列中的所有行
            newrow = oldrow + delta_x; // 沿 x 軸平移
            newcol = oldcol + delta_y; // 沿 y 軸平移
            send(oldrow, oldcol, newrow, newcol, Pmaster); // 將舊坐標和新坐標傳回 Master
        }
    ```
    
- **回傳新坐標**： secondary  process 計算出每個像素的**新坐標 (newrow, newcol)後，會將其連同**舊坐標 (oldrow, oldcol)一起回傳給 primary 。在此平移的例子中，如果像素的值不變，則無需傳送像素值，只需傳送坐標資訊。

四、 結果收集與影像更新 primary process

- Primary process 收集結果：primary process 持續接收來自所有從 secondary  process 的舊坐標和新坐標資訊。
    
    ```
    // primary process (收集與更新邏輯)
    for(i=0; i<(480*640); i++) { // 預期接收所有像素的結果
        recv(oldrow, oldcol, newrow, newcol, P_my); // 接收來自 secondary  process  處理後的像素坐標
        // 處理邊界條件 (此處 pseudo code 的邏輯可能需進一步檢查，通常會檢查新坐標是否在影像範圍內才進行更新)
        // 假設此處 `if` 條件是判斷新坐標在影像範圍內:
        // if ((newrow>=0) && (newrow<480) && (newcol>=0) && (newcol<640))
        //     temp_map[newrow][newcol] = map[oldrow][oldcol];
        // 由於 pseudo code 的條件是 `||` 且是 `!` 則表示新坐標在範圍外也更新，這可能是一個錯誤或特殊處理
        // 這裡將按照原文描述的邏輯進行理解，即如果新坐標在範圍外，則更新 temp_map
        if ((newrow<0) || (newrow>=480) || (newcol<0) || (newcol>=640))
            temp_map[newrow][newcol] = map[oldrow][oldcol];
    }
    ```
    
- **使用暫存陣列 (temp_map) 避免資料依賴問題**：
    
    - 在更新影像時，Primary  會先將所有處理過的新像素值存入一個**暫存陣列 (`temp_map`)** 中，而非直接更新原始影像陣列 (`map`)。
    - 這是因為新的影像 (`new map`) 依賴於舊的影像 (`old map`)。如果直接在原始 `map` 上更新，可能導致某些像素在計算其新值時，讀取到已經被其他新值覆蓋的「舊值」，從而產生**資料依賴錯誤 (data dependency)**。
    
    ```
    for(i=0; i<480; i++) for(j=0; j<640; j++) temp_map[i][j] = 0; // 初始化暫存陣列
    
    // ... (接收數據部分如上)
    
    for(i=0; i<480; i++) for(j=0; j<640; j++) map[i][j] = temp_map[i][j]; // 將暫存陣列完整覆蓋回原始影像陣列
    ```
    
    - 當所有像素的處理結果都收集並存入 `temp_map` 後，Master 會將 `temp_map` 的內容**overwrite** 到原始的 `map` 陣列中。


### **應用範例二：Monte Carlo Method (蒙地卡羅方法)**

除了影像轉換這種相對單純的問題外，Embarrassingly Parallel Computation 在許多複雜問題中也廣泛應用。

- **定義與概念**：
    - Monte Carlo Method 是一個**演算法的類別 (class of algorithms)**。
    - 它**基於取樣 (sampling) 的概念來解決問題**。
    - 核心思想是**透過模擬 (simulation) 來求解問題**，而不是直接解析方程式。
    - 它透過大量取樣與模擬來查看結果，然後根據結果調整方程式的值。
- **起源**：
    - 它是在 **Manhattan Project (曼哈頓計畫)** 期間發展出來的，當時為了設計核子武器。
    - 在科學計算中，經常會遇到許多複雜的方程式，需要非常精確的解答，例如彈道、化學比例、材料結構等。
    - 當遇到難以找出精確極值或最佳解的複雜方程式時，Monte Carlo Method 提供了一種解決方案。
- **主要優點**：
    - 您只需寫一個模擬器 (simulator) 來模擬其數學模型即可解決複雜的數學問題。
    - **每一次的模擬都是獨立的**。這意味著如果擁有大量計算資源，可以**同時進行大量的取樣和模擬**。
    - **準確度會隨著取樣數量增加而提升**。它可以用計算資源來換取最終結果的準確度 (accuracy)。
    - 這種方法非常有效率，特別適合用電腦來求解。
- **例子一：計算圓周率 (Pi)**：
    - **概念**：將一個單位半徑的圓 (面積為 π) 放入一個 2x2 的正方形 (面積為 4) 中。
    - **機率**：在正方形區域內隨機生成一個點，該點落在圓內的機率是 **π/4** (圓面積/正方形面積)。
    - **實作**：
        1. 在正方形內隨機生成非常大量的點。
        2. 對於每個點 (x, y)，判斷它是否落在圓內。判斷方式是計算點到圓心的距離。如果 $x^2 + y^2 <= 1$ (單位半徑)，則點在圓內。
        3. 統計落在圓內的點的數量。
        4. 根據 **(落在圓內的點數 / 總取樣點數) ≈ π/4** 這個比例，即可推算出 π 的近似值。
    - **準確性**：取樣的點越多，計算出的 π 值就越接近真實值。
- **例子二：計算函數的積分面積 (Integral Area)**：
    - **概念**：類似計算圓周率，將要積分的函數 f(x) 框在一個矩形區域內。
    - **實作**：
        1. 在該矩形區域內隨機生成大量的點 (x, y)。
        2. 對於每個點，比較它的 y 值與該 x 值對應的函數值 f(x)。
        3. 如果 `y <= f(x)`，則點落在函數曲線下方 (即積分區域內)。反之，如果 `y > f(x)`，則點在區域外。
        4. 統計落在積分區域內的點的數量。
        5. 根據 **(落在積分區域內的點數 / 總取樣點數) ≈ (積分區域面積 / 矩形總面積)** 這個比例，即可推算出積分面積。
    - **通用性**：這個方法具有很強的通用性，可以推廣應用於解決許多不同的問題。
    - **平行性**：**每個取樣點的處理都是獨立的**，因此非常適合進行平行計算。




### **應用範例三：Mandelbrot 集合 (Mandelbrot Set)**

Mandelbrot 集合是一個**特殊的數學問題**。它將複數平面上的數字進行分類，判斷它們是否「屬於」Mandelbrot 集合。一個數字是否屬於此集合，由一個數學條件決定，最終所有數字只會落在集合內或集合外這兩種可能性。

**判斷條件**： Mandelbrot 集合的判斷依據一個**迭代的運算法則**：

- 對於任何一個複數 $C$（由實部和虛部組成，可投射到座標點上），我們需要判斷它是否屬於這個集合。
- 迭代公式為：$Z_{k+1} = Z_k^2 + C$。
- 起始值：程式碼中 `cal_pixel` 函數將 **`z` 初始化為 (0, 0)**，即 $Z_0 = 0$ 。
- 判斷條件：如果在無限次迭代後，複數 $Z_k$ 離原點的距離（即其**模長 $|Z_k|$**）始終保持在**小於或等於 2** 的範圍內，則該複數 $C$ 屬於 Mandelbrot 集合。
- 反之，如果 $|Z_k|$ 在迭代過程中**超過了 2**，它將會「發散」，並代表該複數 $C$ **不屬於** Mandelbrot 集合。在程式碼中，為了簡化計算，我們檢查的是**模長平方 (`lengthsq`) 是否超過 4.0**，這與模長超過 2 是等價的 。

**Fractal Property**： Mandelbrot 集合最特別的點在於它擁有一種**分形 (fractal)的特性**。

- **定義**：分形圖形在不同的尺度 (scale) 下會呈現**自我重複 (self-repeating) 的狀況**。
- **視覺化**：如果你對 Mandelbrot 集合的圖形進行「縮放 (zoom in)」，你會發現在放大後的局部區域，其圖形與原始圖形驚人地相似，甚至難以辨別差異。
- **意義**：這種特性不僅限於單一圖案，而是包含許多自我重複的模式。它在物理學（如混沌原理、結晶現象）和自然界中許多行為的描述中都具有重要意義。

**圖形著色**： Mandelbrot 集合的圖形可以透過著色變得非常美觀。

- **著色原理**：不同的顏色點是根據該點在**第幾次迭代時**被發現不屬於 Mandelbrot 集合而決定的。
- **顏色與迭代次數**：
    - 如果某點**越早**被發現發散（即 $|Z_k|$ 越早超過 2），它的顏色會越淺。
    - 如果某點在達到**最大迭代次數**後仍未發散（即始終 $|Z_k| \le 2$），它會被歸類為集合的成員，並通常以**最深的顏色**表示。
- 這種著色方式讓分形特性更加明顯，產生豐富多彩的影像。

### **循序 Mandelbrot 集合程式 - 測試程式 (`cal_pixel`)**

這個測試程式的目的是，給定一個複數 $C$，它會計算並回傳該複數在多少次迭代後其模長 $|Z_k|$ 超過 2。如果達到最大迭代次數後仍未超過，則回傳最大迭代次數 。

`cal_pixel` 函數說明 

```
int cal_pixel(complex c) {
    int count = 0;          // 迭代次數計數器
    int max = 256;          // 最大迭代次數
    float temp, lengthsq;   // 暫存變數，lengthsq 為 |z|^2
    complex z;
    z.real = 0;             // 初始化 z 的實部為 0
    z.imag = 0;             // 初始化 z 的虛部為 0
    do {
        // 計算下一個 z.real = (z.real^2 - z.imag^2) + c.real
        temp = (z.real * z.real) - (z.imag * z.imag) + c.real;
        // 計算下一個 z.imag = (2 * z.real * z.imag) + c.imag
        z.imag = (2 * z.real * z.imag) + c.imag;
        z.real = temp;
        // 更新 |z|^2 = z.real^2 + z.imag^2
        lengthsq = (z.real * z.real) + (z.imag * z.imag);
        count++; // 迭代計數器加一
    } while ((lengthsq < 4.0) && (count < max)); // 循環條件：|z|^2 < 4 且 迭代次數未達上限
    return count; // 返回迭代次數
}
```

- 此函數接收一個複數 `c` 作為輸入，代表要測試的像素點 。
- 它初始化 `z` 為 (0, 0) 。
- 在 `do-while` 迴圈中，它根據迭代公式 `Z_{k+1} = Z_k^2 + C` 計算新的 `z` 值 。
- 同時，它計算 `z` 的模長平方 `lengthsq` (即 $|Z_k|^2$) 。
- 迴圈會持續進行，直到 `lengthsq` 大於或等於 4 (表示 $|Z_k|$ 大於或等於 2)，或者迭代次數 `count` 達到 `max` (此處設定為 256) 。
- 最後，函數回傳 `count`，這個值可以用來決定像素的顏色（例如灰階或彩色）。

---
其他課程連結

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