OpenMP
OpenMP（Open Multi-Processing）是一套支援跨平台共享記憶體方式的多執行緒並行的編程API，使用C,C++和Fortran語言，可以在大多數的處理器體系和作業系統中執行，目前最新的版本為4.5((Nov. 2015)。
OpenMP使用特殊形式的前置敘述或註解，來指導編譯器將特定的程式區塊變成平行執行，使用者幾乎不用修改程式本身架構即能完成程式的平行化，目前大部分的C/C++編譯器都能支援OpenMP，只要在編譯程式時加入OpenMP的選項，即會在編譯過程中將特定程式區塊進行平行化。
OpenMP提供的這種對於並列描述的高層抽象降低了並列編程的難度和複雜度，這樣程式設計師可以把更多的精力投入到並列演算法本身，而非其具體實作細節。對基於資料分集的多執行緒程式設計，OpenMP是一個很好的選擇。
由於我的工作比較偏向利用多核心計算(shared memory)，因此使用pthread或是tbb分散計算過反而過於複雜，OpenMP較為適合。
shared memory架構
shared memory簡單講是指多個處理單元共享同一塊記憶體區塊，這些處理單元可自由存取此記憶體的資料，如果某個程序擁有多個執行緒，則這些執行緒可以共享此程序的資源，則此程序就成為一個符合在shared memory架構下執行的程序，而OpenMP的平行方式正是採用多執行緒。
上圖將程式分成兩個區域：序列執行區(serial region)與平行執行區(parallel region)，序列執行區由一個執行緒來處理工作(圖中一支箭條線代表一個執行諸)，這個執行緒也稱作程式的主執行緒(master thread)，而在平行執行區則是由多個執行緒來處理工作，其中也包含原本的主執行緒。從序列區進入到平行區時會經歷一個叫fork的步驟，在這個步驟中系統會依OpenMP的設計，派生出需要的執行緒以協助平行處理接下來的工作，待需要平行處理的工作完成後，系統會釋放多餘的執行緒，只留下主執行緒繼續進行未完成的任務，這個步驟即為圖中的 join 部份，使用OpenMP簡單講就是在程式中找出需要平行化的程式區塊，然後在這個區塊加上適當的OpenMP directive，讓編譯器在編譯時將這個區塊設定為平行執行。
OpenMP Directive
程式中受到OpenMP影響的範圍是緊接在directive宣告之後的程式結構，這些結構必須具有單一的進入點與結束點，在C/C++程式中，是指像函式括號{ }內部的範圍，例如：
#pragma omp directive [clause[[,] clause] ...]
{
statement
...
}
其中，directive共11個：
- atomic 記憶體位置將會原子更新（Specifies that a memory location that will be updated atomically.）
- barrier 執行緒在此等待，直到所有的執行緒都執行到此barrier。用來同步所有執行緒。
- critical 其後的代碼塊為臨界區，任意時刻只能被一個執行緒執行。
- flush 所有執行緒對所有共享物件具有相同的記憶體視圖（view of memory）
- for 用在for迴圈之前，把for迴圈並列化由多個執行緒執行。迴圈變數只能是整型
- master 指定由主執行緒來執行接下來的程式。
- ordered 指定在接下來的代碼塊中，被並列化的 for迴圈將依序執行（sequential loop）
- parallel 代表接下來的代碼塊將被多個執行緒並列各執行一遍。
- sections 將接下來的代碼塊包含將被並列執行的section塊。
- single 之後的程式將只會在一個執行緒（未必是主執行緒）中被執行，不會被並列執行。
- threadprivate 指定一個變數是執行緒局部儲存（thread local storage）
OpenMP Construct
OpenMP construct是指程式中受到OpenMP directive影響的程式區塊，按照其用途與工作型態可以分成三個群組：
- Parallel Construct
- Work-Sharing Constructs
- Synchronization Constructs
parallel construct是OpenMP最基本的construct，只有在parallel construct內的程式才會被平行執行，用parallel directive產生parallel construct，當編譯器遇到parallel directive時，會進行fork的步驟以派生執行緒，然後在parallel construct結束點進行join結束平行處理。parallel construct是唯一能產生新執行緒的construct，因此其他construct必須被包含在parallel construct內，然後運用由parallel directive產生出來的多執行緒進行平行化的工作。
work-sharing constructs是我們對程式平行化的方式，可分為loop construct、sections construct、single construct與master construct等。一般需要平行執行的部分，為需要大量重覆計算的迴圈結構，或者是數個彼此獨立且順序無關的任務，loop construct用來平行化迴圈結構，sections construct用來平行化獨立任務。
synchronization constructs是用來控制執行緒彼此間的進程，由於平行化所分割的工作其大小可能是不相等的，基本上這些執行緒不會互相等待，當它們處理完負責的工作部分後，會繼續進行下一項分配到的任務，有時我們希望先完成工作的執行緒能夠停下來等候其它的執行緒，待所有執行緒都完成相同的工作後再一同進行下一項任務，此時我們可以使用barrier construct來達成這個需求。另外在平行執行的階段可能會有二個以上的執行緒，同時去存取同一個共享變數資料的情況，會造成運算上或變數賦值上的錯誤，可以使用critical construct讓共享變數在同一時間內只能由一個執行緒去更新它的資料，而其它執行緒必須等到前一個執行緒完成動作後再依序去存取該變數。