基于OpenMP編程模型的多線(xiàn)程程序性能分析

李梅

（西安歐亞學(xué)院 陜西 西安 710065）

多核環(huán)境下軟件開(kāi)發(fā)的核心是多線(xiàn)程開(kāi)發(fā)[1]。采用多線(xiàn)程程序設(shè)計(jì)技術(shù)可以提高系統(tǒng)及 程序的運(yùn)行性能，諸如吞吐量、計(jì)算速度、響應(yīng)時(shí)間等。所以高性能、高效率是多線(xiàn)程程序并行化的目的之一。但是在很多情況下并行化后的程序并不能達(dá)到預(yù)期的執(zhí)行性能。影響執(zhí)行性能的原因是多方面的，比如OpenMP并行化的開(kāi)銷(xiāo)、線(xiàn)程在 CPU核間的動(dòng)態(tài)遷移、負(fù)載平衡、線(xiàn)程同步開(kāi)銷(xiāo)等。

OpenMP是一種面向共享存儲(chǔ)體系結(jié)構(gòu)的多線(xiàn)程并行編程語(yǔ)言[2]，是一種共享內(nèi)存并行的應(yīng)用程序編程接口。所有處理器都被連接到一個(gè)共享的內(nèi)存單元上，處理器在訪(fǎng)問(wèn)內(nèi)存的時(shí)候使用的是相同的內(nèi)存編址空間，由于內(nèi)存共享，因此，某一處理器寫(xiě)入的數(shù)據(jù)會(huì)立刻被其他處理器訪(fǎng)問(wèn)到。OpenMP編程模型通過(guò)提供一組與平臺(tái)無(wú)關(guān)的編譯指導(dǎo)、運(yùn)行時(shí)庫(kù)函數(shù)及環(huán)境變量，指導(dǎo)編譯器何時(shí)以及如何利用程序中的并行性進(jìn)行多線(xiàn)程并行執(zhí)行。OpenMP在并行執(zhí)行程序時(shí)，采用Fork/Join方式，它的基本思想是串行區(qū)域由主線(xiàn)程執(zhí)行，并行程序通過(guò)派生多個(gè)線(xiàn)程來(lái)并行執(zhí)行，并行執(zhí)行的程序要全部結(jié)束后才能執(zhí)行后面的非并行執(zhí)行的代碼[3]。

1 OpenMP并行化的開(kāi)銷(xiāo)

OpenMP是一個(gè)外部編程模型，而不是自動(dòng)編程模型，它能夠使程序員完全控制并行化[4]。OpenMP并行化本身是有一定開(kāi)銷(xiāo)的，因?yàn)镺penMP獲得應(yīng)用程序多線(xiàn)程并行化能力需要程序庫(kù)的支持，庫(kù)中代碼的運(yùn)行會(huì)帶來(lái)一定的開(kāi)銷(xiāo)。這種開(kāi)銷(xiāo)是不可避免的。但有時(shí)這種開(kāi)銷(xiāo)是沒(méi)有必要的。實(shí)際上，并不是所有的代碼都需要并行化，有些情況下，并行化之后程序的運(yùn)行效率反而比不上串行執(zhí)行的效率。很大一部分原因是由于使用OpenMP進(jìn)行并行化之后引入OpenMP本身的開(kāi)銷(xiāo)過(guò)大。因此，只有并行執(zhí)行代碼段負(fù)擔(dān)足夠大，而引入OpenMP本身的開(kāi)銷(xiāo)又足夠小，此時(shí)引入并行化操作才能加速程序的執(zhí)行。由于并行化會(huì)帶來(lái)額外的開(kāi)銷(xiāo)，因此，從效率上考慮，并不是所有的程序都應(yīng)當(dāng)并行化的，特別是對(duì)于小程序，并行化帶來(lái)的效率不足以彌補(bǔ)并行化本身帶來(lái)的運(yùn)行負(fù)擔(dān)，勉強(qiáng)進(jìn)行并行化就會(huì)得不償失。應(yīng)當(dāng)盡量使得程序真正工作的負(fù)載超過(guò)并行化的負(fù)擔(dān)，每一個(gè)線(xiàn)程負(fù)擔(dān)的工作要足夠多，這樣才能獲得并行化之后的性能提升。例如：

