一種針對線性循環結構的非線性靜態調度策略

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

（1.鄭州大學中原網絡安全研究院，鄭州 450001；2.中國人民解放軍戰略支援部隊信息工程大學數學工程與先進計算國家重點實驗室，鄭州 450001；3.中國人民解放軍戰略支援部隊信息工程大學，鄭州 450001）

0 概述

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

為充分發揮多核處理器的計算潛力，并行編程模型應運而生，其中OpenMP 規范［1］對現有編程語言進行了擴展，為軟件開發人員提供簡單、高效的編程接口，成為應用最廣泛的多線程編程模型。OpenMP 是一組由計算機硬件和軟件供應商聯合定義的應用程序接口（API）［1］，OpenMP 標準規范于1997 年首次發布，最新版本為V5.0，為基于共享內存并行程序的開發人員提供一種可擴展的編程模型，目前在主流的編譯器中都具有相關技術支持。在OpenMP 線程執行模式下，當程序開始時單一主線程串行執行，當程序執行到并行區域時派生出一組分支線程和主線程并行執行，離開并行區域后所有線程進行同步并且自動結束，最后程序只剩一個單獨的主線程，繼續串行執行。

針對不同的循環結構，OpenMP 規范提供了多種調度策略，但都存在不同程度的調度開銷和負載均衡問題，最終影響熱點循環在目標機器上的執行效率。為盡可能地減少調度開銷，使得各個處理器負載趨于均衡，軟件開發人員需要根據循環特征在調度開銷和負載均衡之間進行權衡，找到合適的調度策略。

本文提出一種針對線性循環結構的調度策略Nonlinear_static，結合線性負載均勻變化參數與總負載、負載峰值、線程數構建Nonlinear_static 調度模型，通過該模型計算每個迭代塊的大小使其呈現非線性遞增或遞減趨勢，并在開源OMPi 編譯器上編碼實現Nonlinear_static 調度策略，從而消除調度開銷并實現負載的均衡分配。

1 相關工作

1.1 循環結構

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

圖1 4 種循環結構Fig.1 Four loop structures

從圖1（a）可以看出，規則循環結構的負載L（i）在迭代索引i上的分布是均勻不變的。隨機循環結構的負載L（i）在迭代索引i上隨機分布，沒有規律。遞增循環結構和遞減循環結構的負載L（i）在循環索引i上呈線性遞增和線性遞減趨勢。4 種循環結構基本包括絕大部分的應用場景，其中隨機循環結構、遞增循環結構和遞減循環結構稱為非規則循環結構［4］，而遞增循環結構和遞減循環結構又稱線性循環結構。

1.2 OpenMP 循環調度策略

在共享存儲體系結構中，調度開銷和負載均衡是循環級并行化面臨的重要問題。不同的調度策略針對特定循環的效果有好有壞，沒有任何一種調度策略能夠解決所有的循環調度問題［5］，關鍵在于找到適合目標循環特征的調度策略。

目前，OpenMP 規范中提供了4 種標準的調度策略，分別是靜態調度（static）、動態調度（dynamic）、指導調度（guided）以及運行時調度（runtime），其中運行時調度根據環境變量動態選擇前3 種中的1 種，環境變量由程序員提前指定。

靜態調度在默認情況下將循環迭代劃分為大小相等的塊，每個線程分到的迭代塊值chunksize（線程分到迭代塊的大小）等于P/N（N代表循環總的迭代數，P代表使用的線程數），當無法整除時會盡可能平均分配。靜態調度還可以指定chunksize 值，在這種情況下，每個線程依次得到chunksize 值的迭代塊，直到所有的迭代都分配完成。這種調度方法適用于規則循環結構，對于隨機循環結構和線性循環結構，不同的線程負載差距較大，負載均衡性較差［6-7］，其優點是迭代在線程上的映射編譯時已經確定，所以在運行時沒有調度開銷。

