[發(fā)明專利]基于多智能體深度強(qiáng)化學(xué)習(xí)的集群資源調(diào)度方法及系統(tǒng)

有效

• 申請?zhí)枺?/td>: 202010322543.0
• 申請日: 2020-04-22
• 公開（公告）號: CN111694656B
• 公開（公告）日: 2022-08-05
• 發(fā)明（設(shè)計(jì)）人: 潘麗晨;毛航宇;肖臻;張正超
• 申請（專利權(quán)）人: 北京大學(xué)
• 主分類號: G06F9/50
• 分類號: G06F9/50;G06F9/48;G06N3/08
• 代理公司: 北京君尚知識產(chǎn)權(quán)代理有限公司 11200
• 代理人: 陳艷

1.一種基于多智能體深度強(qiáng)化學(xué)習(xí)的集群資源調(diào)度方法，其特征在于，包括以下步驟：

生成作業(yè)序列，包括生成隨機(jī)合成的作業(yè)序列或者基于云服務(wù)提供商公開數(shù)據(jù)的真實(shí)作業(yè)序列；

從作業(yè)序列中提取作業(yè)，添加到等待作業(yè)隊(duì)列中并計(jì)算預(yù)計(jì)執(zhí)行時間，該等待作業(yè)隊(duì)列設(shè)置成由多臺機(jī)器組成的集群共享，每臺機(jī)器含有待分配的計(jì)算資源；

根據(jù)傳統(tǒng)手工設(shè)計(jì)的啟發(fā)式調(diào)度算法生成調(diào)度決策，并利用該調(diào)度決策訓(xùn)練、評估和優(yōu)化基于多智能體深度強(qiáng)化學(xué)習(xí)的自適應(yīng)調(diào)度算法，根據(jù)基于多智能體深度強(qiáng)化學(xué)習(xí)的自適應(yīng)調(diào)度算法從等待作業(yè)隊(duì)列中讀取每個作業(yè)的屬性向量和集群中每臺機(jī)器的屬性向量，對上述兩種屬性向量分別通過作業(yè)智能體和機(jī)器智能體利用神經(jīng)網(wǎng)絡(luò)生成維度相同的動作向量，將一個作業(yè)的動作向量和一臺機(jī)器的動作向量做點(diǎn)積操作后得到一個調(diào)度方案的可行性分?jǐn)?shù)，每個待調(diào)度作業(yè)選定可行性分?jǐn)?shù)最高的調(diào)度方案為其最終調(diào)度決策，所有作業(yè)的調(diào)度決策再按照可行性分?jǐn)?shù)從高到低排序后，得到當(dāng)前所有待調(diào)度作業(yè)整體的最終調(diào)度決策；基于多智能體深度強(qiáng)化學(xué)習(xí)的自適應(yīng)調(diào)度算法中使用的神經(jīng)網(wǎng)絡(luò)通過基于共享集中式價值網(wǎng)絡(luò)的MADDPG算法訓(xùn)練；訓(xùn)練樣本包括當(dāng)前作業(yè)和機(jī)器的屬性向量和動作向量，調(diào)度決策的懲罰函數(shù)值，后續(xù)作業(yè)和機(jī)器的屬性向量；如果一個作業(yè)被成功調(diào)度到一個機(jī)器上，則懲罰函數(shù)值為0，后續(xù)作業(yè)和機(jī)器的屬性向量為空；如果調(diào)度失敗，則懲罰函數(shù)值為作業(yè)的預(yù)計(jì)運(yùn)行時間的負(fù)倒數(shù)，后續(xù)作業(yè)和機(jī)器的屬性向量設(shè)置為向前推進(jìn)一個單位時間后對應(yīng)的作業(yè)和機(jī)器的屬性向量；訓(xùn)練中通過對共享集中式價值網(wǎng)絡(luò)和作業(yè)智能體、機(jī)器智能體的策略網(wǎng)絡(luò)的優(yōu)化，求得最優(yōu)的調(diào)度策略；

對于待調(diào)度作業(yè)，根據(jù)上述最終調(diào)度決策指定的目標(biāo)機(jī)器，在目標(biāo)機(jī)器的可用計(jì)算資源中扣除作業(yè)使用的資源，到達(dá)作業(yè)預(yù)計(jì)完成時間后釋放，完成調(diào)度。