#include “stdafx.h”

#include

#include

int_tmain（intargc，_TCHAR*argv[]）

{

clock_tstart，stop；

unsigned long sum=0；

start=clock（）；

#pragamomp parallel for reduction（+:sum）

for（int i=0；i<1000；i++）

sum=sum+i；

stop=clock（）；

printf（“exec with OpenMP:sum=%ul，time=%f seconds ”，sum， （（double）

（stop-start）/1000.0））；

sum=0；

start=clock（）；

for（int i=0；i<1000；i++）

sum=sum+i；

stop=clock（）；

printf （“serial exec:sum=%ul，time=%f seconds ”，sum，（（double）（stop-start）/1000.0））；

return 0；

}

第一個(gè)循環(huán)使用了OpenMP對(duì)循環(huán)進(jìn)行并行化，而第二個(gè)循環(huán)使用了簡(jiǎn)單的串行執(zhí)行方式。下面是程序的一次執(zhí)行結(jié)果：

exec with OpenMP:sum=499950001，time=0.016000 seconds serial exec:sum=499950001，time=0.000000 seconds

可以看到串行執(zhí)行的效率要比并行執(zhí)行的效率高，這主要是由于循環(huán)的規(guī)模比較小，使用并行化帶來(lái)的效果無(wú)法抵消并行化的額外負(fù)擔(dān)。但是如果將上述循環(huán)次數(shù)改為1000000000

exec with openmp:sum=8874597121，timei=0.156000 seconds

serial exec:sum=8874597121，timei=0.297000 seconds

加速比為0.297000/0.156000=1.9034。

從這個(gè)例子中明顯看到在編寫(xiě)并行化程序時(shí)，應(yīng)當(dāng)盡量使得程序真正工作的負(fù)載超過(guò)并行化的負(fù)擔(dān)，每一個(gè)線(xiàn)程負(fù)擔(dān)的工作要足夠多，這樣才能獲得并行化之后的性能提升。

2 線(xiàn)程在CPU核間的動(dòng)態(tài)遷移

OpenMP應(yīng)用程序中，如果過(guò)多的線(xiàn)程集中在一個(gè)CPU上訪(fǎng)問(wèn)不同的內(nèi)存塊，顯然這種對(duì)內(nèi)存總線(xiàn)的競(jìng)爭(zhēng)會(huì)顯著降低訪(fǎng)存的速度。為提高處理器核的使用效率，主流操作系統(tǒng)調(diào)整了其調(diào)度算法，最常用的就是負(fù)載均衡技術(shù)，將 CPU的負(fù)荷平均分配到多個(gè) CPU核中，這就意味著，在比較繁忙的CPU核上運(yùn)行的線(xiàn)程可能會(huì)被操作系統(tǒng)自動(dòng)遷移到空閑的CPU核上，這種遷移將導(dǎo)致被遷移的線(xiàn)程的上下文需要遷移到新的CPU核上。如果頻繁遷移會(huì)導(dǎo)致應(yīng)用程序性能下降。為避免線(xiàn)程在CPU核間的動(dòng)態(tài)遷移，可以在不同平臺(tái)下將OpenMP線(xiàn)程綁定到指定的 CPU核上運(yùn)行，從而消除由于遷移原因而導(dǎo)致的性能降低。

1）windows平臺(tái)下線(xiàn)程和CPU核的綁定