動態調度在程序運行中每個線程會申請chunksize 大小的迭代塊，當某個線程執行完任務處于空閑狀態但還有迭代未被執行時，它會再次請求chunksize 大小的迭代塊，直到所有的循環都執行完成。在默認情況下，當不指定chunksize 時，其值為1。相較于靜態調度，動態調度能夠更好地適應非規則循環結構，但其會面臨chunksize 值的抉擇，過大的塊會引起線程間的負載不均衡，過小的塊則會引起頻繁的線程調度，造成嚴重的調度開銷［8］。

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

除OpenMP 規范中標準調度策略之外，梯式調度（TSS）［3］綜合了動態調度和指導調度優點，常用于處理非規則循環。相似于動態調度，梯式調度迭代塊值的變化是線性的，與動態調度不同的是其迭代塊值下降到一定程度后將保持不變，在一定程度上緩解了動態調度和指導調度后期調度開銷大的問題。線性變化的迭代塊值使得梯式調度在面對遞增循環結構時相較于指導調度具有更優的負載均衡性。

Factoring 調度（FSS）［10］采用分段的方法處理循環迭代。在同一個段內，每個線程分配的迭代塊值是相同的，而段與段之間是線性減小的。這種方法在面對非規則循環時相較于梯式調度負載均衡性更優，但實現復雜且開銷更大。從整體上分析，Factoring 調度的迭代塊值同樣是不斷減小的，所以在處理遞減型循環時，隨著負載的不斷減小，分配到的迭代塊也是越來越小，造成嚴重的負載失衡。

針對指導調度和Factoring 調度不適用于遞減型循環的問題，文獻［12］借鑒α調度策略［11］，提出new_guided調度策略。在循環的前半段使用靜態調度，后半段使用指導調度，保證調度初期迭代塊值不至于過大，在一定程度上緩解了負載在最初幾個線程過于集中的問題。在面對遞減型循環時，new_guided 調度相較于指導調度具有更優的均衡效果，但在本質上并沒有解決現有調度策略迭代塊遞降的弊端。

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

在硬件方面，硬件感知編譯器增強調度［16］結合硬件特點和調度策略，充分發揮硬件的算力，更適用于異構平臺。

以上調度策略中N代表循環總的迭代數，P代表使用的線程數，迭代塊值代表線程分到迭代塊的值。當循環迭代數為1 000，線程數為4 時，不同調度策略的迭代塊值如表1 所示，動態調度的迭代塊值是100，指導調度最小為100。

表1 不同調度策略的迭代塊值Table 1 Chunksize of different scheduling strategies

1.3 現有調度策略

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

圖2 靜態調度和非線性靜態調度Fig.2 Static scheduling and Nonlinear_static scheduling

2 Nonlinear_static 調度策略的設計與實現

2.1 OMPi 編譯器

OMPi 編譯器［17］是由希臘約阿尼納大學的并行處理小組研發的OpenMP 編譯器，是一款輕量型、可移植的源到源C 編譯器，最新開發到了2.0.0 版本，支持OpenMP 4.0 標準。OMPi 編譯器將程序員編寫的帶有OpenMP 指導語句的C 代碼轉換為基于pthreads 等線程庫的C 代碼，然后重新調用指定的C 編譯器進行二次編譯并生成可執行文件。由于OMPi 編譯器具有輕量、結構性強、易于實現OpenMP 調度策略等特點，因此本文調度策略的設計以及實現都是基于OMPi 編譯器2.0.0 版本。

OMPi 代碼編譯示例如圖3 所示，由于是靜態調度，迭代塊值的計算在編譯階段已經完成，每個線程迭代塊的開始位置存放在指針*fiter 中，結束位置存放在指針*liter 中，各個線程按照迭代塊并行執行互不干擾并且沒有調度開銷。

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

2.2 Nonlinear_static 調度模型

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

