第一章操作系統(tǒng)概述

1、OpenMP編程簡介,一種面向共享內(nèi)存以及分布式共享內(nèi)存的多處理器多線程并行編程語言。一種能夠被用于顯示指導(dǎo)多線程、共享內(nèi)存并行的應(yīng)用程序編程接口（API）。OpenMP具有良好的可移植性，支持多種編程語言O(shè)penMP能夠支持多種平臺，包括大多數(shù)的類UNIX系統(tǒng)以及Windows NT系統(tǒng)（Windows 2000，Windows XP，Windows Vista等）。OpenMP標(biāo)準(zhǔn)誕生于1997年。www.openmp.or

2、g,OpenMP編程簡介,OpenMP 最初是為共享內(nèi)存的多處理器系統(tǒng)設(shè)計的并行編程方法，這種計算機對程序員來說是多個處理器共享同一個內(nèi)存設(shè)備，其體系結(jié)構(gòu)如圖所示：,OpenMP多線程編程基礎(chǔ),OpenMP 的編程模型以線程為基礎(chǔ)，通過編譯指導(dǎo)語句來顯示地指導(dǎo)并行化，為編程人員提供了對并行化的完整控制。OpenMP 的執(zhí)行模型采用 Fork-Join 的形式：,Fork-Join的形式,派生線程遇到編譯指導(dǎo)語句將派生出另外一組線程,O

3、penMP編程組成,OpenMP同時支持C/C++語言和Fortran語言，可以選擇任意一種語言以及支持OpenMP的編譯器編寫OpenMP程序。 OpenMP 的功能由兩種形式提供：編譯指導(dǎo)語句與運行時庫函數(shù)，并通過環(huán)境變量的方式靈活控制程序的運行。編譯指導(dǎo)語句提供了將一個串行程序漸進的改造為并行程序的能力，而對于不支持OpenMP編譯指導(dǎo)語句的編譯器，這些編譯指導(dǎo)語句又可以被忽略，完全和原來的串行程序兼容。運行時庫函數(shù)，則只有

4、在必須的情況下才考慮調(diào)用。,編譯指導(dǎo)語句,在編譯器編譯程序的時候，會識別特定的注釋，而這些特定的注釋就包含著OpenMP程序的一些語義。(#pragma omp parallel ).在一個無法識別OpenMP語意的普通編譯器中，這些特定的注釋會被當(dāng)作普通的注釋而被忽略。 在 C/C++程序中，OpenMP 的所有編譯制導(dǎo)語句以#pragma omp開始，后面跟具體的功能指令。即具有如下的形式： #pragma omp [cla

5、use[ [,] clause]…]其中directive部分就包含了具體的編譯指導(dǎo)語句，包括parallel, for, parallel for, section, sections, single, master, critical, flush, ordered和atomic。將串行的程序逐步地改造成一個并行程序，達到增量更新程序的目的，減少程序編寫人員一定的負擔(dān)。,運行時庫函數(shù),OpenMP運行時函數(shù)庫原本用以設(shè)置和獲取執(zhí)

6、行環(huán)境相關(guān)的信息，它們當(dāng)中也包含一系列用以同步的API。支持運行時對并行環(huán)境的改變和優(yōu)化，給編程人員足夠的靈活性來控制運行時的程序運行狀況。環(huán)境變量（OMP_NUM_THREADS ）,編寫OpenMP程序,開發(fā)工具已經(jīng)增加了對OpenMP的支持，Visual Studio 2005完全支持OpemMP 。編寫OpenMP程序的必要步驟：生成項目；配置項目，支持OpenMP;編寫代碼，加速#include “omp.h”；

7、編寫源程序；配置環(huán)境變量，確定線程的數(shù)目；執(zhí)行程序。,,,,,循環(huán)并行化,循環(huán)并行化編譯制導(dǎo)語句的格式，在C/C++語言中，循環(huán)并行化語句的編譯指導(dǎo)語句格式如下：#pragma omp parallel for [clause[clause…]] for (index = first ; test_expression ; increment_expr){ body of the loop;

