李亞朋，龐建民，徐金龍，聶 凱

（1.鄭州大學(xué)中原網(wǎng)絡(luò)安全研究院，鄭州 450001；2.中國(guó)人民解放軍戰(zhàn)略支援部隊(duì)信息工程大學(xué)數(shù)學(xué)工程與先進(jìn)計(jì)算國(guó)家重點(diǎn)實(shí)驗(yàn)室，鄭州 450001；3.中國(guó)人民解放軍戰(zhàn)略支援部隊(duì)信息工程大學(xué)，鄭州 450001）

0 概述

2003 年以前，單核處理器的主頻在摩爾定律的影響下不斷提高，程序的執(zhí)行效率主要依賴處理器的主頻。2003年以后，由于功耗的原因，主頻遇到技術(shù)瓶頸，多核技術(shù)成為提升硬件性能的有效方案。多核處理器的發(fā)展，一方面提高了處理器的性能，另一方面將提高實(shí)際計(jì)算能力的任務(wù)轉(zhuǎn)移給了軟件開發(fā)人員。

為充分發(fā)揮多核處理器的計(jì)算潛力，并行編程模型應(yīng)運(yùn)而生，其中OpenMP 規(guī)范［1］對(duì)現(xiàn)有編程語(yǔ)言進(jìn)行了擴(kuò)展，為軟件開發(fā)人員提供簡(jiǎn)單、高效的編程接口，成為應(yīng)用最廣泛的多線程編程模型。OpenMP 是一組由計(jì)算機(jī)硬件和軟件供應(yīng)商聯(lián)合定義的應(yīng)用程序接口（API）［1］，OpenMP 標(biāo)準(zhǔn)規(guī)范于1997 年首次發(fā)布，最新版本為V5.0，為基于共享內(nèi)存并行程序的開發(fā)人員提供一種可擴(kuò)展的編程模型，目前在主流的編譯器中都具有相關(guān)技術(shù)支持。在OpenMP 線程執(zhí)行模式下，當(dāng)程序開始時(shí)單一主線程串行執(zhí)行，當(dāng)程序執(zhí)行到并行區(qū)域時(shí)派生出一組分支線程和主線程并行執(zhí)行，離開并行區(qū)域后所有線程進(jìn)行同步并且自動(dòng)結(jié)束，最后程序只剩一個(gè)單獨(dú)的主線程，繼續(xù)串行執(zhí)行。

針對(duì)不同的循環(huán)結(jié)構(gòu)，OpenMP 規(guī)范提供了多種調(diào)度策略，但都存在不同程度的調(diào)度開銷和負(fù)載均衡問題，最終影響熱點(diǎn)循環(huán)在目標(biāo)機(jī)器上的執(zhí)行效率。為盡可能地減少調(diào)度開銷，使得各個(gè)處理器負(fù)載趨于均衡，軟件開發(fā)人員需要根據(jù)循環(huán)特征在調(diào)度開銷和負(fù)載均衡之間進(jìn)行權(quán)衡，找到合適的調(diào)度策略。

本文提出一種針對(duì)線性循環(huán)結(jié)構(gòu)的調(diào)度策略Nonlinear_static，結(jié)合線性負(fù)載均勻變化參數(shù)與總負(fù)載、負(fù)載峰值、線程數(shù)構(gòu)建Nonlinear_static 調(diào)度模型，通過該模型計(jì)算每個(gè)迭代塊的大小使其呈現(xiàn)非線性遞增或遞減趨勢(shì)，并在開源OMPi 編譯器上編碼實(shí)現(xiàn)Nonlinear_static 調(diào)度策略，從而消除調(diào)度開銷并實(shí)現(xiàn)負(fù)載的均衡分配。

1 相關(guān)工作

1.1 循環(huán)結(jié)構(gòu)

科學(xué)計(jì)算中的二八法則表明，程序中20%的代碼占據(jù)80%的執(zhí)行時(shí)間，這些占據(jù)大量時(shí)間的代碼通常是程序中的循環(huán)結(jié)構(gòu)。因此，挖掘循環(huán)的并行性是提高程序執(zhí)行效率的有效方法［2］。循環(huán)分為含有依賴循環(huán)和不含依賴循環(huán)。有依賴的循環(huán)無(wú)法直接并行，因此不在本文的研究范圍內(nèi)。本文提到的循環(huán)均為不含依賴的循環(huán)。根據(jù)循環(huán)中負(fù)載的分布情況，常見循環(huán)分為4 種不同的結(jié)構(gòu)［3］，如圖1 所示，橫坐標(biāo)為循環(huán)索引變量i，縱坐標(biāo)L（i）表示第i次迭代中負(fù)載量。

