多執行緒簡介

不同的應用程式，在作業系統中是以處理序 (Process) 做為分隔，讓不同的應用程式間不會相互干擾，我們從 Windows 工作管理員可以看到幾個頁籤，其中「應用程式」頁是指有視窗的應用程式，「處理程序」頁則列出所有正在執行的處理序。執行緒 (Thread) 是作業系統分配處理器 (CPU) 時間的基本單元，也就是當應用程式在執行時是經由執行緒向作業系統申請處理器的使用權。因為同一時間一個處理器只能給一個執行緒使用，作業系統中所有正在執行的處理序所建立的所有執行緒需要使用處理器時，會在一個佇列中等候作業系統分配可用的處理器時間，當執行緒使用處理器的時間量超過限額時就會暫止，由 佇列中下一個執行緒繼續使用。每段時間量的長度視作業系統和處理器而定，由於這是一個極短的時間，例如每一個執行緒使用10毫秒，1秒鐘就會有100個執 行緒次被執行，因此即使只有一個處理器，看起來就像多個執行緒同時在執行一樣，但終究和多工有所不同，多工是指不管把時間細分到多小都還是同時執行。執行 緒的內容包含其主處理序的位址空間中能順利繼續執行所需的所有資訊，包括一組 CPU 暫存器和堆疊。每個執行緒會維護例外處理常式 (Exception Handler)、排程優先權，以及系統用來在執行緒排程之前儲存其內容的一組結構。

多核心與程式開發簡介

曾經每年都在急速成長的 CPU 處理速度，已經停留在 2 至 3G MHz 很久的一段時間，在個人電腦的硬體配備中，已經由追求 CPU 的速度提升，轉向追求核心數量的增加。主流的 CPU 規格也逐漸由雙核心進步到四核心、六核心，甚至是未來的八核心中央處理器。「多核心」聽起來很酷，對於程式設計者，甚至是專案的執行者來說，認識多核心的運用潛力，並且學習如何使用相關的技術，。而為了正確應用多核心的程式開發技術，有三項關鍵概念須知道：

◎可擴展性 (Scalability)：擴展的目的並不是為了使用 8 個核心以獲取 8 倍的效能，我們需要的是維持程式系統的可擴展性，不將程式的多緒架構寫死，限定只能在雙核或是四核的硬體系統中執行， 而是要能夠使程式系統不論在多少核心的情況下都能夠正常運作，並且同時獲得執行效能上的提升。

◎正確性 (Correctness)：防止競賽條件 (Race Condition) 與鎖死 (Deadlock) 狀況的產生，並且確認你的多緒程式系統，能夠在單緒的環境下得到正確的執行結果，對於專案的後 續測試、除錯與維護程序，將會有非常大的助益與影響。

◎可維護性 (Maintainability)：為了因應不斷快速成長與變化的多緒程式設計技術發展，程式設 計者要避免直接使用低階或原始的程式模組如 pthread 或 Windows 執行緒，而應該利用各項高階的抽象化工具與函式庫， 例如：OpenMP、MPI、執行緒結構模組 (Threading Building Blocks)，才能夠達到良好的可維護性以及跨平台能力。

OpenMP簡介

寫程式的時大部分都怎麼去寫多執行緒的程式？一般的方法，程式設計師必須自己操作 thread 的控制，實際在程式中去產生其他的 thread 來處理。像 POSIX Threads 這套 library，就是用來產生、控制執行緒的函式庫。而像 Microsoft VisualStudio 2005 中，也有提供控制 thread 的功能。這種方法，大多就是產生多個 thread，而再由主要的 thread 把工作拆開，分給各 thread 去運算，最後再由主要的 thread 回收結果、整合。 但是，實際上要去控制 thread ，程式設計師必須很麻煩的在程式的編寫上，也會複雜不少；而如果只是想要把一些簡單的迴圈平行化處理，用 thread library 來控制，實在大材小用的感覺。這時候，用 Open MP 就比較簡單，OpenMP 是一種能透過高階指令，很簡單地將程式平行化、多執行緒化的 API；在最簡單的情形，甚至可以只加一行指令，就可以將迴圈內的程式平行化處理！

OpenMP是由OpenMP Architecture Review Board提出的，並已被廣泛接受的，用於共享內存平行處理系統的多執行緒程式設計的一套指導性註釋（Compiler Directive）。OpenMP支持的程式語言包括C 語言、C++和Fortran； 而支持OpenMP的編譯器包括Sun Studio和Intel Compiler，以及開放程式碼的GCC和Open64編譯器。OpenMP提供了對平行演算法的高層的抽象描述，程式設計師通過在程式碼中加入專用的pragma來指明自己的意圖，由此編譯器可以自動將程式進行平行處理化，並在必要之處加入同步互斥以及通信。當選擇忽略這些pragma，或者編譯器不支持OpenMP時，程式又可退化為通常的程式（一般為串行），程式碼仍然可以正常運作，只是不能利用多執行緒來加速Process執行。

