基于OpenMP的多線程負(fù)載均衡調(diào)度策略

范會(huì)敏，李滋田

(西安工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，陜西 西安 710032)

0 引言

2005年4月，Intel公司推出雙核處理器，率先揭開了多核時(shí)代的帷幕。時(shí)至今日，多核處理器已經(jīng)成為處理器領(lǐng)域的主流。多核處理器通過劃分任務(wù)，使線程應(yīng)用能夠充分利用多個(gè)執(zhí)行內(nèi)核，可在特定的時(shí)間內(nèi)執(zhí)行更多任務(wù)，從而提高性能。

研究多核技術(shù)的一個(gè)重要問題是負(fù)載平衡。如果能通過調(diào)度策略將并行程序中的并行任務(wù)合理地劃分并分配到各個(gè)處理器上，盡量減少處理器間的負(fù)載不平衡性，那么在軟件方面就能有效地提高程序的運(yùn)行效率，在硬件方面也能發(fā)揮多核的優(yōu)勢(shì)。本文對(duì)OpenMP環(huán)境下的負(fù)載均衡算法進(jìn)行深入研究，并針對(duì)這些算法的缺陷，提出一種改進(jìn)調(diào)度方案。

1 相關(guān)工作

1.1 OpenMP 概述［1］

OpenMP［2］是共享存儲(chǔ)體系結(jié)構(gòu)上的編程模型，是一種能夠被用于顯式指導(dǎo)多線程、共享內(nèi)存并行的應(yīng)用程序編程接口;支持多平臺(tái)，具有良好的可移植性，支持Fortran/C/C++等多種編程語言。

OpenMP使用Fork-Join并行執(zhí)行模型［3］。當(dāng)程序開始執(zhí)行的時(shí)候只有一個(gè)叫做主線程存在，如圖1所示。主線程會(huì)一直串行地執(zhí)行，直到遇見第一個(gè)并行域(Parallel Region)才開始并行執(zhí)行。當(dāng)遇到需要進(jìn)行并行運(yùn)算時(shí)，主線程創(chuàng)建一隊(duì)并行的線程，并行域中的代碼在不同的線程隊(duì)中并行執(zhí)行;當(dāng)派生出的線程在并行域中執(zhí)行完之后，它們退出或者掛起，最后只有主線程在執(zhí)行。

圖1 Fork-Join并行執(zhí)行模型

1.2 OpenMP中的負(fù)載均衡策略

負(fù)載均衡是影響OpenMP多線程程序運(yùn)行性能的重要因素［4］，為了實(shí)現(xiàn)較好的負(fù)載平衡從而取得更好的性能，就必須對(duì)循環(huán)進(jìn)行調(diào)度和分塊。本文主要是針對(duì)for循環(huán)調(diào)度進(jìn)行研究。

在OpenMP中針對(duì)for循環(huán)的調(diào)度，主要有4種調(diào)度方式［3］:Static靜態(tài)調(diào)度、Dynamic動(dòng)態(tài)調(diào)度、Guided指數(shù)調(diào)度和Runtime運(yùn)行時(shí)調(diào)度。Runtime調(diào)度實(shí)際上是根據(jù)OpenMP中的環(huán)境變量OMP_SCHEDULED來選擇前3種的某一種類型，所以本文不做討論。

1.2.1 Static 靜態(tài)調(diào)度

靜態(tài)調(diào)度的原理非常簡(jiǎn)單，就是將循環(huán)的迭代以近乎平均的方式分布到各個(gè)線程上。如果有1000次迭代，線程組中有4個(gè)線程，那么每個(gè)線程將分配250次迭代。當(dāng)不能整除時(shí)，將余數(shù)次的迭代依次分配給最后一個(gè)線程。

靜態(tài)調(diào)度具有最小的調(diào)度開銷，然而，由于靜態(tài)調(diào)度是按循環(huán)次數(shù)平均劃分，沒有考慮到每次任務(wù)的大小可能不一樣，所以，靜態(tài)調(diào)度不能獲得較好的負(fù)載平衡。

1.2.2 Dynamic 動(dòng)態(tài)調(diào)度

與靜態(tài)調(diào)度不同，動(dòng)態(tài)調(diào)度不是按順序?qū)⒏鱾€(gè)(或各組)迭代分配到各個(gè)線程，而是在程序執(zhí)行過程中，某個(gè)線程完成了一個(gè)(或一組)迭代后，動(dòng)態(tài)申請(qǐng)下一個(gè)(或下一組)迭代進(jìn)行執(zhí)行。

