多核程序設計OpenMP

1、l一種面向共享內(nèi)存以及分布式共享內(nèi)存的多處理器多線程并行編程語言。l一種能夠被用于顯示指導多線程、共享內(nèi)存并行的應用程序編程接口（API）。lOpenMP具有良好的可移植性，支持多種編程語言lOpenMP能夠支持多種平臺，包括大多數(shù)的類UNIX系統(tǒng)以及Windows NT系統(tǒng)（Windows 2000，Windows XP，Windows Vista等）。lOpenMP標準誕生于1997年。 lOpenMP 最初是為共享內(nèi)存的多處理器系統(tǒng)設計的并行編程方法，這種計算機對程序員來說是多個處理器共享同一個內(nèi)存設備，其體系結構如圖所示： lOpenMP 的編程模型以線程為

2、基礎，通過編譯指導語句來顯示地指導并行化，為編程人員提供了對并行化的完整控制。lOpenMP 的執(zhí)行模型采用 Fork-Join 的形式： l派生線程遇到編譯指導語句將派生出另外一組線程MasterThreadParalllRegionNestedParallelRegionlOpenMP同時支持同時支持C/C+語言和Fortran語言，可以選擇任意一種語言以及支持OpenMP的編譯器編寫OpenMP程序。 lOpenMP 的功能由兩種形式功能由兩種形式提供：編譯指導語句編譯指導語句與運行時庫函數(shù)運行時庫函數(shù)，并通過環(huán)境變量環(huán)境變量的方式靈活控制程序的運行。l編譯指導語句提供了將一個串行程序漸

3、進的改造為并行程序的能力，而對于不支持OpenMP編譯指導語句的編譯器，這些編譯指導語句又可以被忽略，完全和原來的串行程序兼容。l運行時庫函數(shù)，則只有在必須的情況下才考慮調(diào)用。 l在編譯器編譯程序的時候，會識別特定的注釋，而這些特定的注釋就包含著OpenMP程序的一些語義。(#pragma omp parallel ).l在一個無法識別OpenMP語意的普通編譯器中，這些特定的注釋會被當作普通的注釋而被忽略。 l在 C/C+程序中，OpenMP 的所有編譯制導語句以#pragma omp開始，后面跟具體的功能指令。即具有如下的形式： #pragma omp clause , clause其中d

4、irective部分就包含了具體的編譯指導語句，包括parallel, for, parallel for, section, sections, single, master, critical, flush, ordered和atomic。將串行的程序逐步地改造成一個并行程序，達到增量更新程序的目的，減少程序編寫人員一定的負擔。lOpenMP運行時函數(shù)庫原本用以設置和獲取執(zhí)行環(huán)境相關的信息，它們當中也包含一系列用以同步的API。l支持運行時對并行環(huán)境的改變和優(yōu)化，給編程人員足夠的靈活性來控制運行時的程序運行狀況。l環(huán)境變量（OMP_NUM_THREADS ）l開發(fā)工具已經(jīng)增加了對OpenM

5、P的支持，Visual Studio 2005完全支持OpemMP 。l編寫OpenMP程序的必要步驟：生成項目；配置項目，支持OpenMP;編寫代碼，加速#include “omp.h”；編寫源程序；配置環(huán)境變量，確定線程的數(shù)目；執(zhí)行程序。 l循環(huán)并行化編譯制導語句的格式，在C/C+語言中，循環(huán)并行化語句的編譯指導語句格式如下：#pragma omp parallel for clauseclause for (index = first ; test_expression ; increment_expr) body of the loop; lparallel關鍵字將緊跟的程序塊擴展為若

6、干完全等同的并行區(qū)域，每個線程擁有完全相同的并行區(qū)域；l關鍵字for則將循環(huán)中的工作分配到線程組中，線程組中的每一個線程完成循環(huán)中的一部分內(nèi)容。 l并行化語句必須是for循環(huán)語句并具有規(guī)范的格式，能夠推測出循環(huán)的次數(shù)，有以下約束 ：循環(huán)語句中的循環(huán)變量必須是有符號整型；循環(huán)語句中的比較操作必須是這樣的形式：loop_variable , 或= loop_invariant_integer；循環(huán)語句中的第三個表達式（for循環(huán)的循環(huán)步長）必須是整數(shù)加或整數(shù)減，加減的數(shù)值必須是一個循環(huán)不變量（loop invariant value）；如果比較操作是或或=，那么循環(huán)變量的值在每次迭代時都必須減少；

7、循環(huán)必須是單入口、單出口的，循環(huán)內(nèi)部不允許有能夠到達循環(huán)之外的跳轉(zhuǎn)語句，也不允許有外部的跳轉(zhuǎn)語句到達循環(huán)內(nèi)部。 l兩個向量相加，并將計算的結果保存到第三個向量中，向量的維數(shù)為n。向量相加即向量的各個分量分別相加。 for（int i=0;in;i+） zi=xi+yi; 存在循環(huán)依賴性實例：for（int i=0;in;i+） zi=zi-1+xi+yil對于向量加法來說，可以使用循環(huán)并行化編譯指導語句直接對循環(huán)進行并行化 ：#pragma omp parallel forfor（int i=0;in;i+） zi=xi+yi; l如果語句S2與語句S1存在數(shù)據(jù)相關，那么必然存在以下兩種情況之

8、一： S1在循環(huán)的一次迭代中訪問存儲單元L，而S2在隨后的一次迭代中訪問同一存儲單元，即：循環(huán)迭代相關 ;S1和S2在同一循環(huán)迭代中訪問同一存儲單元L，但S1的執(zhí)行在S2之前，即：非循環(huán)迭代相關 。 l實例： x0 = 0; y0 = 1; #pragma omp parallel for private(k) for (k = 1; k 100; k+) xk = yk-1 + 1; /S1 yk = xk-1 + 2; /S2 x0 = 0; y0 = 1; x49 = 74;y49 = 74 ;#pragma omp parallel for private(m, k) for (m =

9、 0; m 2; m+) for (k = m*49 + 1; k m*50 + 50; k+) xk = yk-1 + 1; /S1 yk = xk-1 + 2; /S2 l循環(huán)并行化子句可以包含一個或者多個子句來控制循環(huán)并行化的實際執(zhí)行,可以用來控制循環(huán)并行化編譯。 l數(shù)據(jù)的作用域子句用shared來表示一個變量是各個線程之間共享的，而用private來表示一個變量是每一個線程私有的，用 threadprivate表示一個線程私有的全局變量。 l在一個循環(huán)體內(nèi)經(jīng)常會包含另外一個循環(huán)體，循環(huán)產(chǎn)生了嵌套 。l循環(huán)并行化編譯制導語句可以加在任意一個循環(huán)之前，則對應的最近的循環(huán)語句被并行化，其它部