OpenMP用法

在此以 Microsoft Visual C++ 2005為例子，使用 OpenMP 只要將 Project選項中 的 Properties ， C/C++ 裡 Language 的 OpenMP Support 開啟（參數為 /openmp），就可以讓 Microsoft Visual C++ 2005 在編譯時可以支援 OpenMP 的語法；而在使用到 OpenMP 的檔案，則需要先 include OpenMP 的 header file : omp.h。當要對For迴圈作平行化處理的時候只需要在For迴圈前面加上一行



在此附上簡單的程式碼範例，比較使用OpenMP前後的結果:



在 main() 是一個很簡單的迴圈，跑十次，每次都會呼叫 Test() 這個function，並且把是迴圈的執行次數（i）傳進 Test() 並且列印出來。它的結果會是：



當使用OpenMP 把 mian() 裡面For的迴圈平行化處理，只需要修改成下面的樣子：



可以從結果很明顯的發現，結果沒有照著 0 到 9 的順序跑了，而結果輸出順序其實很簡單，OpenMP 只是把迴圈 0 - 9 共十個步驟，拆成 0 - 4, 5 - 9 兩部份，丟給不同的執行緒去跑，所以數字才會交錯的輸出。

OpenMP語法說明

OpenMP分為三類：Directives、Clauses、Functions。

directive 和 clause 的用法，大致上應該是：



而 #pragma omp parallel for，實際上 parallel 和 for 都是 directive；所以語法實際上可以拆開成 #pragma omp parallel 和 #pragma omp for 兩行。也就是



實際上是



在此列出directive 和 clause 有哪些可以使用:

一、Directive



其中，要做平行處理的部份是使用 parallel、sections、for 這三項；而要指定使用單一執行緒，則是透過 master、single、crigical 這三項。barrier 則是拿來控制執行緒同步使用；ordered 是用來設定平行處理的執行順序。atomic、flush、threadprivate 則都是用來控制變數使用。

二、Clause



在 clause 裡面，copyin、copyprivate、default、shared、private、firstprivate、lastprivate、reduction 這 8 項，都是用來控制變數在平行化處理時的處理方法。ordered 和 schedule 是控制平行處理化時候的執行順序分配方法；num_threads、if 則是控制執行緒的設定。而Function的部份在MSDN中有列出可以到MSDN的網站查詢。

OpenMP不能平行處理之情形

先前所提到的OpenMP都可以做平行處理化，並且有許多方式可以提供程式設計師做多執行緒開發，但有種情況是OpenMP平行處理後會得到錯誤的結果，那就是平行處理化後的執行緒之間變數有先後使用的串連，例子如下：



而執行輸出結果就是 0,1,1,2,3,5,8,13,21,34。 不過如直接的透過 OpenMP 作平行處理化後，程式變成



在此跑出來的範例結果會變成0,1,1,2,3,5,-1823049,-1878930,-4,-1717986912。 輸出錯誤的原因是由於在計算 FList[6] 的時候，計算 FList [5] 和 FList [4] 的 thread 還沒有完成，因此會導致計算的結果不正確；而每次跑出來的結果不一定會一樣，取決於各 thread 的計算速度。所以這類型各執行緒間會使用到被其他執行緒Write的變數，就不適合用來平行處理化。

結論

OpenMP提供的這種對於平行演算的高層抽象降低了平行處理程式的難度和複雜度，這樣程式開發工程師可以把更多的精力投入到平行處理演算法的本身，而不是程式具體實現細節。對基於數據分集的多執行緒的程式設計，OpenMP是一個很好的選擇。同時，使用OpenMP也提供了更強的靈活性，可以較容易的適應不同的平行開發系統配置。線程粒度和負載平衡等是傳統多執行緒程式設計中的難題，但在OpenMP中，OpenMP程式庫從程序員手中接管了部分這兩方面的工作。OpenMP也有缺點，OpenMP不適合需要複雜的線程間同步和互斥的情形。 OpenMP的另一個缺點是不能在非共享內存系統（如clusters computer）上使用。在這樣的系統上，MPI使用較多。

參考資料

http://openmp.org/wp/
http://msdn.microsoft.com/en-us/library/tt15eb9t.aspx
http://msdn2.microsoft.com/zh-tw/library/fw509c3b.aspx
http://software.intel.com/en-us/intel-compilers/
https://computing.llnl.gov/tutorials/openMP/
Michael J. Quinn, Parallel Programming in C with MPI and OpenMP, International Edition 2003, McGraw-Hill, ISBN: 007-123265-6.