8、} parallel關(guān)鍵字將緊跟的程序塊擴展為若干完全等同的并行區(qū)域，每個線程擁有完全相同的并行區(qū)域；關(guān)鍵字for則將循環(huán)中的工作分配到線程組中，線程組中的每一個線程完成循環(huán)中的一部分內(nèi)容。,循環(huán)并行化語句的限制,并行化語句必須是for循環(huán)語句并具有規(guī)范的格式，能夠推測出循環(huán)的次數(shù)，有以下約束 ：循環(huán)語句中的循環(huán)變量必須是有符號整型；循環(huán)語句中的比較操作必須是這樣的形式：loop_variable 或>= loop_inv

9、ariant_integer；循環(huán)語句中的第三個表達式（for循環(huán)的循環(huán)步長）必須是整數(shù)加或整數(shù)減，加減的數(shù)值必須是一個循環(huán)不變量（loop invariant value）；如果比較操作是或>=，那么循環(huán)變量的值在每次迭代時都必須減少；循環(huán)必須是單入口、單出口的，循環(huán)內(nèi)部不允許有能夠到達循環(huán)之外的跳轉(zhuǎn)語句，也不允許有外部的跳轉(zhuǎn)語句到達循環(huán)內(nèi)部。,簡單循環(huán)并行化,兩個向量相加，并將計算的結(jié)果保存到第三個向量中，向量的維數(shù)為n

10、。向量相加即向量的各個分量分別相加。 for（int i=0;i<n;i++） z[i]=x[i]+y[i]; 存在循環(huán)依賴性實例：for（int i=0;i<n;i++） z[i]=z[i-1]+x[i]+y[i]對于向量加法來說，可以使用循環(huán)并行化編譯指導(dǎo)語句直接對循環(huán)進行并行化 ：#pragma omp parallel forfor（int i=0;i<n;i++） z[i

11、]=x[i]+y[i];,數(shù)據(jù)相關(guān)的概念,如果語句S2與語句S1存在數(shù)據(jù)相關(guān)，那么必然存在以下兩種情況之一： S1在循環(huán)的一次迭代中訪問存儲單元L，而S2在隨后的一次迭代中訪問同一存儲單元，即：循環(huán)迭代相關(guān) ;S1和S2在同一循環(huán)迭代中訪問同一存儲單元L，但S1的執(zhí)行在S2之前，即：非循環(huán)迭代相關(guān) 。 實例： x[0] = 0; y[0] = 1; #pragma omp parallel for private(k)