10、分保持不變。l實際上并行化是作用于嵌套循環(huán)中的某一個循環(huán)，其它部分由執(zhí)行到的線程負責執(zhí)行。 #include stdafx.h#include omp.hint _tmain(int argc, _TCHAR* argv)int i;int j; #pragma omp parallel for /#pragma omp parallel for private(j)for(i=0;i4;i+) for(j=6;j10;j+)printf(i=%d j=%dn,i,j);printf(#n);for(i=0;i4;i+) #pragma omp parallel for for(j=6;j10

11、;j+)printf(i=%d j=%dn,i,j);return 0;lOpenMP 程序在同一個共享內(nèi)存空間上執(zhí)行，線程通信容易，一個線程寫入一個變量，另一個線程可以讀取這個變量來完成線程間的通信。 l全局變量以及程序代碼都是全局共享的；而動態(tài)分配的堆空間也是共享的。l通過threadprivate來明確指出的某一個數(shù)據(jù)結構屬于線程范圍的全局變量。 lOpenMP 允許線程保留自己的私有變量不能讓其它線程訪問到。每一個線程會建立變量的私有拷貝，雖然變量名是相同的，實際上在共享內(nèi)存空間內(nèi)部的位置是不同的。 l數(shù)據(jù)作用域子句用來確定數(shù)據(jù)的共享屬性，有下面以下幾個子句 ：shared用來指示一個

12、變量的作用域是共享的；private用來指示一個變量作用域是私有的；firstprivate 和 lastprivate 分別對私有的變量進行初始化的操作和最后終結的操作，firstprivate 將串行的變量值拷貝到同名的私有變量中，在每一個線程開始執(zhí)行的時候初始化一次。而lastprivate則將并行執(zhí)行中的最后一次循環(huán)的私有變量值拷貝的同名的串行變量中；default語句用來改變變量的默認私有屬性。 l在使用作用域子句的時候要遵循如下的一些規(guī)則 ：作用域子句作用的變量是已經(jīng)申明的有名變量；作用域子句在作用到類或者結構的時候，必須作用到類或者結構的整體，而不能只作用于類或者結構的一個部分；

13、一個編譯指導語句能夠包含多個數(shù)據(jù)作用域子句，但是變量只能出現(xiàn)在一個作用域子句中，即變量不能既是共享的，又是私有的；在語法結構上，作用域子句只能作用在出現(xiàn)在編譯指導語句起作用的語句變量部分。另外，可以將作用域子句作用在類的靜態(tài)變量上。lOpenMP 對默認情況下，并行區(qū)中所有的變量都是共享的，但有三種例外情況：在parallel for循環(huán)中，循環(huán)索引變量循環(huán)索引變量是私有的；那些并行區(qū)中的局部變量是私有的；所有在private，firstprivate，lastprivate或reduction子句中列出的變量都是私有的。私有化是通過為每個線程創(chuàng)建各個變量的獨立副本來完成的。l常見的規(guī)約操作數(shù)