圖1 4 種循環(huán)結(jié)構(gòu)Fig.1 Four loop structures

從圖1（a）可以看出，規(guī)則循環(huán)結(jié)構(gòu)的負(fù)載L（i）在迭代索引i上的分布是均勻不變的。隨機(jī)循環(huán)結(jié)構(gòu)的負(fù)載L（i）在迭代索引i上隨機(jī)分布，沒有規(guī)律。遞增循環(huán)結(jié)構(gòu)和遞減循環(huán)結(jié)構(gòu)的負(fù)載L（i）在循環(huán)索引i上呈線性遞增和線性遞減趨勢(shì)。4 種循環(huán)結(jié)構(gòu)基本包括絕大部分的應(yīng)用場(chǎng)景，其中隨機(jī)循環(huán)結(jié)構(gòu)、遞增循環(huán)結(jié)構(gòu)和遞減循環(huán)結(jié)構(gòu)稱為非規(guī)則循環(huán)結(jié)構(gòu)［4］，而遞增循環(huán)結(jié)構(gòu)和遞減循環(huán)結(jié)構(gòu)又稱線性循環(huán)結(jié)構(gòu)。

1.2 OpenMP 循環(huán)調(diào)度策略

在共享存儲(chǔ)體系結(jié)構(gòu)中，調(diào)度開銷和負(fù)載均衡是循環(huán)級(jí)并行化面臨的重要問題。不同的調(diào)度策略針對(duì)特定循環(huán)的效果有好有壞，沒有任何一種調(diào)度策略能夠解決所有的循環(huán)調(diào)度問題［5］，關(guān)鍵在于找到適合目標(biāo)循環(huán)特征的調(diào)度策略。

目前，OpenMP 規(guī)范中提供了4 種標(biāo)準(zhǔn)的調(diào)度策略，分別是靜態(tài)調(diào)度（static）、動(dòng)態(tài)調(diào)度（dynamic）、指導(dǎo)調(diào)度（guided）以及運(yùn)行時(shí)調(diào)度（runtime），其中運(yùn)行時(shí)調(diào)度根據(jù)環(huán)境變量動(dòng)態(tài)選擇前3 種中的1 種，環(huán)境變量由程序員提前指定。

靜態(tài)調(diào)度在默認(rèn)情況下將循環(huán)迭代劃分為大小相等的塊，每個(gè)線程分到的迭代塊值chunksize（線程分到迭代塊的大?。┑扔赑/N（N代表循環(huán)總的迭代數(shù)，P代表使用的線程數(shù)），當(dāng)無(wú)法整除時(shí)會(huì)盡可能平均分配。靜態(tài)調(diào)度還可以指定chunksize 值，在這種情況下，每個(gè)線程依次得到chunksize 值的迭代塊，直到所有的迭代都分配完成。這種調(diào)度方法適用于規(guī)則循環(huán)結(jié)構(gòu)，對(duì)于隨機(jī)循環(huán)結(jié)構(gòu)和線性循環(huán)結(jié)構(gòu)，不同的線程負(fù)載差距較大，負(fù)載均衡性較差［6-7］，其優(yōu)點(diǎn)是迭代在線程上的映射編譯時(shí)已經(jīng)確定，所以在運(yùn)行時(shí)沒有調(diào)度開銷。

動(dòng)態(tài)調(diào)度在程序運(yùn)行中每個(gè)線程會(huì)申請(qǐng)chunksize 大小的迭代塊，當(dāng)某個(gè)線程執(zhí)行完任務(wù)處于空閑狀態(tài)但還有迭代未被執(zhí)行時(shí)，它會(huì)再次請(qǐng)求chunksize 大小的迭代塊，直到所有的循環(huán)都執(zhí)行完成。在默認(rèn)情況下，當(dāng)不指定chunksize 時(shí)，其值為1。相較于靜態(tài)調(diào)度，動(dòng)態(tài)調(diào)度能夠更好地適應(yīng)非規(guī)則循環(huán)結(jié)構(gòu)，但其會(huì)面臨chunksize 值的抉擇，過大的塊會(huì)引起線程間的負(fù)載不均衡，過小的塊則會(huì)引起頻繁的線程調(diào)度，造成嚴(yán)重的調(diào)度開銷［8］。

