李梅

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

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

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

1 OpenMP并行化的開銷

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

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

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

1）windows平臺(tái)下線程和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è)線程在不同時(shí)間分配到不同CPU，從而使得每一個(gè)CPU不“過累”。然而，Inter又有一個(gè)技術(shù)叫做SpeedStep，當(dāng)一個(gè)CPU沒有滿負(fù)荷運(yùn)行時(shí)自動(dòng)降頻從而達(dá)到節(jié)能減排的目的。這兩個(gè)功能實(shí)際是沖突的：一個(gè)程序被分配到多個(gè)CPU協(xié)同工作->每個(gè)CPU都不是滿載->每個(gè)CPU都會(huì)降頻->windows發(fā)現(xiàn)每個(gè)CPU性能都降低了，因此程序執(zhí)行速度也降低了。因此，將線程（進(jìn)程）綁定到指定CPU核心，不讓windows自作主張分散任務(wù)，從而提高單線程效率是很有必要的。有兩種方法實(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ù)為線程句柄。

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

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

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

3 負(fù)載均衡

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

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

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

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

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

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

4 線程同步開銷

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

5 結(jié) 論

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

[1]眭俊華，劉慧娜，王建鑫，等.多核多線程技術(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)下的多線程并行編程[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]何濤，李愛波，黃淵.基于openMP多線程技術(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多線程負(fù)載均衡分析方法及調(diào)度策略研究[D].長沙：湖南大學(xué)，2010.

[6]任小西，唐玲，李仁發(fā)，等.OpenMP多線程負(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.