OpenMP 心得 (二) 基本知識與常見術語

在介紹 OpenMP 的用法前，我們先來瞭解一些相關的基本知識與術語，讓讀者可以對 OpenMP 建立起一個大略的圖像以及統一一些專有名詞，這對之後的學習與討論都會有相當的幫助。有關專門術語的中文翻譯部分，翻得不好不如不翻，所以除非是使用上已經比較有共識的名詞外，其它術語我個人是傾向不翻譯而直接使用原文，然後試著在它們第一次出現時再加以說明。

Process、Thread、Multi-processing、Multi-threading
首先來談什麼是「程序」 (process)。我們知道當一個程式在電腦執行時它會先向系統進行註冊，讓系統將這個程式記錄在它的執行清單上並分配適當的資源給這個程式來進行工作，這些資源包含 CPU 的使用權以及獨立的資料儲存空間，我們稱此動作為建立一個處理程序 (process)。系統為了管理方便會為每一個程序都標上一個唯一的 ID 以作為區別，即 PID (Process ID)，每個程序所擁有的資源在執行期間是獨佔的，不與其它程序共用，像是系統會在記憶體中為每個程序切割出需要的空間大小來儲存各個程序的資料，但每個程序只能存取屬於自己的部份而不能直接去更改其它程序的資料，如果程序間需要彼此交流則必須先建立通訊的管道才能交換情報。另外，因為 CPU 的數目有限而待執行的程序可能有很多個，因此系統會為每個程序規劃出一段 CPU 使用時間，在這段時間內分配給這個程序的 CPU(s) 就專屬於該程序而不會去處理其它程序的工作。

再來介紹什麼是「執行緒」(thread)。執行緒是系統處理工作的基本單元，通常一個 CPU 處理核心在同一時間只能提供一個執行緒 (在此不討論 Hyper-Threading 技術) 讓系統調用去執行程式。程序跟執行緒間的關係我們可以把它想像成是工廠與員工的關係，工廠擁有資源與設備但需要由員工去操作才能生產產品。所以要做出一件成品，則工廠內至少要有一位員工在做事。以電腦分時運作架構來看，不同的程序就像是不同的工廠，而執行緒則像是一位派遣員工一樣由作業系統負責調度他在什麼時間該去那家工廠上班。如果電腦擁有多個處理核心，即代表系統可以同時調用的員工數目增加，所謂人多好辦事，如此一來系統在為執行緒安排工作時就有兩種策略可以運用：第一種策略是在同一時間內為各家工廠都分配一個員工去作事，這種方式稱作多程序 (multi-processing) 平行執行。跟單一程序處理比起來，其優點在於可以在相同的時間內完成較多的工作；另一種策略是在同一時間內把所有員工都派到同一家工廠去工作，此法稱做多執行緒 (multi-threading) 平行執行。相較於單一執行緒處理方式，它有機會讓相同的工作在比較短的時間內完成。

多執行緒工作的其中一項特點就是隸屬在同一程序下的所有執行緒會分享該程序的所有資源，此外各執行緒彼此間也可以擁有自己私有的資源而不與其它同一程序內的執行緒共用。這就像是工廠內的公共設備是所有員工可以自由使用一樣，但每個員工也都會有自己的工作空間與置物櫃可以擺放自己私人的物品，其他員工不能隨意侵犯他人的私有領域。

從以上說明可以歸結幾點：

• 擁有多處理核心的電腦系統可以同時平行處理多項程序或將單一程序平行處理。
• 一個程序被執行時至少要有一個執行緒，但也可同時擁有多個執行緒來進行處理。
• 程序間的資源是彼此獨立不共用的，但是在同一程序下的所有執行緒分享該程序的所有資源。
• 同一程序下的執行緒之間也能夠擁有彼此獨立的資源。

Shared Memory
在第一篇文章中有提到 OpenMP 是用在 shared memory 架構的平行程式 API，但是 shared memory 指的是什麼？Shared memory 簡單講是指多個處理單元共享同一塊記憶體區塊，在該記憶體區塊內的資料可以被這些處理單元自由存取。從前一節討論中我們已經知道系統會為程序分配資源，其中的資源就包括用來儲存變數資料的記憶體空間，如果該程序擁有多個執行緒，則此程序就成為一個符合在 shared memory 架構下執行的程序。由此可見 multi-threading 的平行方式是應用在 shared memory 架構的平臺上，而 OpenMP 的平行方式正是採用 multi-threading。因為在 shared memory 架構下所有的處理單元都可共用同一個記憶體區塊，所以可能會發生多個處理單元同時都在存取記憶體中同一筆資料的情況，一不小心就會造成資料使用與更新不一致的問題，這個問題有個專有名稱叫 race condition。在寫多執行緒程式時我們必須對這個問題多加留意，一般是想辦法讓程式在同一時間內只能由一個執行緒來更新變數資料，以避免 race condition 的發生。