12、 for (k = 1; k < 100; k++){ x[k] = y[k-1] + 1; //S1 y[k] = x[k-1] + 2; //S2 },,x[0] = 0; y[0] = 1; x[49] = 74;y[49] = 74 ;#pragma omp parallel for private(m, k) for (m = 0; m < 2; m++){ for (

13、k = m*49 + 1; k < m*50 + 50; k++){ x[k] = y[k-1] + 1; //S1 y[k] = x[k-1] + 2; //S2 } },循環(huán)并行化編譯指導(dǎo)語句的子句,循環(huán)并行化子句可以包含一個或者多個子句來控制循環(huán)并行化的實際執(zhí)行,可以用來控制循環(huán)并行化編譯。 數(shù)據(jù)的作用域子句用shared來表示一個變量是各個線程之間共享的，而用private

14、來表示一個變量是每一個線程私有的，用 threadprivate表示一個線程私有的全局變量。,循環(huán)嵌套,在一個循環(huán)體內(nèi)經(jīng)常會包含另外一個循環(huán)體，循環(huán)產(chǎn)生了嵌套 。循環(huán)并行化編譯制導(dǎo)語句可以加在任意一個循環(huán)之前，則對應(yīng)的最近的循環(huán)語句被并行化，其它部分保持不變。實際上并行化是作用于嵌套循環(huán)中的某一個循環(huán)，其它部分由執(zhí)行到的線程負責(zé)執(zhí)行。,,#include "stdafx.h"#include "omp

15、.h"int _tmain(int argc, _TCHAR* argv[]){int i;int j; #pragma omp parallel for //#pragma omp parallel for private(j)for(i=0;i<4;i++) for(j=6;j<10;j++)printf("i=%d j=%d\n",i,j);

16、printf("######################\n");for(i=0;i<4;i++) #pragma omp parallel for for(j=6;j<10;j++)printf("i=%d j=%d\n",i,j);return 0;},控制數(shù)據(jù)的共享屬性,OpenMP 程序在同一個共享內(nèi)存空間上執(zhí)行，線程通信容易，一個線程寫入

17、一個變量，另一個線程可以讀取這個變量來完成線程間的通信。,控制數(shù)據(jù)的共享屬性,全局變量以及程序代碼都是全局共享的；而動態(tài)分配的堆空間也是共享的。通過threadprivate來明確指出的某一個數(shù)據(jù)結(jié)構(gòu)屬于線程范圍的全局變量。 OpenMP 允許線程保留自己的私有變量不能讓其它線程訪問到。每一個線程會建立變量的私有拷貝，雖然變量名是相同的，實際上在共享內(nèi)存空間內(nèi)部的位置是不同的。,控制數(shù)據(jù)的共享屬性,數(shù)據(jù)作用域子句用來確定數(shù)據(jù)的共享屬

18、性，有下面以下幾個子句 ：shared用來指示一個變量的作用域是共享的；private用來指示一個變量作用域是私有的；firstprivate 和 lastprivate 分別對私有的變量進行初始化的操作和最后終結(jié)的操作，firstprivate 將串行的變量值拷貝到同名的私有變量中，在每一個線程開始執(zhí)行的時候初始化一次。而lastprivate則將并行執(zhí)行中的最后一次循環(huán)的私有變量值拷貝的同名的串行變量中；default語句用

19、來改變變量的默認私有屬性。,,在使用作用域子句的時候要遵循如下的一些規(guī)則 ：作用域子句作用的變量是已經(jīng)申明的有名變量；作用域子句在作用到類或者結(jié)構(gòu)的時候，必須作用到類或者結(jié)構(gòu)的整體，而不能只作用于類或者結(jié)構(gòu)的一個部分；一個編譯指導(dǎo)語句能夠包含多個數(shù)據(jù)作用域子句，但是變量只能出現(xiàn)在一個作用域子句中，即變量不能既是共享的，又是私有的；在語法結(jié)構(gòu)上，作用域子句只能作用在出現(xiàn)在編譯指導(dǎo)語句起作用的語句變量部分。另外，可以將作用域子句作用

20、在類的靜態(tài)變量上。,,OpenMP 對默認情況下，并行區(qū)中所有的變量都是共享的，但有三種例外情況：在parallel for循環(huán)中，循環(huán)索引變量是私有的；那些并行區(qū)中的局部變量是私有的；所有在private，firstprivate，lastprivate或reduction子句中列出的變量都是私有的。私有化是通過為每個線程創(chuàng)建各個變量的獨立副本來完成的。,,,規(guī)約操作的并行化,常見的規(guī)約操作——數(shù)組求和 # pragma om

21、p parallel for private（arx,ary,n） reduction（+:a,b） for（i=0;i<n;i++）{ a=a+arx[i]; b=b+ary[i]; },,使用reduction子句進行多線程程序設(shè)計時，要記住以下三個要點： 在第一個線程到達指定了reduction子句的共享區(qū)域或循環(huán)末尾時，原來的規(guī)約變量的值變?yōu)椴淮_定，并保持此不確定狀態(tài)直至規(guī)約計算完成 ;

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