2.如權(quán)利要求1所述的方法，其特征在于，該傳統(tǒng)手工設(shè)計(jì)的啟發(fā)式調(diào)度算法，為對作業(yè)使用最短作業(yè)優(yōu)先和先來先服務(wù)的策略，對機(jī)器使用首先適配、最優(yōu)適配和最差適配的策略，將前兩種策略與后三種策略之間進(jìn)行兩兩組合得到六種調(diào)度算法，并根據(jù)短作業(yè)優(yōu)先以及作業(yè)資源請求量與機(jī)器剩余資源量匹配程度的Tetris算法得到第七種調(diào)度算法，根據(jù)上述七種調(diào)度算法的任意一種產(chǎn)生調(diào)度決策。

3.如權(quán)利要求1所述的方法，其特征在于，生成隨機(jī)合成的作業(yè)序列的方法是：通過概率模型生成每個作業(yè)所需的資源類型、資源數(shù)量和復(fù)雜程度系數(shù)，得到隨機(jī)合成的作業(yè)序列；生成真實(shí)作業(yè)序列的方法是：從云服務(wù)提供商公開的線上集群中獲得作業(yè)提交和執(zhí)行的原始記錄數(shù)據(jù)；將原始記錄數(shù)據(jù)預(yù)處理后，提取出每個作業(yè)的到來時間、資源類型、資源數(shù)量和復(fù)雜程度系數(shù)，得到真實(shí)作業(yè)序列。

4.如權(quán)利要求3所述的方法，其特征在于，根據(jù)每個作業(yè)的復(fù)雜程度系數(shù)和集群中機(jī)器的處理能力，計(jì)算每個作業(yè)的預(yù)計(jì)執(zhí)行時間。

5.如權(quán)利要求4所述的方法，其特征在于，根據(jù)調(diào)度決策把作業(yè)調(diào)度到其目標(biāo)機(jī)器上進(jìn)行執(zhí)行，每臺機(jī)器的每種資源被劃分為若干個資源槽，表示為一個一維向量；若機(jī)器具有滿足作業(yè)對每種資源的申請數(shù)量的空閑資源，則將機(jī)器相應(yīng)數(shù)目的空閑資源槽的值設(shè)置為作業(yè)的預(yù)計(jì)執(zhí)行時間。

6.如權(quán)利要求1所述的方法，其特征在于，基于多智能體深度強(qiáng)化學(xué)習(xí)的自適應(yīng)調(diào)度算法中，調(diào)度方案為由待調(diào)度作業(yè)編號和待評估機(jī)器編號組成的二元組。

7.如權(quán)利要求1所述的方法，其特征在于，根據(jù)指定的起始時間戳和提取長度，依次讀取出匹配該長度的作業(yè)序列。

8.如權(quán)利要求1所述的方法，其特征在于，將作業(yè)序列加載到一個可被循環(huán)訪問的全局作業(yè)隊(duì)列中；根據(jù)全局時鐘向前推進(jìn)，每向前推進(jìn)一個時間單位，則從全局作業(yè)隊(duì)列中把當(dāng)前時刻新到來的作業(yè)加入到等待作業(yè)隊(duì)列中。

9.一種基于多智能體深度強(qiáng)化學(xué)習(xí)的集群資源調(diào)度系統(tǒng)，其特征在于，包括作業(yè)序列生成模塊、作業(yè)序列測評模塊、第一調(diào)度決策產(chǎn)生模塊、第二調(diào)度決策產(chǎn)生模塊以及多智能體強(qiáng)化學(xué)習(xí)算法訓(xùn)練模塊；

作業(yè)序列生成模塊，用于根據(jù)作業(yè)數(shù)據(jù)生成隨機(jī)合成的作業(yè)序列和基于云服務(wù)提供商公開數(shù)據(jù)的真實(shí)作業(yè)序列；