表2 Nonlinear_static 調度模型參數說明Table 2 Parameter description of Nonlinear_static scheduling model

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

圖4 遞減循環負載分塊示意圖Fig.4 Schematic diagram of decreasing loop load block

圖5 遞增循環負載分塊示意圖Fig.5 Schematic diagram of incremental loop load block

Nonlinear_static 調度策略的目的是使得每個線程的負載量保持一致，對于遞減型循環f（i）的推導主要分為以下5 個步驟。

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

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

3）計算h（i），如式（6）所示：

4）計算lload（i）如式（7）所示：

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

同理可得當循環為線性遞增型循環時，f（i）如式（9）所示：

式（4）表明每個線程的負載lload（i）需要等于理論上的平均負載，式（7）用于計算線程i根據本文提出的調度策略分配到的負載值。通過以上計算就可以得到f（i），f（i）是Nonlinear_static 調度策略劃分迭代塊的依據，不同的線程獲得不同大小的f（i），但對應到負載上每個線程是嚴格均衡的。在代碼實現中，當計算結果不是整數時，處理方法是向下取整。

2.3 Nonlinear_static 調度實現

本文在OMPi 編譯器中編碼實現一種不同于傳統靜態調度的非線性靜態調度策略，具有沒有調度開銷以及高數據局部性的優點。Nonlinear_static 調度按照f（i）進行迭代塊的劃分使得每個線程的負載總是等于avg_load，保證負載的均衡性。

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

在Nonlinear_static 調度模型中計算每個線程迭代塊的大小f（i），作為分塊的依據，但在調度策略代碼實現中，還需要知道迭代塊首尾索引的值，即為*fiter、*liter 賦值。sstart（i）為線程i分配到迭代塊的開始索引，推導主要用到2.2 節中的變量。

1）當循環為線性遞減循環時，sstart（i）如式（10）所示：

2）當循環為線性遞增循環時，sstart（i）如式（11）所示：

從f（i）以及sstart（i）的計算結果得到*fiter 和*liter的值，*fiter=start（i），*liter=*fiter+f（i）。Nonlinear_static調度策略是一種靜態調度，本文在OpenMP 標準靜態調度的基礎上進行實現的，總迭代數的獲取如圖6所示，Nonlinear_static 偽代碼如圖7 所示，其中myid對應線程i，fi 對應f（i），start 對應開始索引sstart（i）。為保證計算的精確度，中間變量都定義為浮點型數據。

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

圖7 Nonlinear_static 調度的偽代碼Fig.7 Pseudocode of Nonlinear_static scheduling

3 實驗與結果分析

3.1 實驗環境

本文采用戴爾Power Edge T640 服務器作為實驗平臺，具有2 個Intel?Xeon?Silver 4110 CPU，2 個CPU 有8 個核心，共16 核心，主頻為2.10 GHz，內存為128 GB。操作系統使用Ubuntu16.04，編譯器采用GCC 7.1.0 版本，優化選項-O3，OMPi 編譯器使用最新的2.0.0 版本。

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

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

本文實驗主要研究4 種測試用例中的熱點循環部分，針對整個熱點循環從開始執行到執行完畢的時間，計時操作使用OpenMP 提供的函數omp_get_wtime（），該函數返回1 個雙精度浮點值，等于經過的時間（以s 為單位）。

3.2 實驗結果分析

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

表3 測試用例串行執行時間Table 3 Serial execution time of test case s

3.2.1 AC 程序并行執行結果

AC 是線性循環中的遞減型循環。AC 程序并行執行時間如表4 所示，不同調度策略的AC 程序并行執行時間對比如圖9 所示。從表4 和圖9 可以看出，表現最差的是靜態調度和指導調度。靜態調度把循環迭代均勻分割在各個線程，造成負載在最先分配的線程上最多，最后分配的線程上最少。指導調度由于迭代塊是指數下降的，負載的不均衡度更大。表現較優的是動態調度和new_guided 調度，線程動態申請迭代塊，減少了線程的等待，使得線程一直處于工作狀態。根據文獻［20］的實驗數據，梯式調度的效果與new_guided 調度相當。表現最優的是Nonlinear_static 調度，與動態調度和指導調度相比，Nonlinear_static 調度具有更優的負載均衡且沒有調度開銷。