Fork-join Model
OpenMP 使用 Fork-join model 來對程式進行平行化：

從上圖可以看出此模式分成兩個區域：序列執行區 (serial region) 與平行執行區 (parallel region)。程式在序列執行區是由一個執行緒來處理工作 (圖中一支箭條線代表一個執行諸)，這個執行緒也稱作程式的主執行緒 (master thread)；而在平行執行區則是由多個執行緒來處理工作，其中也包含原本的主執行緒 (藍色的箭條線)。從 serial region 進入到 parallel region 時會經歷一個叫 fork 的步驟，在這個步驟中系統會依 OpenMP 程式的設計來派生出需要的執行緒數目以協助主執行緒平行處理接下來的工作。這些派生的執行緒可以視作程式的副執行緒，與原本的主執行緒組成一個團隊 (team) 在平行區一起工作，待需要平行處理的工作完成後，系統會釋出多餘的執行緒只留下主執行緒繼續進行未完成的任務，這個步驟即為圖中的 join 部份。使用 OpenMP 平行化程式的過程簡單講就是在程式中找出需要平行化的程式區塊，然後在這個區塊加上適當的 OpenMP directive 讓編譯器在編譯執行檔時將這個區塊設定為平行執行。

OpenMP Construct
OpenMP construct 是指程式中受到 OpenMP directive 影響的程式區塊，一個 construct 內可以包含其它 OpenMP constructs。Construct 按照其用途與工作型態可以分成三個群組：

• Parallel Construct
• Work-Sharing Constructs
• Synchronization Constructs

Parallel construct 是 OpenMP 最基本且最重要的 construct，只有在 parallel construct 內的程式才會被平行執行。建立 parallel construct 的 OpenMP directive 只有一個，就是 parallel directive，當編譯器遇到 parallel directive 時就會進行 fork 的步驟以派生執行緒，然後在 parallel construct 結束點進行 join 以結束平行處理。所以 parallel construct 的主要作用可以說是產生新的執行緒，而其它的 OpenMP constructs 並無新增執行緒的能力，因此它們在使用上必須被包含在 parallel construct 內，然後運用由 parallel directive 產生出來的多執行緒進行平行化的工作。

Work-sharing constructs 是我們對程式平行化的真正意圖。一般程式需要平行執行的部分大多是需要大量重覆計算的迴圈結構，或者是數個彼此間獨立且可不依順序執行的任務，work-sharing constructs 的 loop construct 與 sections construct 就是分別用來平行化迴圈結構與獨立任務的 constructs。其它屬於 work-sharing constructs 的還有 single construct、與 workshare construct。

Synchronization constructs 是用來控制執行緒彼此間的進程。需要這麼做的原因有幾個：第一個是因為為了平行執行程式所分割的工作其大小可能是不相等的，有的分到比較多的工作量而有的比較少，因此在平行執行時會有先完成工作的執行緒與較晚完成工作的執行緒。基本上這些執行緒是不會互相等待地，當它們處理完負責的工作部分後會繼續進行下一項分配到的任務。不過我們有時候會希望先完成工作的執行緒能夠停下來等候其它的執行緒，待所有執行緒都完成相同的工作後再一同進行下一項任務，此時我們可以使用 barrier construct 來達成這個需求；第二個原因是為了避免 race condition 的發生，因為程式在平行執行的階段可能會有二個以上的執行緒同時去存取同一個共享變數資料的情況，這會造成運算上或變數賦值上的錯誤。解決的方法之一就是使用 critical construct 讓共享變數在同一時間內只能由一個執行緒去更新它的資料，而其它執行緒必須等到前一個執行緒完成動作後再依序去存取該變數。剩下屬於 synchronization constructs 的還有 ordered construct、atomic construct、以及 master construct，這些 synchronization constructs 提供其它常用的功能讓程式設計人員可以依需要來選用。

Directive 的作用範圍
程式中受到 OpenMP directive 影響的範圍是緊接在 directive 宣告之後的單一程式敘述或者是可區別的程式結構，這些結構必須具有單一的進入點與結束點。在 C/C++ 程式中，可區別的程式結構指的是像 for 迴圈結構、或是由一對大括號 { } 所框出的程式區塊，例如
        #pragma omp directive
       {
            statement
            ...
        }
而在 Fortran 程式中，大部份的 OpenMP directive 語法都會有相對應的 end 敘述來指明其作用的範圍，例如
        !$OMP DIRECTIVE
               statement
               ...
        !$OMP END DIRECTIVE
不過有些 directive 是沒有所謂的作用範圍，像是 barrier directive 的作用是集結執行緒，以同步它們的執行速度，因此比較像是一個程式執行上的暫停點，而非影響某行程式敘述或區塊的執行方式。

小結
本篇文章介紹了 OpenMP 的運作模型以及相關的知識與術語。有了這些基礎知識後接下來就可以開始介紹 OpenMP API 的實際用法。

(發佈日期：2011/03/25 by AAZ)