14、組求和 # pragma omp parallel for private（arx,ary,n） reduction（+:a,b） for（i=0;in;i+） a=a+arxi; b=b+aryi; 運算符運算符數(shù)據(jù)類型數(shù)據(jù)類型默認初始值默認初始值+整數(shù)，浮點0*整數(shù)，浮點1-整數(shù)，浮點0&整數(shù)所有位都開啟，0|整數(shù)0整數(shù)0&整數(shù)1|整數(shù)0l使用reduction子句進行多線程程序設計時，要記住以下三個要點： 在第一個線程到達指定了reduction子句的共享區(qū)域或循環(huán)末尾時，原來的規(guī)約變量的值變?yōu)椴淮_定，并保持此不確定狀態(tài)直至規(guī)約計算完成 ;如果在一個循環(huán)中使用到了redu

15、ction子句，同時又使用了nowait子句，那么在確保所有線程完成規(guī)約計算的柵欄同步操作前，原來的規(guī)約變量的值將一直保持不確定的狀態(tài);各個線程的私有副本值被規(guī)約的順序是未指定的。因此，對于同一段程序的一次串行執(zhí)行和一次并行執(zhí)行，甚至兩次并行執(zhí)行來說，都無法保證得到完全相同的結果（這主要針對浮點計算而言），也無法保證計算過程中諸如浮點計算異常這樣的行為會完全相同。l開始時訪問到私有變量在主線程中的同名變量的值，也有可能需要將循環(huán)并行化最后一次循環(huán)的變量結果返回給主線程中的同名的變量。lOpenMP 編譯指導語句使用firstprivate和 lastprivate對這兩種需求進行支持，使得循環(huán)

16、并行開始執(zhí)行的時候私有變量通過主線程中的變量初始化，同時循環(huán)并行結束的時候，將最后一次循環(huán)的相應變量賦值給主線程的變量。l程序?qū)嵗?l并不是所有的循環(huán)都能夠使用#pragma omp parallel for 來進行并行化。為了對一個循環(huán)進行并行化操作，我們必須要保證數(shù)據(jù)兩次循環(huán)之間不存在數(shù)據(jù)相關性。l數(shù)據(jù)競爭當兩個線程對同一個變量進行操作，并且有一個操作為寫操作的時候，就說明這兩個線程存在數(shù)據(jù)競爭，此時，讀出的數(shù)據(jù)不一定就是前一次寫操作的數(shù)據(jù)，而寫入的數(shù)據(jù)也可能并不是程序所需要的。 for（int i=0;i99;i+） ai=ai+ai+1; l具有循環(huán)之間數(shù)據(jù)相關性的串行程序 for（

17、int j=1;jN;j+） for（int i=0;iN;i+） ai,j=ai,j+ai,j-1; l具有循環(huán)之間數(shù)據(jù)相關性的并行程序for（int j=1;jN;j+） #pragma omp parallel for for（int i=0;iN;i+） ai,j=ai,j+ai,j-1;l并行區(qū)域就是通過循環(huán)并行化編譯指導語句使得一段代碼能夠在多個線程內(nèi)部同時執(zhí)行。 l并行區(qū)域編譯指導語句的格式：#pragma omp parallel clauseclause blocklparallel編譯指導語句的執(zhí)行過程#pragma omp parallel for（int i=0;i5;

18、i+） printf（hello world i=%dn,i）; #pragma omp parallel for for（int i=0;i5;i+） printf（hello world i=%dn,i）; l使用threadprivate子句用來標明某一個變量是線程私有數(shù)據(jù)，在程序運行的過程中，不能夠被其他線程訪問到。l使用copyin子句對線程私有的全局變量進行初始化。int counter=0;#pragma omp threadprivate(counter)void inc_counter()counter+;int _tmain(int argc, _TCHAR* argv)#

19、pragma omp parallelfor(int i=0;i10000;i+)inc_counter();printf(counter=%dn,counter);return 0;l工作隊列：基本工作過程即為維持一個工作的隊列，線程在并行執(zhí)行的時候，不斷從這個隊列中取出相應的工作完成，直到隊列為空為止。int next_task=0; int get_next_task() int task; #pragma omp criticalif(next_task8) task=next_task; next_task+; else task=-1; return task; void task