一個(gè)程序指定到單獨(dú)一個(gè)CPU上運(yùn)行會(huì)比不指定CPU運(yùn)行時(shí)快。這中間主要有兩個(gè)原因：CPU切換時(shí)損耗的性能；Intel的自動(dòng)降頻技術(shù)和windows的機(jī)制沖突：windows有一個(gè)功能是平衡負(fù)載，可以將一個(gè)線(xiàn)程在不同時(shí)間分配到不同CPU，從而使得每一個(gè)CPU不“過(guò)累”。然而，Inter又有一個(gè)技術(shù)叫做SpeedStep，當(dāng)一個(gè)CPU沒(méi)有滿(mǎn)負(fù)荷運(yùn)行時(shí)自動(dòng)降頻從而達(dá)到節(jié)能減排的目的。這兩個(gè)功能實(shí)際是沖突的：一個(gè)程序被分配到多個(gè)CPU協(xié)同工作->每個(gè)CPU都不是滿(mǎn)載->每個(gè)CPU都會(huì)降頻->windows發(fā)現(xiàn)每個(gè)CPU性能都降低了，因此程序執(zhí)行速度也降低了。因此，將線(xiàn)程（進(jìn)程）綁定到指定CPU核心，不讓windows自作主張分散任務(wù)，從而提高單線(xiàn)程效率是很有必要的。有兩種方法實(shí)現(xiàn)綁定進(jìn)程到指定CPU：

手工調(diào)節(jié)：在資源管理器的進(jìn)程里面，設(shè)置相關(guān)性，可以設(shè)置進(jìn)程到某個(gè)或者某些指定的CPU核心。

代碼自動(dòng)調(diào)節(jié)：

DWORD_PTR SetThreadAffinityMask（HANDLE hThread，DWORD_PTR dwThreadAffinityMask）；

第一個(gè)參數(shù)為線(xiàn)程句柄。

第二個(gè)參數(shù)為 mask，可取值為 0～2^31（32位）和 0～2^63（64位），每一位代表每一個(gè)CPU是否使用。

2）Linux平臺(tái)下線(xiàn)程和CPU核的綁定

從 Linux2.6內(nèi)核開(kāi)始，Linux系統(tǒng)提供API函數(shù) sched_setaffinity和sched_getaffinity將線(xiàn)程和CPU核進(jìn)行綁定。

3 負(fù)載均衡

對(duì)于OpenMP多線(xiàn)程程序而言，負(fù)載均衡是影響其運(yùn)行性能的重要因素[5]。在多線(xiàn)程程序中，保證線(xiàn)程間的負(fù)載平衡是提高程序性能的方法之一。良好的負(fù)載平衡可以保證執(zhí)行核盡可能的在大部分時(shí)間里保持忙碌的狀態(tài)，將調(diào)度開(kāi)銷(xiāo)、上下文切換開(kāi)銷(xiāo)和同步開(kāi)銷(xiāo)降到最低。如果負(fù)載平衡做的很差，那么某些線(xiàn)程可能很早就完成了自己的工作，從而導(dǎo)致處理器資源閑置，降低了程序執(zhí)行的性能。

通常情況下，循環(huán)并行的負(fù)載平衡差是由循環(huán)迭代計(jì)算時(shí)間的不確定性引起的。一方面，有的循環(huán)通過(guò)檢查源代碼的方法來(lái)確定循環(huán)迭代的計(jì)算時(shí)間是比較容易的。在多數(shù)情況下，循環(huán)迭代總是耗費(fèi)一定數(shù)量的時(shí)間，即便不是這樣，也可以找到耗時(shí)相近的一組迭代。例如，有時(shí)候所有的偶數(shù)迭代集合和所有奇數(shù)迭代集合所耗費(fèi)的時(shí)間幾乎相等，或者循環(huán)前半部分迭代和后半部分迭代所耗費(fèi)的時(shí)間幾乎相等。另一方面，要找出耗時(shí)相同的迭代集合幾乎是不可能的。然而不管怎樣，都可以通過(guò)OpenMP的調(diào)度策略提供循環(huán)調(diào)度信息，使編譯器和運(yùn)行時(shí)庫(kù)能夠更好的劃分迭代，并將迭代分布到各個(gè)線(xiàn)程上，從而實(shí)現(xiàn)更好的負(fù)載平衡。