指導(dǎo)調(diào)度［9］是一種啟發(fā)式的自調(diào)度方法，其迭代塊值不是恒定不變的而是逐漸減小的，先申請(qǐng)任務(wù)線程得到的迭代塊會(huì)比較大，之后逐漸減小。迭代塊值是一個(gè)可選參數(shù)，迭代塊的變化呈指數(shù)下降，直至下降到迭代塊值保持不變，當(dāng)不指定迭代塊值時(shí)，其值默認(rèn)為1。在OMPi 編譯器中迭代塊是按照ch=（ch+t->nth-1）/t->nth 來計(jì)算，其中ch 表示剩余迭代的值，t->nth 表示線程數(shù)。指導(dǎo)調(diào)度在面臨遞增型循環(huán)結(jié)構(gòu)時(shí)表現(xiàn)出良好的負(fù)載均衡性，但是當(dāng)遇到隨機(jī)型循環(huán)特別是遞減型循環(huán)時(shí)，容易造成負(fù)載集中于前面幾個(gè)線程的現(xiàn)象。

除OpenMP 規(guī)范中標(biāo)準(zhǔn)調(diào)度策略之外，梯式調(diào)度（TSS）［3］綜合了動(dòng)態(tài)調(diào)度和指導(dǎo)調(diào)度優(yōu)點(diǎn)，常用于處理非規(guī)則循環(huán)。相似于動(dòng)態(tài)調(diào)度，梯式調(diào)度迭代塊值的變化是線性的，與動(dòng)態(tài)調(diào)度不同的是其迭代塊值下降到一定程度后將保持不變，在一定程度上緩解了動(dòng)態(tài)調(diào)度和指導(dǎo)調(diào)度后期調(diào)度開銷大的問題。線性變化的迭代塊值使得梯式調(diào)度在面對(duì)遞增循環(huán)結(jié)構(gòu)時(shí)相較于指導(dǎo)調(diào)度具有更優(yōu)的負(fù)載均衡性。

Factoring 調(diào)度（FSS）［10］采用分段的方法處理循環(huán)迭代。在同一個(gè)段內(nèi)，每個(gè)線程分配的迭代塊值是相同的，而段與段之間是線性減小的。這種方法在面對(duì)非規(guī)則循環(huán)時(shí)相較于梯式調(diào)度負(fù)載均衡性更優(yōu)，但實(shí)現(xiàn)復(fù)雜且開銷更大。從整體上分析，F(xiàn)actoring 調(diào)度的迭代塊值同樣是不斷減小的，所以在處理遞減型循環(huán)時(shí)，隨著負(fù)載的不斷減小，分配到的迭代塊也是越來越小，造成嚴(yán)重的負(fù)載失衡。

針對(duì)指導(dǎo)調(diào)度和Factoring 調(diào)度不適用于遞減型循環(huán)的問題，文獻(xiàn)［12］借鑒α調(diào)度策略［11］，提出new_guided調(diào)度策略。在循環(huán)的前半段使用靜態(tài)調(diào)度，后半段使用指導(dǎo)調(diào)度，保證調(diào)度初期迭代塊值不至于過大，在一定程度上緩解了負(fù)載在最初幾個(gè)線程過于集中的問題。在面對(duì)遞減型循環(huán)時(shí)，new_guided 調(diào)度相較于指導(dǎo)調(diào)度具有更優(yōu)的均衡效果，但在本質(zhì)上并沒有解決現(xiàn)有調(diào)度策略迭代塊遞降的弊端。

在處理負(fù)載均衡問題上，一種解決方法是由用戶定義的調(diào)度策略［13-14］，使用戶收集應(yīng)用的負(fù)載信息再反饋給調(diào)度策略，然后進(jìn)行針對(duì)性的迭代塊劃分，缺點(diǎn)是搜集負(fù)載的難度較大，增加了用戶的工作量，實(shí)際操作較困難；另一種解決方法是動(dòng)態(tài)循環(huán)自調(diào)度技術(shù)（DLS）［15］，但其僅適用于計(jì)算密集型以及不規(guī)則循環(huán)的調(diào)度。