23、到私有變量在主線程中的同名變量的值，也有可能需要將循環(huán)并行化最后一次循環(huán)的變量結(jié)果返回給主線程中的同名的變量。OpenMP 編譯指導(dǎo)語句使用firstprivate和 lastprivate對這兩種需求進行支持，使得循環(huán)并行開始執(zhí)行的時候私有變量通過主線程中的變量初始化，同時循環(huán)并行結(jié)束的時候，將最后一次循環(huán)的相應(yīng)變量賦值給主線程的變量。程序?qū)嵗?私有變量的初始化和終結(jié)操作實例,,數(shù)據(jù)相關(guān)性與并行化操作,并不是所有的循環(huán)都能夠使用

24、#pragma omp parallel for 來進行并行化。為了對一個循環(huán)進行并行化操作，我們必須要保證數(shù)據(jù)兩次循環(huán)之間不存在數(shù)據(jù)相關(guān)性。數(shù)據(jù)競爭——當(dāng)兩個線程對同一個變量進行操作，并且有一個操作為寫操作的時候，就說明這兩個線程存在數(shù)據(jù)競爭，此時，讀出的數(shù)據(jù)不一定就是前一次寫操作的數(shù)據(jù)，而寫入的數(shù)據(jù)也可能并不是程序所需要的。 for（int i=0;i<99;i++） a[i]=a[i

25、]+a[i+1];,,具有循環(huán)之間數(shù)據(jù)相關(guān)性的串行程序 for（int j=1;j<N;j++） for（int i=0;i<N;i++） a[i,j]=a[i,j]+a[i,j-1]; 具有循環(huán)之間數(shù)據(jù)相關(guān)性的并行程序for（int j=1;j<N;j++） #pragma omp parallel for for（int i=0;i<N;i++）

26、 a[i,j]=a[i,j]+a[i,j-1];,并行區(qū)域編程,并行區(qū)域就是通過循環(huán)并行化編譯指導(dǎo)語句使得一段代碼能夠在多個線程內(nèi)部同時執(zhí)行。 并行區(qū)域編譯指導(dǎo)語句的格式：#pragma omp parallel [clause[clause]…] blockparallel編譯指導(dǎo)語句的執(zhí)行過程#pragma omp parallel for（int i=0;i<5;i++） p

27、rintf（"hello world i=%d\n",i）; #pragma omp parallel for for（int i=0;i<5;i++） printf（"hello world i=%d\n",i）;,線程私有數(shù)據(jù)與threadprivate，copyin子句,使用threadprivate子句用來標(biāo)明某一個變量是線程私有數(shù)據(jù)，在程序運行的過程中，不能夠

28、被其他線程訪問到。使用copyin子句對線程私有的全局變量進行初始化。,int counter=0;#pragma omp threadprivate(counter)void inc_counter(){counter++;},int _tmain(int argc, _TCHAR* argv[]){#pragma omp parallelfor(int i=0;i<10000;i++)

29、inc_counter();printf("counter=%d\n",counter);return 0;},,,并行區(qū)域之間的工作共享,工作隊列：基本工作過程即為維持一個工作的隊列，線程在并行執(zhí)行的時候，不斷從這個隊列中取出相應(yīng)的工作完成，直到隊列為空為止。,int next_task=0; int get_next_task() { int task; #pragma

30、 omp criticalif(next_task<8) { task=next_task; next_task++; }else task=-1; return task; },void task_queue（） { int my_task; #pragma omp paralle

31、l private（my_task） { my_task=get_next_task（）; while（my_task!=-1）{ get_task_done（my_task）; my_task=get_next_task（）;

32、} } },并行區(qū)域之間的工作共享,根據(jù)線程號分配任務(wù)：由于每一個線程在執(zhí)行的過程中的線程標(biāo)識號是不同的，可以根據(jù)這個線程標(biāo)識號來分配不同的任務(wù)。,#pragma omp parallel private（myid） { nthreads=omp_get_num_threads（）; myid=omp_get_thread_num（）; get_my_work_done（myid,n