在編寫(xiě)OpenMP代碼時(shí)，注意保證負(fù)載的均衡，盡量讓每個(gè)線(xiàn)程的工作量相當(dāng)，從而保證程序的執(zhí)行效率。在循環(huán)并行化時(shí)，采用將循環(huán)次數(shù)平均分配到所有線(xiàn)程中的靜態(tài)分配策略，因此線(xiàn)程的工作量在進(jìn)入循環(huán)并行化之前就已經(jīng)確定了。這種分配策略在每次循環(huán)迭代工作量相仿的時(shí)候可以較好的保證線(xiàn)程間的負(fù)載平衡，獲得良好的執(zhí)行效率。但是，在實(shí)際情況中，每次循環(huán)的工作量并不一定相同，有時(shí)會(huì)差距很大，這時(shí)靜態(tài)分配策略會(huì)引起線(xiàn)程間負(fù)載的不均衡，使得負(fù)載輕的線(xiàn)程無(wú)事可做，負(fù)載重的線(xiàn)程工作繁忙。

為了解決這個(gè)問(wèn)題，OpenMP提供了動(dòng)態(tài)分配策略，動(dòng)態(tài)策略將循環(huán)迭代劃分為若干個(gè)迭代塊，每個(gè)塊使用一個(gè)內(nèi)部任務(wù)隊(duì)列采用先來(lái)先服務(wù)的方式進(jìn)行調(diào)度。首先為每個(gè)線(xiàn)程各分配一個(gè)循環(huán)塊，當(dāng)一個(gè)線(xiàn)程完成其分配的塊后，它將請(qǐng)求另一個(gè)循環(huán)塊，系統(tǒng)將從任務(wù)隊(duì)列頭部取出下一個(gè)循環(huán)塊分配給該線(xiàn)程。這個(gè)過(guò)程不斷重復(fù)，直至所有的迭代塊都被分配執(zhí)行完成。即讓線(xiàn)程根據(jù)自己的執(zhí)行能力向系統(tǒng)申請(qǐng)循環(huán)塊。動(dòng)態(tài)調(diào)度有利于緩解負(fù)載不均衡性[6]。

#include"stdafx.h"

#include

#include

void smallwork（）

{}

void bigwork（）

{unsigned long sum=0；

for（int i=0；i<100000000；i++）sum+=i；

}

int_tmain（intargc， _TCHAR*argv[]）

{clock_t start， stop；

start=clock（）；

#pragma omp parallel for

for（int i=0；i<100；i++）{

if（i<50）smallwork（）；

elsebigwork（）；

}

stop=clock（）；

printf （"The first:time=%f seconds "，（（double）（stopstart）/1000.0））；

start=clock（）；

#pragma omp parallel for schedule（dynamic，25）

for（int i=0；i<100；i++）{

if（i<50）smallwork（）；

elsebigwork（）；

}

stop=clock（）；

printf （"The second:time=%f seconds "，（（double）（stopstart）/1000.0））；

start=clock（）；

#pragma omp parallel for

for（int i=0；i<100；i++）{

if（i%2）smallwork（）；

elsebigwork（）；

}

stop=clock（）；

printf （"The third:time=%f seconds "，（（double）（stopstart）/1000.0））；

return 0；

}

下面是某次運(yùn)行結(jié)果：

The first:time=14.859000 seconds

The second:time=8.003000 seconds

The third:time=7.922000 seconds

通過(guò)這段代碼可以明顯看出負(fù)載均衡對(duì)程序性能的影響。程序中有smallwork（）和bigwork（）兩個(gè)函數(shù)，分別具有不同的負(fù)載，輕載的函數(shù)實(shí)際上就是一個(gè)空函數(shù)，而重載的函數(shù)則用來(lái)求和。