動(dòng)態(tài)調(diào)度可以分為指定chunksize參數(shù)和沒有指定chunksize參數(shù)。當(dāng)沒有使用chunksize參數(shù)時(shí)，線程在完成上一任務(wù)后動(dòng)態(tài)申請(qǐng)一個(gè)循環(huán)迭代并執(zhí)行;當(dāng)指定chunksize參數(shù)時(shí)，可以認(rèn)為每次分配給線程的迭代次數(shù)為指定的chunksize值。

各線程動(dòng)態(tài)地申請(qǐng)任務(wù)，因此較快的線程可能申請(qǐng)更多次數(shù)，而較慢的線程申請(qǐng)任務(wù)次數(shù)可能較少，因此，動(dòng)態(tài)調(diào)度可以在一定程度上避免前面提到的按循環(huán)次數(shù)劃分引起的負(fù)載不平衡問題。

1.2.3 Guided 指數(shù)調(diào)度

Guided調(diào)度是一種采用指導(dǎo)性的啟發(fā)式自調(diào)度方法，它的調(diào)度規(guī)則是將迭代空間劃分為子塊，并按動(dòng)態(tài)調(diào)度的方法調(diào)度各個(gè)子塊的執(zhí)行，子塊的大小按指數(shù)遞減。在開始時(shí)線程將會(huì)分配到較大的迭代塊，之后分配到的迭代塊會(huì)逐漸遞減，直至指定的chunksize大小。

讓chunksize的值由大到小指數(shù)型遞減，從一定程度上緩解chunksize值不好指定的問題，因此，指數(shù)調(diào)度可以視作動(dòng)態(tài)調(diào)度在調(diào)度開銷和負(fù)載平衡上的折中。然而，如果循環(huán)結(jié)構(gòu)極不規(guī)則［5］，那么在開始時(shí)分配的任務(wù)塊可能過大以至于后續(xù)分配的任務(wù)塊沒有足夠的任務(wù)量來緩和所引起的負(fù)載不均衡性。

1.3 其它相關(guān)調(diào)度策略

在循環(huán)調(diào)度方面，學(xué)術(shù)界提出了很多循環(huán)調(diào)度的算法。除了PSS調(diào)度(類似于無參數(shù)的Dynamic調(diào)度)、CSS調(diào)度(類似于有參數(shù)的Dynamic調(diào)度)、GSS調(diào)度(類似于Guided調(diào)度)外，針對(duì)不同的研究重點(diǎn)還提出了各種不同的調(diào)度方案。

new-guided調(diào)度［6］是一種啟發(fā)式的a調(diào)度策略，它將靜態(tài)調(diào)度和指數(shù)調(diào)度相結(jié)合。a是一個(gè)比率值，對(duì)于前面a的循環(huán)迭代，采用靜態(tài)調(diào)度;對(duì)于后面1-a的循環(huán)迭代，采用傳統(tǒng)的指數(shù)調(diào)度。參數(shù)a的取值不是一成不變的，隨著應(yīng)用程序的不同和測(cè)試環(huán)境的不同，參數(shù)a的最優(yōu)值也會(huì)變化。TSS策略［7］不是采用改變指數(shù)調(diào)度循環(huán)塊指數(shù)遞減的方式，而是采用算法使每次調(diào)度時(shí)循環(huán)塊線性減少。TSS調(diào)度通過線程數(shù)、循環(huán)體的類型和大小以及運(yùn)行時(shí)的環(huán)境狀態(tài)等因素確定線性減少比率，而后每次調(diào)用循環(huán)體大小按比率減少。

另外，文獻(xiàn)［8］提出了FSS(Factoring Self-Scheduling)調(diào)度。該方案將循環(huán)迭代分成若干段，每段內(nèi)部采用Dynamic調(diào)度。這種調(diào)度能夠有效緩解Guided調(diào)度不適合極不規(guī)則的循環(huán)調(diào)度的缺點(diǎn)。文獻(xiàn)［9］提出一種反饋型Guided調(diào)度，在處理小規(guī)模的循環(huán)數(shù)據(jù)時(shí)能夠有效減少調(diào)度開銷。文獻(xiàn)［10］則針對(duì)TSS調(diào)度提出了一種改進(jìn)方案，根據(jù)處理單元的可用量分配循環(huán)塊，對(duì)于解決TSS處理不規(guī)則循環(huán)時(shí)的問題起到了一定的作用。

2 幾種調(diào)度策略比較分析

