[發(fā)明專(zhuān)利]多核集群服務(wù)器上基于依賴度的并行任務(wù)分組調(diào)度方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201310117866.6
• 申請(qǐng)日: 2013-04-07
• 公開(kāi)（公告）號(hào): CN103235742A
• 公開(kāi)（公告）日: 2013-08-07
• 發(fā)明（設(shè)計(jì)）人: 李新;賈智平;趙衍恒;謝帥
• 申請(qǐng)（專(zhuān)利權(quán)）人: 山東大學(xué)
• 主分類(lèi)號(hào): G06F9/50
• 分類(lèi)號(hào): G06F9/50
• 代理公司: 濟(jì)南圣達(dá)知識(shí)產(chǎn)權(quán)代理有限公司 37221
• 代理人: 鄭華清

1.多核集群服務(wù)器上基于依賴度的并行任務(wù)分組調(diào)度方法，其特征在于：包括以下步驟：

步驟（1）根據(jù)任務(wù)執(zhí)行參數(shù)和依賴關(guān)系得到初始執(zhí)行路徑；然后，計(jì)算每條初始執(zhí)行路徑的負(fù)載，按照負(fù)載從大到小的順序?qū)Τ跏紙?zhí)行路徑進(jìn)行排序；

步驟（2）根據(jù)給定的處理器個(gè)數(shù)，按照依賴關(guān)系安排初始執(zhí)行路徑運(yùn)行位置，即按照初始執(zhí)行路徑之間的依賴關(guān)系，將兩條或多條依賴度大的初始執(zhí)行路徑安排在同一個(gè)處理器上，組成一條優(yōu)化后的執(zhí)行路徑；

步驟（3）將處理器使用個(gè)數(shù)減1，并按照步驟（2）安排所有N條初始執(zhí)行路徑的運(yùn)行位置，尋找其它可選調(diào)度方案；

步驟（4）不斷執(zhí)行步驟（3），直到調(diào)度方案的完成時(shí)間超過(guò)允許的總體完成時(shí)間為止；在所有的可選調(diào)度方案列表中，選擇完成時(shí)間小于或等于總體完成時(shí)間約束的、節(jié)約能耗最多的一組調(diào)度方案作為最終調(diào)度。

2.如權(quán)利要求1所述的基于依賴度的并行任務(wù)分組調(diào)度方法，其特征在于：所述的步驟（1）的具體步驟如下：

（1-1）計(jì)算各個(gè)任務(wù)的執(zhí)行參數(shù)，包括最優(yōu)前驅(qū)任務(wù)、任務(wù)在依賴關(guān)系圖中的高度；

（1-2）利用計(jì)算出來(lái)的執(zhí)行參數(shù)，根據(jù)已有的任務(wù)復(fù)制調(diào)度算法，生成初始執(zhí)行路徑，并假設(shè)初始執(zhí)行路徑有N條，其中N≤總內(nèi)核數(shù)；

（1-3）計(jì)算每條初始執(zhí)行路徑的負(fù)載，即初始執(zhí)行路徑上所有任務(wù)的執(zhí)行時(shí)間總和；依據(jù)負(fù)載從大到小的順序?qū)Τ跏紙?zhí)行路徑進(jìn)行排序，并假設(shè)所有初始執(zhí)行路徑中負(fù)載最大值為最大負(fù)載為Max_Load；

（1-4）根據(jù)所用系統(tǒng)的單個(gè)處理器內(nèi)核個(gè)數(shù)，假設(shè)為K，設(shè)定最多可用處理器個(gè)數(shù)Max_CPU=生成初始執(zhí)行路徑條數(shù)/單個(gè)處理器內(nèi)核個(gè)數(shù)=N/K取上整數(shù)；設(shè)置占用處理器個(gè)數(shù)初始值M=Max_CPU。

3.如權(quán)利要求2所述的并行任務(wù)分組調(diào)度方法，其特征在于：所述的初始執(zhí)行路徑任務(wù)未分配到處理器上時(shí)，任務(wù)的初始執(zhí)行路徑由TDS、EAD或PEBD算法生成。

4.如權(quán)利要求2所述的并行任務(wù)分組調(diào)度方法，其特征在于：所述的步驟（2）的具體步驟如下：

首先將N條初始執(zhí)行路徑的前M條路徑分配到M個(gè)處理器的第一個(gè)核上，然后從第M+1條路徑開(kāi)始計(jì)算該路徑對(duì)M個(gè)處理器的依賴度，選擇依賴度最大的處理器上分配給該路徑；該路徑將運(yùn)行在依賴度最大的處理器中的空閑時(shí)間最多的內(nèi)核上；按照相同的方法，循環(huán)迭代安排第M+2至第N條路徑的運(yùn)行位置，即運(yùn)行該路徑的處理器及其內(nèi)核；當(dāng)所有N條初始執(zhí)行路徑安排完運(yùn)行位置之后，將此時(shí)處理器個(gè)數(shù)、最后一個(gè)任務(wù)完成時(shí)間和總能耗作為一種可選調(diào)度方案，添加到{處理器個(gè)數(shù)、完成時(shí)間、總能耗}列表中。

5.如權(quán)利要求1所述的并行任務(wù)分組調(diào)度方法，其特征在于：所述的步驟（3）的具體步驟如下：

不斷重復(fù)執(zhí)行步驟（3），直到調(diào)度方案的完成時(shí)間超過(guò)允許的總體完成時(shí)間為止；在所有的可選調(diào)度方案列表中，在允許的總體完成時(shí)間范圍內(nèi)，選擇節(jié)約能耗最多的一組調(diào)度方案作為最終調(diào)度。