通過(guò)執(zhí)行結(jié)果可以看到，雖然三個(gè)循環(huán)的工作量是一樣的，但是運(yùn)行時(shí)間不盡相同。幾乎相差了一倍。在第一個(gè)循環(huán)中，由于步長(zhǎng)是1，OpenMP運(yùn)行時(shí)采用靜態(tài)調(diào)度策略將前面50個(gè)循環(huán)分配給一個(gè)線(xiàn)程，將后面50個(gè)循環(huán)分配給另一個(gè)線(xiàn)程。后一個(gè)線(xiàn)程需要運(yùn)行的都是負(fù)擔(dān)沉重的函數(shù)，而前一個(gè)線(xiàn)程會(huì)很快執(zhí)行完50個(gè)空函數(shù)，金繼續(xù)等待另一線(xiàn)程完成工作。在第二個(gè)循環(huán)中采用那個(gè)動(dòng)態(tài)調(diào)度策略將循環(huán)分為4個(gè)迭代塊，根據(jù)線(xiàn)程的執(zhí)行情況動(dòng)態(tài)分配，保證線(xiàn)程的負(fù)載平衡。在第三個(gè)循環(huán)處采用修改代碼的方法將輕重負(fù)載函數(shù)均衡地分配給兩個(gè)線(xiàn)程，從而保證負(fù)載平衡。

4 線(xiàn)程同步開(kāi)銷(xiāo)

多個(gè)線(xiàn)程在進(jìn)行同步的時(shí)候必然帶來(lái)一定的同步開(kāi)銷(xiāo)。當(dāng)然，有的同步開(kāi)銷(xiāo)是不可避免的，但是在某些情況下，不合適的同步機(jī)制或者算法會(huì)帶來(lái)運(yùn)行效率的急劇下降。因此在使用多線(xiàn)程進(jìn)行應(yīng)用程序開(kāi)發(fā)時(shí)一定要考慮同步的必要性，消除不必要的同步，或者調(diào)整同步的順序，帶來(lái)性能上的提升。

5 結(jié) 論

為提高程序性能，保證程序的執(zhí)行效率，在編寫(xiě)并行化程序時(shí)，應(yīng)盡量使程序真正工作的負(fù)載超過(guò)并行化的負(fù)擔(dān)，每個(gè)線(xiàn)程負(fù)擔(dān)的工作要足夠多；應(yīng)注意保證負(fù)載的平衡，盡量讓每個(gè)線(xiàn)程的工作量相當(dāng)；程序開(kāi)發(fā)時(shí)一定要考慮同步的必要性，消除不必要的同步。

[1]眭俊華，劉慧娜，王建鑫，等.多核多線(xiàn)程技術(shù)綜述[J].計(jì)算機(jī)應(yīng)用，2013（6）：239-242，261.SUIJun-hua，LIUHui-na，WANGJian-xin，etal.Multicore multi-threading technology were reviewed [J].Journal of Computer Applications，2013（6）：239-242，261.

[2]于芳.多核平臺(tái)下的多線(xiàn)程并行編程[J].陰山學(xué)刊，2010（9）:33-36.YU Fang.Multi-threads parallel programming method on multi-core PC[J].YinshanAcademIc Journal，2010（9）:33-36.

[3]何濤，李?lèi)?ài)波，黃淵.基于openMP多線(xiàn)程技術(shù)SAR地面處理軟件的并行設(shè)計(jì) [J].計(jì)算機(jī)工程與應(yīng)用，2011，47（8）:267-271 HE Tao，LI Ai-bo，HUANG Yuan.Parallel designof SAR-ground processing software based on OPenMP[J].Englneering and APPlications，2011，47（8）:267-271.

[4]游佐勇.openMP并行編程模型與性能優(yōu)化方法的研究與應(yīng)用[D].成都：成都理工大學(xué)，2011.

[5]唐玲.openMP多線(xiàn)程負(fù)載均衡分析方法及調(diào)度策略研究[D].長(zhǎng)沙：湖南大學(xué)，2010.

[6]任小西，唐玲，李仁發(fā)，等.OpenMP多線(xiàn)程負(fù)載均衡調(diào)度策略研究與實(shí)現(xiàn)[J].計(jì)算機(jī)科學(xué)，2010（11）：148-151.REN Xiao-xi，TANG Ling，LI Ren-fa，et al.Study and implementation of OpenMP multi-thread load balance scheduling schema[J].Computer Science，2010（11）:148-151.