作業(yè)序列測評模塊，用于構(gòu)建運(yùn)行環(huán)境，該運(yùn)行環(huán)境中包含由多臺機(jī)器組成的集群，每臺機(jī)器含有待分配的計(jì)算資源，整個集群擁有共享的等待作業(yè)隊(duì)列；從作業(yè)序列生成模塊中獲得其新近生成的作業(yè)，將其添加到等待作業(yè)隊(duì)列中，并計(jì)算其預(yù)計(jì)執(zhí)行時間；依次在調(diào)度決策中指定的待調(diào)度作業(yè)的目標(biāo)機(jī)器的可用計(jì)算資源中扣除作業(yè)使用的資源，到達(dá)作業(yè)預(yù)計(jì)完成時間之后釋放；還負(fù)責(zé)為多智能體強(qiáng)化學(xué)習(xí)算法訓(xùn)練模塊計(jì)算懲罰函數(shù)值；

第一調(diào)度決策產(chǎn)生模塊，為基于傳統(tǒng)手工設(shè)計(jì)的啟發(fā)式調(diào)度算法的調(diào)度決策產(chǎn)生模塊，對作業(yè)使用最短作業(yè)優(yōu)先和先來先服務(wù)的策略，對機(jī)器使用首先適配、最優(yōu)適配和最差適配的策略，將前兩種策略與后三種策略之間進(jìn)行兩兩組合得到六種調(diào)度算法，并根據(jù)短作業(yè)優(yōu)先以及作業(yè)資源請求量與機(jī)器剩余資源量匹配程度的Tetris算法得到第七種調(diào)度算法，根據(jù)上述七種調(diào)度算法的任意一種或幾種產(chǎn)生調(diào)度決策；利用傳統(tǒng)手工設(shè)計(jì)的啟發(fā)式調(diào)度算法生成的調(diào)度決策，訓(xùn)練、評估和優(yōu)化基于多智能體深度強(qiáng)化學(xué)習(xí)的自適應(yīng)調(diào)度算法；

第二調(diào)度決策產(chǎn)生模塊，為基于多智能體深度強(qiáng)化學(xué)習(xí)的自適應(yīng)調(diào)度算法的調(diào)度決策產(chǎn)生模塊，包括機(jī)器智能體和作業(yè)智能體，機(jī)器智能體通過深度神經(jīng)網(wǎng)絡(luò)對每臺機(jī)器的屬性向量生成一個動作向量，作業(yè)智能體通過深度神經(jīng)網(wǎng)絡(luò)對每個作業(yè)的屬性向量生成一個相同維度的動作向量，兩個動作向量點(diǎn)積后得到一個調(diào)度策略的可行性分?jǐn)?shù)；對于每個待調(diào)度作業(yè)，選定可行性分?jǐn)?shù)最高的調(diào)度策略作為其最終調(diào)度決策；對所有作業(yè)的調(diào)度決策按照可行性分?jǐn)?shù)從高到低進(jìn)行排序后，得到當(dāng)前所有待調(diào)度作業(yè)整體的最終調(diào)度決策；

多智能體強(qiáng)化學(xué)習(xí)算法訓(xùn)練模塊，使用基于共享集中式價值網(wǎng)絡(luò)的MADDPG算法訓(xùn)練深度神經(jīng)網(wǎng)絡(luò)，訓(xùn)練樣本包括當(dāng)前作業(yè)和機(jī)器的屬性向量和動作向量，調(diào)度決策的懲罰函數(shù)值，后續(xù)作業(yè)和機(jī)器的屬性向量；如果一個作業(yè)被成功調(diào)度到一個機(jī)器上，則懲罰函數(shù)值為0，后續(xù)作業(yè)和機(jī)器的屬性向量為空；如果調(diào)度失敗，則懲罰函數(shù)值為作業(yè)的預(yù)計(jì)運(yùn)行時間的負(fù)倒數(shù)，后續(xù)作業(yè)和機(jī)器的屬性向量設(shè)置為向前推進(jìn)一個單位時間后對應(yīng)的作業(yè)和機(jī)器的屬性向量；訓(xùn)練中通過對共享集中式價值網(wǎng)絡(luò)和作業(yè)智能體、機(jī)器智能體的策略網(wǎng)絡(luò)的優(yōu)化，求得最優(yōu)的調(diào)度策略。