通過循環(huán)數(shù)和計(jì)算量之間的關(guān)系可以將for循環(huán)結(jié)構(gòu)分為兩大類:規(guī)則循環(huán)結(jié)構(gòu)和非規(guī)則循環(huán)結(jié)構(gòu)。規(guī)則循環(huán)結(jié)構(gòu)是指隨著循環(huán)變量的增加(或減少)，每次循環(huán)的工作量沒有變化。非規(guī)則循環(huán)結(jié)構(gòu)又分為遞增循環(huán)結(jié)構(gòu)、遞減循環(huán)結(jié)構(gòu)和隨機(jī)循環(huán)結(jié)構(gòu)。遞增循環(huán)結(jié)構(gòu)是指隨著循環(huán)變量的增加(或減少)，每次循環(huán)的工作量也隨著增加(或減少);遞減循環(huán)結(jié)構(gòu)是指隨著循環(huán)變量的增加(或減少)，每次循環(huán)的工作量隨著減少(或增加);隨機(jī)循環(huán)結(jié)構(gòu)是指每次循環(huán)的工作量的變化與循環(huán)變量的變化沒有直接的聯(lián)系。

本文通過一個(gè)實(shí)驗(yàn)來具體比較幾種調(diào)度策略的性能。實(shí)驗(yàn)是在Linux系統(tǒng)下進(jìn)行，使用的是OMPi編譯器，版本是OMPi-1.2.0。通過使用 gettimeofday()函數(shù)可以獲得UNIX到現(xiàn)在的是時(shí)間，單位可以精確到微秒。通過在每個(gè)for循環(huán)結(jié)構(gòu)的開始位置與結(jié)束位置分別插入gettimeofday()［11］函數(shù)，計(jì)算出時(shí)間差即為該運(yùn)行循環(huán)結(jié)構(gòu)的時(shí)間，這個(gè)時(shí)間將隨著循環(huán)結(jié)構(gòu)和調(diào)度策略的更改而變化，從而反應(yīng)出每個(gè)調(diào)度策略的特點(diǎn)。

在本次試驗(yàn)中，將分別對(duì)4種循環(huán)結(jié)構(gòu)進(jìn)行試驗(yàn)，以取得更加全面的實(shí)驗(yàn)結(jié)果。本文采用經(jīng)典的CP(Compute Pots)程序、AC(Adjoint Convolution)程序、MM(Matrix Multiplication)程序和 MS(Mandelbrot Set)程序進(jìn)行測(cè)試。其中，CP程序?qū)儆谶f增循環(huán)結(jié)構(gòu)，用于計(jì)算三維空間中的3000個(gè)點(diǎn)的某種場(chǎng)勢(shì);AC屬于遞減循環(huán)結(jié)構(gòu)，用于計(jì)算向量卷積，循環(huán)規(guī)模是200×200;MM程序?qū)儆谝?guī)則循環(huán)結(jié)構(gòu)，用于計(jì)算浮點(diǎn)矩陣乘法，循環(huán)規(guī)模是250×250;MS程序?qū)儆陔S機(jī)循環(huán)結(jié)構(gòu)，用于計(jì)算復(fù)平面上的曼德布洛特集合，循環(huán)規(guī)模是500×500。

測(cè)試結(jié)果(單位為毫秒)如表1至表4所示。

表1 CP測(cè)試結(jié)果

表2 AC測(cè)試結(jié)果

表3 MM測(cè)試結(jié)果

表4 MS測(cè)試結(jié)果

從上述實(shí)驗(yàn)結(jié)果可以看出，在3種循環(huán)調(diào)度中，static調(diào)度在各種調(diào)度中表現(xiàn)最差，dynamic調(diào)度由于其較好的靈活性，在每次循環(huán)的工作量不確定的隨機(jī)循環(huán)調(diào)度中獲得較好的性能;guided調(diào)度在遞減循環(huán)結(jié)構(gòu)和隨機(jī)循環(huán)結(jié)構(gòu)中，由于其開始時(shí)分配的循環(huán)塊過大，引起了負(fù)載極不平衡，從而性能較差。

3 一種新的調(diào)度策略

3.1 新調(diào)度策略的提出

影響OpenMP中調(diào)度策略性能的關(guān)鍵因素［12］是調(diào)度開銷和負(fù)載平衡，從最初簡(jiǎn)單的靜態(tài)調(diào)度到現(xiàn)在的TSS調(diào)度和New-guided調(diào)度，都是在調(diào)度開銷和負(fù)載平衡之間的不斷權(quán)衡。在保證較低調(diào)度開銷的同時(shí)保證各任務(wù)負(fù)載平衡一直是研究者研究的主要問題。調(diào)度開銷和負(fù)載平衡與size值息息相關(guān)，從圖2各種調(diào)度算法的發(fā)展歷程圖中可以看出，size值是變化還是不變化、以線性的變化還是非線性的變化，貫穿了所有調(diào)度策略的始終，所以較好地對(duì)size值的控制是優(yōu)化和改進(jìn)調(diào)度策略的關(guān)鍵。

