一種改進的OpenMPGuided調(diào)度策略研究

1、 種改進的嚴 調(diào)度策略研究 表 在曙光機上的測試結(jié) 表 在刀片上的測試結(jié)果 單位：秒 果（單位：秒） 涮度策略 】 】 線程數(shù) 】 】 】 】 】 】 】 】 】 】 】 】 】 】 】 】 蒯度策略 】 】 矗 】 】 線程數(shù) 】 】 ， 目 鼢 ， ， 】 】 【 】 】 】 表 在曙光機上的測試結(jié) 果（單位：秒） 表 在刀片上的測試 結(jié)果（單位：秒 州艘策略 】 矗 矗 矗 矗 蒯度策略 】 線程數(shù) 線程數(shù) 】 】 】 】 】 ， 】 ， 坼 礬， 礬 在舊刀片上的測試結(jié)果 表 在刀片上的測試 結(jié)果（單位：秒） 劉于每一個循環(huán)結(jié)構(gòu)，我們均采用和曙光服 務(wù)器相同的調(diào)度策略進行了測試測試過程

2、中， 采用了至個線程，測試結(jié)果分別如表一表 所示。 表 州發(fā)策略 ：， 線程數(shù) ” 在刀片上的測試結(jié)果 單位：秒） ： 撕 粥 州艘策略 】 ， 】 線程數(shù) 】 礬（ 礬 實驗結(jié)果分析 從表一表可以看，不同的凋度策略和 參數(shù)在曙光服務(wù)器和刀片上對性 能的影響基本相同對于四個測試程序，默認的 ， ， 一種改進的嚴 調(diào)度策略研究 調(diào)度性能都是最差的。對于、 和凋度，參數(shù)對調(diào) 度性能的影響比較小。 程序是一個不規(guī)則的循環(huán)結(jié)構(gòu)。從表 和表可以看出，調(diào)度和（，） 進行一次凋度的開銷往往并不相同，編譯器在為 線程分配迭代塊時，一股首先鎖住所有線程共享 的任務(wù)隊列，然后在臨界區(qū)（ ）計 算需要分配的迭代塊大

3、小，并更新任務(wù)隊列，最 后解鎖。調(diào)度采用的是制導(dǎo)訂 調(diào)度可以獲得較好的性能，其次是 調(diào)度策略如圖所示，程序的迭代可以分 為前面、中間和后面三個部分。其中，在前面部 分和后面部分的迭代中，每次迭代的計算量都很 小，而中間部分的迭代的計算量都特別大對于 這樣的循環(huán)結(jié)構(gòu)，和默認的調(diào)度都 會導(dǎo)致獲得中問那部分迭代的線程作量非常 句中的參數(shù)來直接指定迭代塊大小， 而凋度則需要在每次調(diào)度時計算迭代塊 大小。也就是說，調(diào)度對應(yīng)的臨界區(qū)代 碼量少于調(diào)度的臨界區(qū)代碼量。例如在 編譯中，調(diào)度對應(yīng)的臨界區(qū)代碼為 行，而調(diào)度對應(yīng)的臨界區(qū)代碼為行 兇此，執(zhí)行一次調(diào)度的開銷要少于執(zhí)行 一次調(diào)度的開銷。但是，調(diào)度每次 分配

4、的迭代塊多于，斟此，對于同一個 程序，采用策略的調(diào)度次數(shù)要少于策略 對于表中的例子，采用策略需要進行 次調(diào)度，而采用策略只需要次調(diào)度。 如果綜合考慮一次調(diào)度的額外開銷和調(diào)度次數(shù)， 凋度和的總額外開銷近乎相似。 從表、表、表、表中的測試結(jié)果可以看出， 對遞增結(jié)構(gòu)的程序和規(guī)則的程序采用 、和調(diào)度時的性能差 不多。 大，而其它線程的作量非常小，從而導(dǎo)致嚴重 的負載不半衡。調(diào)度和（，）調(diào) 度會將計算量大的迭代和計算量小的迭代均勻 地分配給各個線程，兇此可以獲得較好的調(diào)度性 能。這兩個凋度策略的區(qū)別在于（，）在 進入循環(huán)前就將所有迭代分配完畢，而 調(diào)度則是在一個線程執(zhí)行完當前迭代塊后冉給 它分配下一個迭