在硬件方面，硬件感知編譯器增強(qiáng)調(diào)度［16］結(jié)合硬件特點(diǎn)和調(diào)度策略，充分發(fā)揮硬件的算力，更適用于異構(gòu)平臺(tái)。

以上調(diào)度策略中N代表循環(huán)總的迭代數(shù)，P代表使用的線程數(shù)，迭代塊值代表線程分到迭代塊的值。當(dāng)循環(huán)迭代數(shù)為1 000，線程數(shù)為4 時(shí)，不同調(diào)度策略的迭代塊值如表1 所示，動(dòng)態(tài)調(diào)度的迭代塊值是100，指導(dǎo)調(diào)度最小為100。

表1 不同調(diào)度策略的迭代塊值Table 1 Chunksize of different scheduling strategies

1.3 現(xiàn)有調(diào)度策略

現(xiàn)有調(diào)度策略無(wú)論是OpenMP 標(biāo)準(zhǔn)調(diào)度策略還是梯式調(diào)度、Factoring 調(diào)度策略、new_guided 調(diào)度策略，迭代塊值的變化主要是線性、非線性、分段線性、線性和非線性相混合。從表1 可以看出，除了靜態(tài)調(diào)度和動(dòng)態(tài)調(diào)度的迭代塊值一直保持不變以外，其他調(diào)度策略迭代塊值總體上都是不斷減小，調(diào)度策略難以解決負(fù)載集中在先分配的迭代塊的問題，特別是在處理遞減型循環(huán)時(shí)，這種現(xiàn)象尤為嚴(yán)重。針對(duì)這種問題，本文提出一種非線性靜態(tài)調(diào)度的策略，能夠?qū)⒇?fù)載平均劃分到各個(gè)迭代塊中，并沒有調(diào)度開銷。此外，對(duì)于遞增型循環(huán)也可以用同樣的方法進(jìn)行處理。遞增型循環(huán)動(dòng)態(tài)調(diào)度和指導(dǎo)調(diào)度雖然負(fù)載分配較均衡，但是需要進(jìn)行多次調(diào)度，調(diào)度開銷較大。本文調(diào)度策略在處理線性循環(huán)時(shí)與靜態(tài)調(diào)度的區(qū)別如圖2 所示，迭代塊的劃分由原來的均分變成了非線性劃分，由于迭代塊的變化是非線性的，因此記為Nonlinear_static 調(diào)度策略。

圖2 靜態(tài)調(diào)度和非線性靜態(tài)調(diào)度Fig.2 Static scheduling and Nonlinear_static scheduling

2 Nonlinear_static 調(diào)度策略的設(shè)計(jì)與實(shí)現(xiàn)

2.1 OMPi 編譯器

OMPi 編譯器［17］是由希臘約阿尼納大學(xué)的并行處理小組研發(fā)的OpenMP 編譯器，是一款輕量型、可移植的源到源C 編譯器，最新開發(fā)到了2.0.0 版本，支持OpenMP 4.0 標(biāo)準(zhǔn)。OMPi 編譯器將程序員編寫的帶有OpenMP 指導(dǎo)語(yǔ)句的C 代碼轉(zhuǎn)換為基于pthreads 等線程庫(kù)的C 代碼，然后重新調(diào)用指定的C 編譯器進(jìn)行二次編譯并生成可執(zhí)行文件。由于OMPi 編譯器具有輕量、結(jié)構(gòu)性強(qiáng)、易于實(shí)現(xiàn)OpenMP 調(diào)度策略等特點(diǎn)，因此本文調(diào)度策略的設(shè)計(jì)以及實(shí)現(xiàn)都是基于OMPi 編譯器2.0.0 版本。

OMPi 代碼編譯示例如圖3 所示，由于是靜態(tài)調(diào)度，迭代塊值的計(jì)算在編譯階段已經(jīng)完成，每個(gè)線程迭代塊的開始位置存放在指針*fiter 中，結(jié)束位置存放在指針*liter 中，各個(gè)線程按照迭代塊并行執(zhí)行互不干擾并且沒有調(diào)度開銷。

圖3 OMPi 代碼編譯示例Fig.3 Compilation example of OMPi code

2.2 Nonlinear_static 調(diào)度模型