圖2 調(diào)度算法的發(fā)展歷程圖

負(fù)載均衡調(diào)度策略的發(fā)展歷程在一定程度上就是調(diào)度開銷和負(fù)載平衡之間的相互妥協(xié)，而多數(shù)改進(jìn)策略也是圍繞這一點(diǎn)展開研究。文獻(xiàn)［6］提出的New-guided調(diào)度對(duì)于Guided調(diào)度的一個(gè)最大的優(yōu)點(diǎn)是解決了Guided調(diào)度在遞減循環(huán)結(jié)構(gòu)中由于開始循環(huán)塊過大而可能導(dǎo)致的負(fù)載不平衡。然而，Newguided調(diào)度并不是完美的，由于它是結(jié)合了靜態(tài)調(diào)度和Guided調(diào)度的一種策略，所以必然也繼承了靜態(tài)調(diào)度負(fù)載不平衡的缺點(diǎn)。針對(duì)這個(gè)問題，本文提出利用Dynamic調(diào)度替換靜態(tài)調(diào)度，即將Dynamic調(diào)度和Guided結(jié)合的一種啟發(fā)式的新的調(diào)度策略。這種策略前a部分用 Dynamic調(diào)度，后面1-a部分應(yīng)用Guided調(diào)度，本文稱為Dynamic-guided調(diào)度，其中比例因子a代表一個(gè)百分比值。

3.2 算法描述與流程

圖3 算法原理圖

如圖3所示，Dynamic-guided調(diào)度算法將所有待處理的for循環(huán)分為兩部分。對(duì)于前一部分for循環(huán)，首先，編譯器根據(jù)參數(shù)chunksize和step的大小計(jì)算第一個(gè)循環(huán)塊的大小，其中step指循環(huán)步長(zhǎng)，即每線程每次執(zhí)行for循環(huán)代碼的最小單位，在多數(shù)情況下循環(huán)步長(zhǎng)step為1，chunksize是由用戶指定的參數(shù);然后，已經(jīng)由編譯器編號(hào)的各線程將調(diào)用并執(zhí)行循環(huán)塊，每個(gè)線程每次調(diào)用一個(gè)循環(huán)塊，除最后一個(gè)循環(huán)塊外其余循環(huán)塊的大小相等。各個(gè)線程的調(diào)用并不是依次執(zhí)行，而是按需進(jìn)行，即當(dāng)一個(gè)線程空閑時(shí)就調(diào)用下一個(gè)循環(huán)塊，而不是事先將所有的調(diào)度都分配好，這樣可以更加有效地利用處理器資源。對(duì)于后一部分for循環(huán)，與前面一樣，編譯器會(huì)根據(jù)剩余的未調(diào)度的循環(huán)迭代數(shù)Last_chunksize與線程個(gè)數(shù)Num_thread等參數(shù)確定第一塊循環(huán)塊的大小，之后各個(gè)線程將調(diào)用循環(huán)塊，第一塊循環(huán)之后的所有循環(huán)塊的大小都是按照該算法確定。循環(huán)塊大小按指數(shù)遞減，直到減至用戶指定的chunksize大小，剩余小于chunksize的迭代由一個(gè)線程一次調(diào)用完成。

令Fchunksize表示for循環(huán)中前一部分的剩余迭代數(shù)，Lchunksiz表示后一部分的剩余迭代數(shù)，它們的初始值可分別由總的迭代總數(shù)乘以百分比值a或1-a得出，算法流程圖如圖4所示。

圖4 算法流程

Dynamic-guided調(diào)度是一種結(jié)合了動(dòng)態(tài)調(diào)度和指數(shù)調(diào)度的混合型調(diào)度策略，可以通過控制百分比a的值來適應(yīng)不同的環(huán)境，具有較好的靈活性。一方面，它能夠很好地繼承動(dòng)態(tài)調(diào)度和指數(shù)調(diào)度的優(yōu)點(diǎn)，相比靜態(tài)調(diào)度，能夠更有效地利用線程資源，緩解出現(xiàn)由各線程處理速度不同和各個(gè)迭代計(jì)算量的不同所引起的負(fù)載不平衡。另一方面，算法前一部分采用動(dòng)態(tài)調(diào)度，所以在極不規(guī)則循環(huán)結(jié)構(gòu)中也比單純使用指數(shù)調(diào)度更具優(yōu)勢(shì)，后一部分迭代采用guided調(diào)度，能有效解決單純使用動(dòng)態(tài)調(diào)度時(shí)chunksize值不好指定的問題，也能夠緩解指數(shù)調(diào)度開始分配循環(huán)塊過大可能引起極大負(fù)載不平衡的缺陷。