表4 AC 程序并行執行時間Table 4 Parallel execution time of AC program s

圖9 不同調度策略的AC 程序并行執行時間對比Fig.9 Parallel execution time comparison of AC program among different scheduling strategies

3.2.2 CP 程序并行執行結果

CP 程序并行執行時間如表5 所示，不同調度策略的CP 程序并行執行時間對比如圖10 所示。從表5 和圖10 可以看出，對于CP 的遞增型循環結構，靜態調度表現最差，指導調度略弱于動態調度和new_guided 調度，根據文獻［20］的實驗數據，梯式調度的效果與動態調度相當，Nonlinear_static 調度表現最優。

表5 CP 程序并行執行時間Table 5 Parallel execution time of CP program s

圖10 不同調度策略的CP 程序并行執行時間對比Fig.10 Parallel execution time comparison of CP program among different scheduling strategies

3.2.3 MS 與MM 程序并行執行時間

MS隨機循環結構的并行執行時間如表6所示，MM規則循環結構并行執行時間如表7 所示。從表6 和表7可以看出，表現最優的是動態調度、指導調度以及new_guided調度。隨機循環結構負載分布是隨機變化，因此，需要動態分配迭代塊才能實現負載均衡，靜態調度以及Nonlinear_static 調度的迭代塊分配在編譯過程中已經確定了，所以表現最差。在面對規則循環時，Nonlinear_static調度的表現也是最差的。根據文獻［20］的實驗數據，梯式調度在面對隨機循環結構時效果優于new_guided 調度，在處理規則循環結構時表現出與動態調度相同的效果。

表6 MS 程序并行執行時間Table 6 Parallel execution time of MS program s

表7 MM 程序并行執行時間Table 7 Parallel execution time of MM program s

不同調度策略的本質是對chunksize 劃分不同，循環結構的負載分布是變化的，因此會造成線程分配到的負載量難以明確，反映到OpenMP 調度模型上使得先執行完任務的線程，并等待未執行完任務的線程進行同步操作，而這一步驟會降低程序整體的執行效率。從表4～表7 可以看出，對于不同的測試用例，除了靜態調度在指定chunksize 時有明顯的加速（對于規則循環是負加速）外，其他的調度策略在指定chunksize 時基本沒有大的變化。

從整體上分析，靜態調度不能有效地平衡負載，除了規則循環結構，一般情況下效果都是最差的。

指導調度的特性導致其不適合處理遞減型循環。Nonlinear_static 調度由于靜態的迭代塊劃分規則，無論是哪種類型的循環，其迭代塊的劃分是固定的，所以不適合隨機循環以及規則循環結構。在其他情況下，動態調度和指導調度性能較優，符合其動態分配迭代塊的設計原理，但額外的調度開銷使得它們在線性循環時相較于Nonlinear_static 調度效果較差。Nonlinear_static 調度相較于其他調度策略能夠更好地處理線性循環，理論與實驗結果相一致。

4 結束語

本文提出靜態調度策略Nonlinear_static 用于消除調度開銷。將線性循環負載均勻變化參數與總負載、負載峰值、線程數相結合構建Nonlinear_static 調度策略的模型，并在OMPi 編譯器中進行編碼。實驗結果表明，該策略在負載均衡的基礎上實現了負載的靜態分配，與靜態調度、動態調度、指導調度等策略相比，其總體執行時間縮短了5%～10%。后續將在處理非線性循環結構時采用迭代編譯方法獲得關鍵信息，同時重新劃分迭代塊的大小進行二次編譯，進一步提高負載的均衡性。