Nonlinear_static 調(diào)度策略是一種靜態(tài)調(diào)度策略，并行程序在編譯過程中確定迭代塊的劃分，沒有調(diào)度開銷。迭代塊根據(jù)線性遞增或線性遞減的負(fù)載進(jìn)行平均劃分，確保每個(gè)線程在并行執(zhí)行期間都能夠處于工作狀態(tài)，減少線程同步等待時(shí)間，提升程序執(zhí)行效率。模型參數(shù)說明如表2 所示。

表2 Nonlinear_static 調(diào)度模型參數(shù)說明Table 2 Parameter description of Nonlinear_static scheduling model

遞減循環(huán)和遞增循環(huán)負(fù)載分塊示意圖如圖4和圖5所示，不同灰度的色塊表示不同線程分配到的迭代塊。

圖4 遞減循環(huán)負(fù)載分塊示意圖Fig.4 Schematic diagram of decreasing loop load block

圖5 遞增循環(huán)負(fù)載分塊示意圖Fig.5 Schematic diagram of incremental loop load block

Nonlinear_static 調(diào)度策略的目的是使得每個(gè)線程的負(fù)載量保持一致，對(duì)于遞減型循環(huán)f（i）的推導(dǎo)主要分為以下5 個(gè)步驟。

1）計(jì)算參與的常量（總負(fù)載、平均負(fù)載、斜率），如式（1）～式（3）所示：

2）列出恒等式，如式（4）、式（5）所示：

3）計(jì)算h（i），如式（6）所示：

4）計(jì)算lload（i）如式（7）所示：

5）從以上公式推理可得：

同理可得當(dāng)循環(huán)為線性遞增型循環(huán)時(shí)，f（i）如式（9）所示：

式（4）表明每個(gè)線程的負(fù)載lload（i）需要等于理論上的平均負(fù)載，式（7）用于計(jì)算線程i根據(jù)本文提出的調(diào)度策略分配到的負(fù)載值。通過以上計(jì)算就可以得到f（i），f（i）是Nonlinear_static 調(diào)度策略劃分迭代塊的依據(jù)，不同的線程獲得不同大小的f（i），但對(duì)應(yīng)到負(fù)載上每個(gè)線程是嚴(yán)格均衡的。在代碼實(shí)現(xiàn)中，當(dāng)計(jì)算結(jié)果不是整數(shù)時(shí)，處理方法是向下取整。

2.3 Nonlinear_static 調(diào)度實(shí)現(xiàn)

本文在OMPi 編譯器中編碼實(shí)現(xiàn)一種不同于傳統(tǒng)靜態(tài)調(diào)度的非線性靜態(tài)調(diào)度策略，具有沒有調(diào)度開銷以及高數(shù)據(jù)局部性的優(yōu)點(diǎn)。Nonlinear_static 調(diào)度按照f（i）進(jìn)行迭代塊的劃分使得每個(gè)線程的負(fù)載總是等于avg_load，保證負(fù)載的均衡性。

從代碼層面分析，OMPi 編譯器模塊化清晰明了，能夠更好地進(jìn)行擴(kuò)展，為實(shí)現(xiàn)OpenMP 調(diào)度策略提供便利，這也是在GCC 編譯器和可執(zhí)行文件之間選擇一個(gè)源到源編譯器的原因。通過OMPi 編譯器更改其中關(guān)于OpenMP 調(diào)度的代碼，進(jìn)而實(shí)現(xiàn)自己的調(diào)度策略。在OMPi 編譯器中，本文實(shí)現(xiàn)3 種基本調(diào)度策略（靜態(tài)、動(dòng)態(tài)、指導(dǎo)）的代碼在文件/ompi-2.0.0/runtime/host/worksharing.c 中，不同的調(diào)度策略對(duì)應(yīng)各自的函數(shù)調(diào)用，其中ort_get_static_default_chunk（）函數(shù)用于計(jì)算靜態(tài)調(diào)度迭代塊的大小f（i），并把f（i）的開始迭代索引存放在指針*fiter 中，把迭代塊結(jié)束索引存放在指針*liter 中。

在Nonlinear_static 調(diào)度模型中計(jì)算每個(gè)線程迭代塊的大小f（i），作為分塊的依據(jù)，但在調(diào)度策略代碼實(shí)現(xiàn)中，還需要知道迭代塊首尾索引的值，即為*fiter、*liter 賦值。sstart（i）為線程i分配到迭代塊的開始索引，推導(dǎo)主要用到2.2 節(jié)中的變量。