4 結(jié)束語

本文首先通過實(shí)驗(yàn)對(duì)OpenMP中的3種調(diào)度策略深入地分析研究，提出改進(jìn)的關(guān)鍵因素是對(duì)調(diào)度塊大小size值的控制，在此基礎(chǔ)上提出一種結(jié)合動(dòng)態(tài)調(diào)度和指數(shù)調(diào)度的新調(diào)度策略。下一步將利用現(xiàn)有的支持多核處理器的軟硬件資源，通過大量的實(shí)驗(yàn)來驗(yàn)證比例因子a在不同環(huán)境中的最佳取值，另外，動(dòng)態(tài)調(diào)度部分和指數(shù)調(diào)度部分的兩個(gè)chunksize參數(shù)的取值問題將是進(jìn)一步研究的重點(diǎn)。

［1］Haoqiang Jin，Dennis Jespersen，Piyush Mehrotra，et al.High performance computing using MPI and OpenMP on multi-core parallel systems［J］.Parallel Computing，2011，37(9):562-575.

［2］王亭亭.基于OpenMP和MPI的并行算法研究［D］.長(zhǎng)春:吉林大學(xué)，2011.

［3］羅秋明，明仲，劉剛，等.OpenMP編譯原理及實(shí)現(xiàn)技術(shù)［M］.北京:清華大學(xué)出版社，2012.

［4］Da Gao，Thomas E Schwartzentruber.Optimizations and OpenMP implementation for the direct simulation Monte Carlo method［J］.Computers ＆ Fluids，2011，42(1):73-81.

［5］張延紅，史永昌，朱曉珺.非規(guī)則循環(huán)的OpenMP調(diào)度算法［J］.計(jì)算機(jī)工程，2011，37(6):68-70.

［6］劉勝飛，張?jiān)迫瑢O相征.一種改進(jìn)的OpenMP指導(dǎo)調(diào)度策略研究［J］.計(jì)算機(jī)研究與發(fā)展，2010，47(4):687-694.

［7］Tzen T H，Ni L M.Trapezoid self-scheduling:A practical scheduling scheme for parallel compilers［J］.IEEE Transactions on Parallel and Distributed Systems，1993，4(1):87-98.

［8］Hummel S F，Schonberg E，F(xiàn)lynn L E.Factoring:A method for scheme scheduling parallel loops［J］.Communications of the ACM，1992，35(8):90-101.

［9］Tabirca T，F(xiàn)reeman L，Tabirca S，et al.Feedback guided dynamic loop scheduling:A theoretical approach［C］//International Conference on Parallel Processing Workshops，2001.2001:115-121.

［10］Chronipoulos A T，Penmatsa S，Xu Jianhua，et al.Distributed loop-scheduling schemes for heterogeneous computer systems:Research articles［J］.Concurrency and Computation:Practice ＆ Experience，2006，18(7):771-785.

［11］GitHub，Inc.OMPi/runtime/ort_ws.c［DB/OL］.https://github.com/tonyseek/OMPi/blob/master/runtime/ort_ws.c，2013-10-01.

［12］任小西，唐玲，李仁發(fā).OPenMP多線程負(fù)載均衡調(diào)度策略研究與實(shí)現(xiàn)［J］.計(jì)算機(jī)科學(xué)，2010，37(11):148-151，183.

［13］賴建新，胡長(zhǎng)軍，趙宇迪，等.OpenMP任務(wù)調(diào)度開銷及負(fù)載均衡分析［J］.計(jì)算機(jī)工程，2006，32(18):58-60.

［14］陳永健.OpenMP編譯與優(yōu)化技術(shù)研究［D］.北京:清華大學(xué)，2004.

［15］劉軼，張昕，李鶴，等.一種面向多核處理器并行系統(tǒng)的啟發(fā)式任務(wù)分配算法［J］.計(jì)算機(jī)研究與發(fā)展，2009，46(6):1058-1064.

［16］余榮祖.并行進(jìn)化算法及其在組合優(yōu)化中的應(yīng)用［D］.西安:西安電子科技大學(xué)，2007.