平行程式 10A~10B Synchronization Tools & Open Multi-Processing(OpenMP)Synchronization Construct

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