[發(fā)明專利]一種針對隨機循環(huán)負載均衡的OpenMP靜態(tài)調度方法

在審

• 申請?zhí)枺?/td>: 202210968158.2
• 申請日: 2022-08-12
• 公開（公告）號: CN115344367A
• 公開（公告）日: 2022-11-15
• 發(fā)明（設計）人: 魏貴義;周詠清;張繼發(fā)
• 申請（專利權）人: 浙江工商大學
• 主分類號: G06F9/48
• 分類號: G06F9/48;G06F9/50;G06F8/41;G06F8/30
• 代理公司: 杭州奧創(chuàng)知識產(chǎn)權代理有限公司 33272
• 代理人: 王佳健

本發(fā)明公開了一種針對隨機循環(huán)負載均衡的OpenMP靜態(tài)調度方法。本發(fā)明在在linux環(huán)境下進行OMPi編譯器的配置后，將計算程序中的隨機循環(huán)部分隔離出來。再用迭代編譯的思想，獲取每一個循環(huán)迭代內的執(zhí)行時間，并用執(zhí)行時間來表征隨機循環(huán)所含有的負載。然后根據(jù)獲取的負載信息和實際運行所需要的線程數(shù)目，求得隨機循環(huán)中每一次迭代的負載、總負載以及平均負載，計算每一個線程分配到迭代塊的開始和結束索引，將開始和結束索引值分別存放在對應指針中。最后更改編譯器中關于OpenMP調度的代碼，實現(xiàn)調度策略。本發(fā)明克服了預運行帶來額外時間開銷的缺點，沒有調度開銷，實現(xiàn)了負載均衡，加快程序的執(zhí)行效率。

技術領域

本發(fā)明涉及多線程下負載均衡的OpenMP靜態(tài)調度領域，具體涉及一種針對隨機循環(huán)的基于迭代編譯的靜態(tài)調度方法。

背景技術

OpenMP是基于編譯指示的共享存儲多線程并行編程模型，由于其簡單以及高效的特點，得到了GCC、ICC、LLVM等主流編譯器的支持，是當前線程級并行編程的主要手段。OpenMP針對隨機循環(huán)并行化提供了三種標準調度策略，分別是static靜態(tài)調度、dynamic動態(tài)調度、guided指導調度。但對于一些特定的隨機循環(huán)模式，已有的標準調度策略難以同時滿足較好的負載均衡和較小的調度開銷需求?，F(xiàn)有的標準調度策略在隨機循環(huán)上存在諸多不足，例如：動態(tài)調度以及變種方法對于隨機循環(huán)，最常見的處理方法是使用dynamic動態(tài)調度，通過不斷請求固定大小的迭代塊來平衡線程間的負載；使用自適應調度的方法，建立一個任務隊列，每個線程都從隊列中取迭代塊，當任務執(zhí)行完后再次取迭代塊，直到任務隊列中沒有任務；使用任務偷取的思想，當某一個線程執(zhí)行完任務后，其狀態(tài)會轉變成空閑線程，空閑線程則會偷取忙碌線程的一部分任務，進而繼續(xù)保持忙碌狀態(tài)，直到所有任務執(zhí)行完畢。靜態(tài)調度均分循環(huán)迭代會造成不同線程負載差距巨大，拖慢了整體的執(zhí)行效率。指導調度由于迭代塊越來越小，負載集中在前、中部分線程內，顯然是負載不均衡的。

上述調度方法的核心思想并不復雜，通常是先根據(jù)線程數(shù)量進行一個初始劃分，然后在程序執(zhí)行的過程中動態(tài)分配剩余的負載，通過頻繁的迭代塊分配來換取負載的均衡。從效果上來看，上面所提到調度方法在面對大型程序時能夠很好的處理負載，缺點是引入了新的操作(取迭代塊、任務隊列、任務偷取)，有一定程度的調度開銷，本質上是用調度開銷換取負載均衡。

發(fā)明內容

為了解決隨機循環(huán)采用動態(tài)調度策略時調度開銷大的問題，本發(fā)明提出了一種針對隨機循環(huán)負載均衡的OpenMP靜態(tài)調度方法(Dual_static)。通過預運行獲取循環(huán)迭代的負載信息，對隨機循環(huán)的任務進行再分配，設計了滿足隨機循環(huán)負載均衡的調度策略。

本發(fā)明主要包含以下步驟：

步驟1，在linux環(huán)境下進行OMPi編譯器的配置。

步驟2，使用代碼隔離的方法，將計算程序中的隨機循環(huán)部分隔離出來。并在關鍵變量的前面添加volatile關鍵字，以防止編譯器通過自動優(yōu)化將隨機循環(huán)識別成死代碼。

步驟3，用迭代編譯的思想，在隨機循環(huán)的內部插入節(jié)拍數(shù)計時函數(shù)，獲取每一個循環(huán)迭代內的執(zhí)行時間，并用執(zhí)行時間來表征隨機循環(huán)所含有的負載。為了減少獲取負載信息所付出的代價，在隨機循環(huán)預運行記錄負載信息時，采用靜態(tài)調度的方式多線程運行。此調度策略會自動獲取目標平臺的核心數(shù)目，并以最大核心數(shù)作為靜態(tài)調度的線程數(shù)，循環(huán)執(zhí)行完畢后輸出時間信息，即負載信息。

步驟4，根據(jù)獲取的負載信息和實際運行所需要的線程數(shù)目計算平均負載，即avg_load＝load/p。將隨機循環(huán)迭代塊劃分成p個塊，每一個塊所含有的負載均等于平均負載avg_load。求得隨機循環(huán)中每一次迭代的負載time(i)、總負載load以及平均負載avg_load。

步驟5，根據(jù)步驟4得到的每一次迭代的負載time(i)、總負載load以及平均負載avg_load，計算每一個線程分配到迭代塊的開始索引start(i)以及結束索引end(i)。