李梅

（西安歐亞學院 陜西 西安 710065）

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

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

1 OpenMP并行化的開銷

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

#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；

}

第一個循環(huán)使用了OpenMP對循環(huán)進行并行化，而第二個循環(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ī)模比較小，使用并行化帶來的效果無法抵消并行化的額外負擔。但是如果將上述循環(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。

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

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

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

1）windows平臺下線程和CPU核的綁定

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

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

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

DWORD_PTR SetThreadAffinityMask（HANDLE hThread，DWORD_PTR dwThreadAffinityMask）；

第一個參數(shù)為線程句柄。

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

2）Linux平臺下線程和CPU核的綁定

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

3 負載均衡

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

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

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

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

}

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

The first:time=14.859000 seconds

The second:time=8.003000 seconds

The third:time=7.922000 seconds

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

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

4 線程同步開銷

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

5 結(jié) 論

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

[1]眭俊華，劉慧娜，王建鑫，等.多核多線程技術(shù)綜述[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]于芳.多核平臺下的多線程并行編程[J].陰山學刊，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].計算機工程與應(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].成都：成都理工大學，2011.

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

[6]任小西，唐玲，李仁發(fā)，等.OpenMP多線程負載均衡調(diào)度策略研究與實現(xiàn)[J].計算機科學，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.