20、_queue（） int my_task; #pragma omp parallel private（my_task） my_task=get_next_task（）; while（my_task!=-1） get_task_done（my_task）; my_task=get_next_task（）; l根據(jù)線程號分配任務：由于每一個線程在執(zhí)行的過程中的線程標識號是不同的，可以根據(jù)這個線程標識號來分配不同的任務。#pragma omp parallel private（myid） nthreads=omp_get_num_threads（）; myid=omp_get_thread_num（

21、）; get_my_work_done（myid,nthreads）; l使用循環(huán)語句分配任務int _tmain(int argc, _TCHAR* argv)int i;#pragma omp parallel /開始并行執(zhí)行printf(outside loop thread=%dn,omp_get_thread_num();#pragma omp for for(i=0;imax_num，需max_num=ar0。此時，系統(tǒng)將線程1掛起。線程2繼續(xù)，發(fā)現(xiàn)ar1max_num ，結果max_num=3，線程2完成。線程1被喚醒，使得max_num=ar0 。執(zhí)行的結果與串行結果完全不同。

22、 int i; int max_num=-1; for（i=0;imax_num） max_num=ari; int i; int max_num=-1; #pragma omp parallel for for（i=0;imax_num） max_num=ari;lOpenMP提供三種不同的互斥鎖機制：臨界區(qū)（critical）原子操作（atomic）由庫函數(shù)來提供同步操作l臨界區(qū)通過編譯指導語句對產(chǎn)生數(shù)據(jù)競爭的內(nèi)存變量進行保護。臨界區(qū)編譯指導語句的格式如下所示： #pragma omp critical （name） block 執(zhí)行程序塊block之前，首先要獲得臨界區(qū)的控制權。在線程組

23、執(zhí)行的時候，保證每次最多只有一個線程執(zhí)行臨界區(qū)。name 是一個臨界區(qū)的屬性，臨界區(qū)的命名操作。l修改尋找正整數(shù)數(shù)組最大的元素的代碼int i; int max_num_x=max_num_y=-1; #pragma omp parallel for for（i=0;imax_num_x） max_num_x=arxi; #pragma omp critical （max_ary） if（aryimax_num_y） max_num_y=aryi; l原子操作OpenMP編程方式給同步編程帶來的特殊的編程功能；通過編譯指導語句的方式直接獲取了現(xiàn)在多處理器計算機體系結構的功能；操作在執(zhí)行的過程中

24、是不會被打斷的。能夠完成對單一內(nèi)存單元的更新，提供一種更高效率的互斥鎖機制。通過#pragma omp atomic 編譯指導語句提供；只能作用在語言內(nèi)建的基本數(shù)據(jù)結構，語法格式如下所示：#pragma omp atomic x =expr #pragma omp atomic x+/or x-, -x, +x l在C/C+語言中可能的原子操作 ：“+ * - / & | ”l注意：當對一個數(shù)據(jù)進行原子操作保護的時候，就不能對數(shù)據(jù)進行臨界區(qū)的保護；在針對同一個內(nèi)存單元使用原子操作的時候需要在程序的所有涉及到的部位都加入原子操作的支持。l運行時庫函數(shù)的互斥鎖支持OpenMP通過一系列的庫

25、函數(shù)支持更加細致的互斥鎖操作 ；編譯指導語句進行的互斥鎖支持只能放置在一段代碼之前，作用在這段代碼之上；程序員必須自己保證在調(diào)用相應鎖操作之后釋放相應的鎖，否則就會造成多線程程序的死鎖。函數(shù)名稱描述void omp_init_lock（omp_lock_t *）初始化一個互斥鎖void omp_destroy_lock（omp_lock_t*）結束一個互斥鎖的使用并釋放內(nèi)存void omp_set_lock（omp_lock_t *）獲得一個互斥鎖void omp_unset_lock（omp_lock_t *）釋放一個互斥鎖int omp_test_lock（omp_lock_t *）試圖獲

26、得一個互斥鎖，并在成功是返回真（true），失敗是返回假（false）l在每一個并行區(qū)域都會有一個隱含的同步屏障（barrier），執(zhí)行此并行區(qū)域的線程組在執(zhí)行完畢本區(qū)域代碼之前，都需要同步并行區(qū)域的所有線程；l一個同步屏障要求所有的線程執(zhí)行到此屏障，然后才能夠繼續(xù)執(zhí)行下面的代碼；l#pragma omp for，#pragma omp single， #pragma omp sections 程序塊都包含自己的隱含的同步屏障；l為了避免在循環(huán)過程中不必要的同步屏障，可以增加nowait子句到相應的編譯指導語句中。 l在有些情況下，隱含的同步屏障并不能提供有效的同步措施，可以在需要的地方插入明確的同步屏障語句#pragma omp barrier。此時，所有的執(zhí)行線程都會在同步屏障語句上進行同步。#pragma omp parallel ini