1）當(dāng)循環(huán)為線性遞減循環(huán)時(shí)，sstart（i）如式（10）所示：

2）當(dāng)循環(huán)為線性遞增循環(huán)時(shí)，sstart（i）如式（11）所示：

從f（i）以及sstart（i）的計(jì)算結(jié)果得到*fiter 和*liter的值，*fiter=start（i），*liter=*fiter+f（i）。Nonlinear_static調(diào)度策略是一種靜態(tài)調(diào)度，本文在OpenMP 標(biāo)準(zhǔn)靜態(tài)調(diào)度的基礎(chǔ)上進(jìn)行實(shí)現(xiàn)的，總迭代數(shù)的獲取如圖6所示，Nonlinear_static 偽代碼如圖7 所示，其中myid對(duì)應(yīng)線程i，fi 對(duì)應(yīng)f（i），start 對(duì)應(yīng)開始索引sstart（i）。為保證計(jì)算的精確度，中間變量都定義為浮點(diǎn)型數(shù)據(jù)。

圖6 總迭代數(shù)的獲取Fig.6 Obtaining the total number of iterations

圖7 Nonlinear_static 調(diào)度的偽代碼Fig.7 Pseudocode of Nonlinear_static scheduling

3 實(shí)驗(yàn)與結(jié)果分析

3.1 實(shí)驗(yàn)環(huán)境

本文采用戴爾Power Edge T640 服務(wù)器作為實(shí)驗(yàn)平臺(tái)，具有2 個(gè)Intel?Xeon?Silver 4110 CPU，2 個(gè)CPU 有8 個(gè)核心，共16 核心，主頻為2.10 GHz，內(nèi)存為128 GB。操作系統(tǒng)使用Ubuntu16.04，編譯器采用GCC 7.1.0 版本，優(yōu)化選項(xiàng)-O3，OMPi 編譯器使用最新的2.0.0 版本。

針對(duì)1.1 節(jié)提到的4 種基本循環(huán)結(jié)構(gòu)，本文選取典型的應(yīng)用程序分別進(jìn)行調(diào)度策略測(cè)試。AC（Adjoint Convolution）是一個(gè)遞減型循環(huán)結(jié)構(gòu)，用于計(jì)算2 個(gè)向量的卷積，實(shí)驗(yàn)規(guī)模為600×600。CP（Compute Pots）［18］是一個(gè)遞增型循環(huán)結(jié)構(gòu)，用于更新三維空間中點(diǎn)與點(diǎn)之間的數(shù)值關(guān)系，類似于模板計(jì)算，實(shí)驗(yàn)規(guī)模為10 000，源代碼發(fā)布于2007 年Intel 多核平臺(tái)編碼優(yōu)化賽事。MM（Matrix Multiplication）［19］是一個(gè)規(guī)則循環(huán)結(jié)構(gòu)，用于計(jì)算浮點(diǎn)矩陣乘法，實(shí)驗(yàn)規(guī)模為2 500×2 500。MS（Mandelbrot Set）是一個(gè)隨機(jī)循環(huán)結(jié)構(gòu)，能夠生成復(fù)平面上分形圖的點(diǎn)的集合，實(shí)驗(yàn)規(guī)模為15 000×15 000。為充分驗(yàn)證測(cè)試用例的性能表現(xiàn)，本文選取的實(shí)驗(yàn)規(guī)模在保證加速效果來自于調(diào)度策略而不是隨機(jī)因素的前提下，盡可能進(jìn)行多次實(shí)驗(yàn)來排除隨機(jī)因素，以驗(yàn)證調(diào)度策略的可靠性以及擴(kuò)展性。CP 程序與AC 程序的負(fù)載分布如圖8 所示，負(fù)載的單位是核心計(jì)算的次數(shù)。

圖8 CP 和AC 程序負(fù)載分布Fig.8 Load distribution of CP and AC programs

本文實(shí)驗(yàn)主要研究4 種測(cè)試用例中的熱點(diǎn)循環(huán)部分，針對(duì)整個(gè)熱點(diǎn)循環(huán)從開始執(zhí)行到執(zhí)行完畢的時(shí)間，計(jì)時(shí)操作使用OpenMP 提供的函數(shù)omp_get_wtime（），該函數(shù)返回1 個(gè)雙精度浮點(diǎn)值，等于經(jīng)過的時(shí)間（以s 為單位）。

