范會敏，李滋田

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

0 引言

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

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

1 相關工作

1.1 OpenMP 概述［1］

OpenMP［2］是共享存儲體系結構上的編程模型，是一種能夠被用于顯式指導多線程、共享內存并行的應用程序編程接口;支持多平臺，具有良好的可移植性，支持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)進行調度和分塊。本文主要是針對for循環(huán)調度進行研究。

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

1.2.1 Static 靜態(tài)調度

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

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

1.2.2 Dynamic 動態(tài)調度

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

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

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

1.2.3 Guided 指數(shù)調度

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

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

1.3 其它相關調度策略

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

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

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

2 幾種調度策略比較分析

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

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

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

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

表1 CP測試結果

表2 AC測試結果

表3 MM測試結果

表4 MS測試結果

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

3 一種新的調度策略

3.1 新調度策略的提出

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

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

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

3.2 算法描述與流程

圖3 算法原理圖

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

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

圖4 算法流程

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

4 結束語

本文首先通過實驗對OpenMP中的3種調度策略深入地分析研究，提出改進的關鍵因素是對調度塊大小size值的控制，在此基礎上提出一種結合動態(tài)調度和指數(shù)調度的新調度策略。下一步將利用現(xiàn)有的支持多核處理器的軟硬件資源，通過大量的實驗來驗證比例因子a在不同環(huán)境中的最佳取值，另外，動態(tài)調度部分和指數(shù)調度部分的兩個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)技術［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調度算法［J］.計算機工程，2011，37(6):68-70.

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

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

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

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

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