范會敏，李滋田

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

0 引言

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

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

1 相關(guān)工作

1.1 OpenMP 概述［1］

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

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

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

1.2 OpenMP中的負載均衡策略

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

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

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

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

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

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

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

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

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

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

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

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

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

在循環(huán)調(diào)度方面，學術(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)度)外，針對不同的研究重點還提出了各種不同的調(diào)度方案。

new-guided調(diào)度［6］是一種啟發(fā)式的a調(diào)度策略，它將靜態(tài)調(diào)度和指數(shù)調(diào)度相結(jié)合。a是一個比率值，對于前面a的循環(huán)迭代，采用靜態(tài)調(diào)度;對于后面1-a的循環(huán)迭代，采用傳統(tǒng)的指數(shù)調(diào)度。參數(shù)a的取值不是一成不變的，隨著應(yīng)用程序的不同和測試環(huán)境的不同，參數(shù)a的最優(yōu)值也會變化。TSS策略［7］不是采用改變指數(shù)調(diào)度循環(huán)塊指數(shù)遞減的方式，而是采用算法使每次調(diào)度時循環(huán)塊線性減少。TSS調(diào)度通過線程數(shù)、循環(huán)體的類型和大小以及運行時的環(huán)境狀態(tài)等因素確定線性減少比率，而后每次調(diào)用循環(huá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)度的缺點。文獻［9］提出一種反饋型Guided調(diào)度，在處理小規(guī)模的循環(huán)數(shù)據(jù)時能夠有效減少調(diào)度開銷。文獻［10］則針對TSS調(diào)度提出了一種改進方案，根據(jù)處理單元的可用量分配循環(huán)塊，對于解決TSS處理不規(guī)則循環(huán)時的問題起到了一定的作用。

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

通過循環(huán)數(shù)和計算量之間的關(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)和隨機循環(huán)結(jié)構(gòu)。遞增循環(huán)結(jié)構(gòu)是指隨著循環(huán)變量的增加(或減少)，每次循環(huán)的工作量也隨著增加(或減少);遞減循環(huán)結(jié)構(gòu)是指隨著循環(huán)變量的增加(或減少)，每次循環(huán)的工作量隨著減少(或增加);隨機循環(huán)結(jié)構(gòu)是指每次循環(huán)的工作量的變化與循環(huán)變量的變化沒有直接的聯(lián)系。

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

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

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

表1 CP測試結(jié)果

表2 AC測試結(jié)果

表3 MM測試結(jié)果

表4 MS測試結(jié)果

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

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

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

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

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

負載均衡調(diào)度策略的發(fā)展歷程在一定程度上就是調(diào)度開銷和負載平衡之間的相互妥協(xié)，而多數(shù)改進策略也是圍繞這一點展開研究。文獻［6］提出的New-guided調(diào)度對于Guided調(diào)度的一個最大的優(yōu)點是解決了Guided調(diào)度在遞減循環(huán)結(jié)構(gòu)中由于開始循環(huán)塊過大而可能導致的負載不平衡。然而，Newguided調(diào)度并不是完美的，由于它是結(jié)合了靜態(tài)調(diào)度和Guided調(diào)度的一種策略，所以必然也繼承了靜態(tài)調(diào)度負載不平衡的缺點。針對這個問題，本文提出利用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代表一個百分比值。

3.2 算法描述與流程

圖3 算法原理圖

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

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

圖4 算法流程

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

4 結(jié)束語

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

［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］.長春:吉林大學，2011.

［3］羅秋明，明仲，劉剛，等.OpenMP編譯原理及實現(xiàn)技術(shù)［M］.北京:清華大學出版社，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］.計算機工程，2011，37(6):68-70.

［6］劉勝飛，張云泉，孫相征.一種改進的OpenMP指導調(diào)度策略研究［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多線程負載均衡調(diào)度策略研究與實現(xiàn)［J］.計算機科學，2010，37(11):148-151，183.

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

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

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

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