3.2 實(shí)驗(yàn)結(jié)果分析

測(cè)試用例串行執(zhí)行時(shí)間如表3 所示。為保證數(shù)據(jù)的全面性，本文分別測(cè)試線程數(shù)為4、8、12、16 時(shí)不同調(diào)度策略的并行執(zhí)行時(shí)間。針對(duì)同一種調(diào)度策略，本文還測(cè)試了不同迭代塊值（由OpenMP 指導(dǎo)語(yǔ)句指定）下的并行時(shí)間，經(jīng)過測(cè)試迭代塊值的選取除了對(duì)靜態(tài)調(diào)度有一定的影響外，對(duì)于其他調(diào)度策略影響較小。因此，本文只列舉chunksize=100 的情況下，對(duì)比不同調(diào)度策略的執(zhí)行時(shí)間。

表3 測(cè)試用例串行執(zhí)行時(shí)間Table 3 Serial execution time of test case s

3.2.1 AC 程序并行執(zhí)行結(jié)果

AC 是線性循環(huán)中的遞減型循環(huán)。AC 程序并行執(zhí)行時(shí)間如表4 所示，不同調(diào)度策略的AC 程序并行執(zhí)行時(shí)間對(duì)比如圖9 所示。從表4 和圖9 可以看出，表現(xiàn)最差的是靜態(tài)調(diào)度和指導(dǎo)調(diào)度。靜態(tài)調(diào)度把循環(huán)迭代均勻分割在各個(gè)線程，造成負(fù)載在最先分配的線程上最多，最后分配的線程上最少。指導(dǎo)調(diào)度由于迭代塊是指數(shù)下降的，負(fù)載的不均衡度更大。表現(xiàn)較優(yōu)的是動(dòng)態(tài)調(diào)度和new_guided 調(diào)度，線程動(dòng)態(tài)申請(qǐng)迭代塊，減少了線程的等待，使得線程一直處于工作狀態(tài)。根據(jù)文獻(xiàn)［20］的實(shí)驗(yàn)數(shù)據(jù)，梯式調(diào)度的效果與new_guided 調(diào)度相當(dāng)。表現(xiàn)最優(yōu)的是Nonlinear_static 調(diào)度，與動(dòng)態(tài)調(diào)度和指導(dǎo)調(diào)度相比，Nonlinear_static 調(diào)度具有更優(yōu)的負(fù)載均衡且沒有調(diào)度開銷。

表4 AC 程序并行執(zhí)行時(shí)間Table 4 Parallel execution time of AC program s

圖9 不同調(diào)度策略的AC 程序并行執(zhí)行時(shí)間對(duì)比Fig.9 Parallel execution time comparison of AC program among different scheduling strategies

3.2.2 CP 程序并行執(zhí)行結(jié)果

CP 程序并行執(zhí)行時(shí)間如表5 所示，不同調(diào)度策略的CP 程序并行執(zhí)行時(shí)間對(duì)比如圖10 所示。從表5 和圖10 可以看出，對(duì)于CP 的遞增型循環(huán)結(jié)構(gòu)，靜態(tài)調(diào)度表現(xiàn)最差，指導(dǎo)調(diào)度略弱于動(dòng)態(tài)調(diào)度和new_guided 調(diào)度，根據(jù)文獻(xiàn)［20］的實(shí)驗(yàn)數(shù)據(jù)，梯式調(diào)度的效果與動(dòng)態(tài)調(diào)度相當(dāng)，Nonlinear_static 調(diào)度表現(xiàn)最優(yōu)。

表5 CP 程序并行執(zhí)行時(shí)間Table 5 Parallel execution time of CP program s

圖10 不同調(diào)度策略的CP 程序并行執(zhí)行時(shí)間對(duì)比Fig.10 Parallel execution time comparison of CP program among different scheduling strategies

3.2.3 MS 與MM 程序并行執(zhí)行時(shí)間