5、代塊。 論文的研究指出：“如果計算負載是隨迭 代變量增大而減小的，則應(yīng)避免使用指數(shù)調(diào)度， 兇為它的前幾個子塊大小都很大，可能導(dǎo)致負載 不均衡?！睆谋淼臏y試結(jié)果可以看，遞減結(jié) 構(gòu)的程序采用（，）、和 調(diào)度時能夠獲得最佳性能，而采用 調(diào)度策略時性能較差。這一點與論文】 的結(jié)論一致、對于遞減循環(huán)結(jié)構(gòu)，計算負載隨著 迭代變量增大而減小，而策略劃分的迭代 塊大小也是由大變小，且呈指數(shù)下降兇此，對 于遞減循環(huán)結(jié)構(gòu)采用調(diào)度會導(dǎo)致前面的 迭代塊計算量非常大，而后面的迭代塊計算量非 常小，從而引起負載不半衡、在曙光服務(wù)器上 當線程數(shù)大于時，隨著線程數(shù)的增加，程 序的執(zhí)行時間沒有繼續(xù)減少、這是【于程序 訪問存儲單

6、元時具有一定的不規(guī)則性，當線程進 一步增多時，存儲訪問的局部件被破壞了 論文采用調(diào)度次數(shù)來衡量兇調(diào)度產(chǎn)生的 額外開銷，認為對遞增結(jié)構(gòu)的循環(huán)， “應(yīng)避免使 綜合表一表的測試結(jié)果可以看出，在 程序中采用策略和（，） 策略的調(diào)度性能比較好。策略劉 策略進行了改進，調(diào)度性能介于和 之間、由于調(diào)度在編譯期就決定了 各個處理器的迭代塊大小，兇此無法根據(jù)程序運 行時處理器的負載動態(tài)調(diào)整此外，當調(diào)度非規(guī) 則循環(huán)結(jié)構(gòu)或者處理器件能不一致時，調(diào)度 很容易現(xiàn)負載不半衡。如在表、表、表 中，（，）策略的調(diào)度性能就比 和策略的凋度性能差。綜合前面的分析， 我們可以認為，在大部分的情況下，策 略都能獲得最好的調(diào)度性能。

7、總結(jié)及以后的工作 隨著多核處理器的問世，多線程程序設(shè)計已 經(jīng)成為一個不可回避的問題。在采用編 用靜態(tài)調(diào)度策略和分塊大小較大的動態(tài)凋度策 略、”但是，在實際的編譯器中，不同調(diào)度策略 一種改進的嚴 調(diào)度策略研究 程時，調(diào)度策略和參數(shù)的選擇列于一個 程序的性能具有一定的影響，但選擇恰當?shù)恼{(diào)度 策略和參數(shù)往往跟具體的運行環(huán)境和循環(huán)結(jié)構(gòu) 有關(guān)。 現(xiàn)有的研究作（如文獻和）都表明， 對于遞減型的循環(huán)結(jié)構(gòu)，采用調(diào)度策略時 存在嚴重的負載不均衡問題。本文借鑒論文】 的閌度策略，對循環(huán)結(jié)構(gòu)的前的迭代采用 鬩度，后面的迭代采用調(diào)度， 從而改進了標準所指定的調(diào)度策 略。此外，針對不同的循環(huán)結(jié)構(gòu)，我們在不同的 多核處理器上對不同的調(diào)度策略進行測試和分 析。本文的進一步作可以研究調(diào)度策略在機 群系統(tǒng)中的應(yīng)用、 ， ， ， ， ，（），： 多核程設(shè)計技