33、threads）; },并行區(qū)域之間的工作共享,使用循環(huán)語句分配任務(wù),int _tmain(int argc, _TCHAR* argv[]){int i;#pragma omp parallel //開始并行執(zhí)行{printf("outside loop thread=%d\n",omp_get_thread_num

34、());#pragma omp for for(i=0;i<4;i++) printf("inside loop i=%d thread=%d\n",i,omp_get_thread_num());}return 0;},并行區(qū)域之間的工作共享,工作分區(qū)編碼（sections）,int _tmain(int argc, _TCHAR* argv[]){#pr

35、agma omp parallel sections{#pragma omp sectionprintf("section 1 thread=%d\n",omp_get_thread_num());#pragma omp sectionprintf("section 2 thread=%d\n",omp_get_thread_num());#pragma omp sectio

36、nprintf("section 3 thread=%d\n",omp_get_thread_num());}return 0;},線程同步,OpenMP 支持兩種不同類型的線程同步機制：互斥鎖的機制：可以用來保護一塊共享的存儲空間，使得每一次訪問這塊共享內(nèi)存空間的線程最多一個，保證了數(shù)據(jù)的完整性?；コ獾牟僮麽槍π枰Ｗo的數(shù)據(jù)而言，在產(chǎn)生了數(shù)據(jù)競爭的內(nèi)存區(qū)域加入互斥，包括critical，atomi

37、c 等語句以及由函數(shù)庫中的互斥函數(shù)構(gòu)成的標(biāo)準(zhǔn)例程；事件通知機制：保證了多個線程之間的執(zhí)行順序。而事件機制則在控制規(guī)定線程執(zhí)行順序時所需要的同步屏障（barrier），定序區(qū)段（ordered sections），主線程執(zhí)行（master）等。,數(shù)據(jù)競爭,實例：尋找一個正整數(shù)數(shù)組中最大的元素。串行的算法如下所示，假設(shè)數(shù)組為ar，數(shù)組元素的數(shù)目為n。分析：設(shè)ar[0]=2, ar[1]=3。線程1執(zhí)行，發(fā)現(xiàn)ar[0]>ma

38、x_num，需max_num=ar[0]。此時，系統(tǒng)將線程1掛起。線程2繼續(xù)，發(fā)現(xiàn)ar[1]>max_num ，結(jié)果max_num=3，線程2完成。線程1被喚醒，使得max_num=ar[0] 。執(zhí)行的結(jié)果與串行結(jié)果完全不同。,int i; int max_num=-1; for（i=0;imax_num） max_num=ar[i];,int i; int max_num=-1; #pragma

39、omp parallel for for（i=0;imax_num） max_num=ar[i];,互斥鎖機制,OpenMP提供三種不同的互斥鎖機制：臨界區(qū)（critical）原子操作（atomic）由庫函數(shù)來提供同步操作臨界區(qū)通過編譯指導(dǎo)語句對產(chǎn)生數(shù)據(jù)競爭的內(nèi)存變量進行保護。臨界區(qū)編譯指導(dǎo)語句的格式如下所示： #pragma omp critical [（name）]