MS隨機(jī)循環(huán)結(jié)構(gòu)的并行執(zhí)行時(shí)間如表6所示，MM規(guī)則循環(huán)結(jié)構(gòu)并行執(zhí)行時(shí)間如表7 所示。從表6 和表7可以看出，表現(xiàn)最優(yōu)的是動(dòng)態(tài)調(diào)度、指導(dǎo)調(diào)度以及new_guided調(diào)度。隨機(jī)循環(huán)結(jié)構(gòu)負(fù)載分布是隨機(jī)變化，因此，需要?jiǎng)討B(tài)分配迭代塊才能實(shí)現(xiàn)負(fù)載均衡，靜態(tài)調(diào)度以及Nonlinear_static 調(diào)度的迭代塊分配在編譯過程中已經(jīng)確定了，所以表現(xiàn)最差。在面對(duì)規(guī)則循環(huán)時(shí)，Nonlinear_static調(diào)度的表現(xiàn)也是最差的。根據(jù)文獻(xiàn)［20］的實(shí)驗(yàn)數(shù)據(jù)，梯式調(diào)度在面對(duì)隨機(jī)循環(huán)結(jié)構(gòu)時(shí)效果優(yōu)于new_guided 調(diào)度，在處理規(guī)則循環(huán)結(jié)構(gòu)時(shí)表現(xiàn)出與動(dòng)態(tài)調(diào)度相同的效果。

表6 MS 程序并行執(zhí)行時(shí)間Table 6 Parallel execution time of MS program s

表7 MM 程序并行執(zhí)行時(shí)間Table 7 Parallel execution time of MM program s

不同調(diào)度策略的本質(zhì)是對(duì)chunksize 劃分不同，循環(huán)結(jié)構(gòu)的負(fù)載分布是變化的，因此會(huì)造成線程分配到的負(fù)載量難以明確，反映到OpenMP 調(diào)度模型上使得先執(zhí)行完任務(wù)的線程，并等待未執(zhí)行完任務(wù)的線程進(jìn)行同步操作，而這一步驟會(huì)降低程序整體的執(zhí)行效率。從表4～表7 可以看出，對(duì)于不同的測(cè)試用例，除了靜態(tài)調(diào)度在指定chunksize 時(shí)有明顯的加速（對(duì)于規(guī)則循環(huán)是負(fù)加速）外，其他的調(diào)度策略在指定chunksize 時(shí)基本沒有大的變化。

從整體上分析，靜態(tài)調(diào)度不能有效地平衡負(fù)載，除了規(guī)則循環(huán)結(jié)構(gòu)，一般情況下效果都是最差的。

指導(dǎo)調(diào)度的特性導(dǎo)致其不適合處理遞減型循環(huán)。Nonlinear_static 調(diào)度由于靜態(tài)的迭代塊劃分規(guī)則，無(wú)論是哪種類型的循環(huán)，其迭代塊的劃分是固定的，所以不適合隨機(jī)循環(huán)以及規(guī)則循環(huán)結(jié)構(gòu)。在其他情況下，動(dòng)態(tài)調(diào)度和指導(dǎo)調(diào)度性能較優(yōu)，符合其動(dòng)態(tài)分配迭代塊的設(shè)計(jì)原理，但額外的調(diào)度開銷使得它們?cè)诰€性循環(huán)時(shí)相較于Nonlinear_static 調(diào)度效果較差。Nonlinear_static 調(diào)度相較于其他調(diào)度策略能夠更好地處理線性循環(huán)，理論與實(shí)驗(yàn)結(jié)果相一致。

4 結(jié)束語(yǔ)

本文提出靜態(tài)調(diào)度策略Nonlinear_static 用于消除調(diào)度開銷。將線性循環(huán)負(fù)載均勻變化參數(shù)與總負(fù)載、負(fù)載峰值、線程數(shù)相結(jié)合構(gòu)建Nonlinear_static 調(diào)度策略的模型，并在OMPi 編譯器中進(jìn)行編碼。實(shí)驗(yàn)結(jié)果表明，該策略在負(fù)載均衡的基礎(chǔ)上實(shí)現(xiàn)了負(fù)載的靜態(tài)分配，與靜態(tài)調(diào)度、動(dòng)態(tài)調(diào)度、指導(dǎo)調(diào)度等策略相比，其總體執(zhí)行時(shí)間縮短了5%～10%。后續(xù)將在處理非線性循環(huán)結(jié)構(gòu)時(shí)采用迭代編譯方法獲得關(guān)鍵信息，同時(shí)重新劃分迭代塊的大小進(jìn)行二次編譯，進(jìn)一步提高負(fù)載的均衡性。