[發明專利]異構計算系統中基于能量感知利潤最大化的任務分配方法

在審

• 申請號: 202211039025.3
• 申請日: 2022-08-29
• 公開（公告）號: CN115454623A
• 公開（公告）日: 2022-12-09
• 發明（設計）人: 李偉東;張學杰;張慶輝
• 申請（專利權）人: 云南大學
• 主分類號: G06F9/50
• 分類號: G06F9/50
• 代理公司: 成都行之智信知識產權代理有限公司 51256
• 代理人: 溫利平

本發明公開了一種異構計算系統中基于能量感知利潤最大化的任務分配方法，獲取異構計算系統中機器和用戶的數據，包括用戶任務在各機器上的固定執行時間和平均功率消耗，然后依次對每個用戶進行任務分配，在每次分配時，先將所有機器按照用戶任務的固定執行時間和平均功率消耗的乘積進行排序，然后在不同任務分配起始機器編號計算任務分配向量，計算每個任務分配向量的利潤值，篩選最大利潤值對應的任務分配向量對用戶進行任務分配，更新機器的負載和能耗，再對下一用戶進行任務分配，直至所有用戶的任務分配結束。本發明綜合考慮了用戶任務在各機器上的固定執行時間和平均功率消耗，在任務分配時實現了能量感知利潤最大化。

技術領域

本發明屬于異構計算系統技術領域，更為具體地講，涉及一種異構計算系統中基于能量感知利潤最大化的任務分配方法。

背景技術

隨著數據中心能耗的快速增長，高性能計算系統中關注于能效的資源分配越來越重要。最近學界提出了一種名為任務包(bag-of-tasks)的靜態調度模型。與以往的經典調度模型相比，任務在機器上的固定執行時間(estimated time to compute)取決于任務類型與機器類型。這個新的模型會確定每個不同類型機器上執行的不同類型任務的數量，而不是任意的分配這些任務。雖然高性能計算中心會有成千上萬臺機器，并且需要執行的任務數也無法估計，但是二者的類型是很有限的，這讓為該模型設計一個能得到擬最優調度的算法成為可能。

經典的能量感知調度模型旨在最小化bag-of-tasks所消耗的能量或最大完工時間(makespan)。然而，高性能計算中心會更想要最大化單位時間的運行利潤，其中利潤等于用戶為一個任務包支付的價格減去執行期間消耗的電力成本，決定了高性能計算中心參與任務分配的積極性，因此需要對以利潤最大化為目標的任務分配方法進行研究，以適應實際應用場景的需要。

發明內容

本發明的目的在于克服現有技術的不足，提供一種異構計算系統中基于能量感知利潤最大化的任務分配方法，綜合考慮用戶任務在各機器上的固定執行時間和平均功率消耗，基于利潤進行任務分配，實現能量感知利潤最大化。

為了實現上述發明目的，本發明異構計算系統中基于能量感知利潤最大化的任務分配方法包括以下步驟：

S1：記異構計算系統中機器數量為M，用戶數量為N，其中用戶i提交的任務包中的任務數為a_i，執行用戶i的任務能產生的收益為p_i，i＝1,2,…,N；構建大小為N×M的固定執行時間矩陣ETC＝(ETC_ij)，其中ETC_ij表示用戶i的單個任務在機器j上的固定執行時間，j＝1,2,…,M，同時構建大小為N×M的平均功率消耗矩陣APC＝(APC_ij)，其中APC_ij表示用戶i的單個任務在機器j上單位時間內的平均功率消耗；初始化各個機器的負載M臺機器的總能耗E⁰＝0；

S2：令用戶序號i＝1；

S3：計算用戶i在各個機器上的固定執行時間和平均功率消耗的乘積APC_ijETC_ij，將M個機器按照該乘積從大到小進行排序，記排序后第m個機器的原始序號為j_m，m＝1,2,…,M；

S4：分別令任務分配起始機器編號τ＝1,2,…,M，求解以下方程組得到M個任務分配向量

其中，表示采用τ作為任務分配起始機器編號時用戶i在排序后第m個機器上所分配的任務數量，表示排序后第m個機器在用戶i-1的任務分配完成后的負載，表示用戶i的單個任務在排序后第m個機器上的固定執行時間，MS^τ,i表示采用τ作為任務分配起始機器編號對用戶i進行任務分配完成后所有機器負載的最大值，即機器負載的計算公式為：