40、block 執(zhí)行程序塊block之前，首先要獲得臨界區(qū)的控制權(quán)。在線程組執(zhí)行的時候，保證每次最多只有一個線程執(zhí)行臨界區(qū)。name 是一個臨界區(qū)的屬性，臨界區(qū)的命名操作。,互斥鎖機制,修改尋找正整數(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=a

41、rx[i]; #pragma omp critical （max_ary） if（ary[i]>max_num_y） max_num_y=ary[i]; },,,互斥鎖機制,原子操作OpenMP編程方式給同步編程帶來的特殊的編程功能；通過編譯指導(dǎo)語句的方式直接獲取了現(xiàn)在多處理器計算機體系結(jié)構(gòu)的功能；操作在執(zhí)行的過程中是不會被打斷的。能夠完成對單一內(nèi)存單元的更新

42、，提供一種更高效率的互斥鎖機制。通過#pragma omp atomic 編譯指導(dǎo)語句提供；只能作用在語言內(nèi)建的基本數(shù)據(jù)結(jié)構(gòu)，語法格式如下所示：,#pragma omp atomic x =expr,#pragma omp atomic x++//or x--, --x, ++x,原子操作,在C/C++語言中可能的原子操作 ：“+ * - / & ^ | >”注意：當(dāng)對一個數(shù)據(jù)進行原子操作

43、保護的時候，就不能對數(shù)據(jù)進行臨界區(qū)的保護；在針對同一個內(nèi)存單元使用原子操作的時候需要在程序的所有涉及到的部位都加入原子操作的支持。,,,互斥鎖機制,運行時庫函數(shù)的互斥鎖支持OpenMP通過一系列的庫函數(shù)支持更加細致的互斥鎖操作 ；編譯指導(dǎo)語句進行的互斥鎖支持只能放置在一段代碼之前，作用在這段代碼之上；程序員必須自己保證在調(diào)用相應(yīng)鎖操作之后釋放相應(yīng)的鎖，否則就會造成多線程程序的死鎖。,,,,,隱含的同步屏障（barrier）,在每

44、一個并行區(qū)域都會有一個隱含的同步屏障（barrier），執(zhí)行此并行區(qū)域的線程組在執(zhí)行完畢本區(qū)域代碼之前，都需要同步并行區(qū)域的所有線程；一個同步屏障要求所有的線程執(zhí)行到此屏障，然后才能夠繼續(xù)執(zhí)行下面的代碼；#pragma omp for，#pragma omp single， #pragma omp sections 程序塊都包含自己的隱含的同步屏障；為了避免在循環(huán)過程中不必要的同步屏障，可以增加nowait子句到相應(yīng)的編譯指導(dǎo)語句

45、中。,,,明確的同步屏障語句,在有些情況下，隱含的同步屏障并不能提供有效的同步措施，可以在需要的地方插入明確的同步屏障語句#pragma omp barrier。此時，所有的執(zhí)行線程都會在同步屏障語句上進行同步。,#pragma omp parallel { initialization（）; #pragma omp barrier process（）; },,,,,循環(huán)并行化中的順序語

46、句,在某些情況下，我們對于循環(huán)并行化中的某些處理需要規(guī)定執(zhí)行的順序，典型的情況是在一次循環(huán)的過程中，一大部分的工作是可以并行執(zhí)行的，而其余的工作需要等到前面的工作全部完成之后才能夠執(zhí)行;在循環(huán)并行化的過程中，可以使用ordered子句使得順序執(zhí)行的語句直到前面的循環(huán)都執(zhí)行完畢之后再執(zhí)行;ordered子句使用實例。,,,影響性能的主要因素,根據(jù)Amdahl定律，我們應(yīng)當(dāng)努力提高并行化代碼在應(yīng)用程序中的比率，這是通用的提高效率的方法。

47、編寫OpenMP程序時需要考慮的程序優(yōu)化的一些方面的問題：OpenMP本身的開銷——OpenMP多線程并行化需要一定的程序庫的支持。在這些運行時庫對程序并行加速的同時需要運行庫的本身，因此，庫中代碼的運行必然會帶來一定的開銷。,影響性能的主要因素,編寫OpenMP程序時需要考慮的程序優(yōu)化的一些方面的問題：負載均衡——使用OpenMP進行并行程序編碼要非常注意使得線程之間的負載大致均衡，能夠讓多個線程在大致相同的時間內(nèi)完成工作，

48、從而能夠提高程序運行的效率。局部性——在程序運行過程中，高速緩存將緩存最近剛剛訪問過的數(shù)據(jù)以及這些數(shù)據(jù)相鄰的數(shù)據(jù)。因此，在編寫程序的時候，需要考慮到高速緩存的作用，有意地運用這種局部性帶來的高速緩存的效率提高。線程同步帶來的開銷——多個線程在進行同步的時候必然帶來一定的同步開銷，在使用多線程進行開發(fā)時需要考慮同步的必要性，消除不必要的同步，或者調(diào)整同步的順序，就有可能帶來性能上的提升。,OpenMP程序性能分析實例,并行化帶來的額外