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

有效

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

技術(shù)領(lǐng)域

本發(fā)明屬于高性能計(jì)算領(lǐng)域，具體涉及到集群服務(wù)器上操作系統(tǒng)中多個(gè)任務(wù)的并行調(diào)度方法，即將多個(gè)可以并行的任務(wù)分配到多個(gè)處理器執(zhí)行，從而使得所有任務(wù)的總體執(zhí)行時(shí)間或使用的處理器個(gè)數(shù)滿足要求。

背景技術(shù)

隨著高性能計(jì)算機(jī)的快速發(fā)展，大型多處理器集群系統(tǒng)的能耗越來越多，高效節(jié)能已經(jīng)成為高性能計(jì)算必須考慮的重要因素之一。集群系統(tǒng)往往由數(shù)百至數(shù)萬個(gè)計(jì)算節(jié)點(diǎn)組成，每個(gè)節(jié)點(diǎn)中包括多個(gè)同構(gòu)多核處理器。集群系統(tǒng)能夠同時(shí)運(yùn)行多個(gè)應(yīng)用程序，向多個(gè)用戶提供服務(wù)。如何通過調(diào)度的方法加快應(yīng)用程序運(yùn)行速度、減少系統(tǒng)總能耗，已經(jīng)成為高性能計(jì)算必須解決的問題之一。

集群系統(tǒng)中并行任務(wù)節(jié)能調(diào)度問題是為系統(tǒng)中每一個(gè)待執(zhí)行的并行任務(wù)分配處理器等執(zhí)行資源，并指定占用這些資源的起止時(shí)間，在滿足任務(wù)間依賴關(guān)系的前提下，使得所有任務(wù)能夠較早完成，并且總能量消耗盡量少。與傳統(tǒng)的并行調(diào)度相比，并行任務(wù)節(jié)能調(diào)度的主要目標(biāo)不僅是減少所有任務(wù)總體完成時(shí)間，更要求盡量減少使用資源數(shù)目和資源的占用時(shí)間，提高資源利用率，達(dá)到整個(gè)集群系統(tǒng)中性能（任務(wù)總體完成時(shí)間）和能耗之間的平衡。

并行任務(wù)在多處理器上的最優(yōu)調(diào)度問題已經(jīng)證明是NP難的，不存在多項(xiàng)式時(shí)間的調(diào)度算法。國內(nèi)外的學(xué)者一般采用啟發(fā)式算法生成調(diào)度方案，在減少所有任務(wù)完成時(shí)間的同時(shí)降低系統(tǒng)能耗。帶依賴關(guān)系的并行任務(wù)可以抽象成一個(gè)由多個(gè)定點(diǎn)構(gòu)成的有向無環(huán)圖（DAG圖），其中頂點(diǎn)表示任務(wù)，頂點(diǎn)內(nèi)部的數(shù)字表示任務(wù)編號(hào)，頂點(diǎn)周圍的數(shù)字表示任務(wù)執(zhí)行時(shí)間；有向邊表示任務(wù)之間的依賴關(guān)系（數(shù)據(jù)傳遞方向）。如果具有依賴關(guān)系的兩個(gè)任務(wù)不在一個(gè)處理器上執(zhí)行，前一個(gè)任務(wù)完成后需要向后一個(gè)任務(wù)傳送數(shù)據(jù)，這需要一定的傳輸耗時(shí)。有向邊上的數(shù)值即表示數(shù)據(jù)傳輸耗時(shí)。如果具有依賴關(guān)系的兩個(gè)任務(wù)在一個(gè)處理器上執(zhí)行（無論是否在同一個(gè)內(nèi)核上），這種數(shù)據(jù)傳輸耗時(shí)相對于處理器之間的傳輸耗時(shí)可以忽略不計(jì)，即認(rèn)為此時(shí)的傳輸耗時(shí)等于0。

已有的任務(wù)復(fù)制調(diào)度策略TDS（Task?Duplication?Scheduling）按照DAG圖的拓?fù)浣Y(jié)構(gòu)生成多條任務(wù)執(zhí)行路徑，每條執(zhí)行路徑上的所有任務(wù)分為一組，分配到一個(gè)處理器上執(zhí)行，通過在多個(gè)處理器上復(fù)制執(zhí)行部分前驅(qū)任務(wù)，避免前驅(qū)任務(wù)的數(shù)據(jù)傳輸耗時(shí)，從而縮短所有任務(wù)的總體執(zhí)行時(shí)間。但是，任務(wù)復(fù)制執(zhí)行的方法在減少任務(wù)總體完成時(shí)間的同時(shí)，不可避免的帶來了能耗增加問題。為此，有人在TDS的基礎(chǔ)上，提出了兩種非搶占式離線節(jié)能調(diào)度算法—能量敏感復(fù)制調(diào)度EAD(Energy-Aware?Duplication)調(diào)度和性能能量均衡復(fù)制調(diào)度PEBD(Performance-Energy?Balanced?Duplication)調(diào)度，通過設(shè)置任務(wù)能量閾值和能量/時(shí)間比閾值，減少不必要任務(wù)的復(fù)制次數(shù)，從而降低系統(tǒng)的總體能量開銷。但是TDS、EAD和PEBD都存在處理器負(fù)載不平衡，平均利用率較低的問題。而且已有方法只是針對單核處理器上的考慮任務(wù)復(fù)制的節(jié)能調(diào)度算法。目前，還沒有同構(gòu)多核處理器上考慮任務(wù)復(fù)制執(zhí)行的節(jié)能調(diào)度算法。

發(fā)明內(nèi)容

為解決現(xiàn)有調(diào)度技術(shù)無法實(shí)現(xiàn)同構(gòu)多核處理器上考慮任務(wù)復(fù)制情況的并行節(jié)能調(diào)度問題，本發(fā)明提供了一種同構(gòu)多核集群服務(wù)器中基于任務(wù)依賴度的并行任務(wù)分組調(diào)度方法。

本發(fā)明采用的技術(shù)方案如下：

多核集群服務(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í)間超過允許的總體完成時(shí)間為止。在所有的可選調(diào)度方案列表中，選擇完成時(shí)間小于或等于總體完成時(shí)間約束的、節(jié)約能耗最多的一組調(diào)度方案作為最終調(diào)度。

所述的步驟（1）的具體步驟如下：

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

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