[發明專利]一種基于穩定匹配博弈理論的工作流調度方法

有效

• 申請號: 202011329163.6
• 申請日: 2020-11-24
• 公開（公告）號: CN112306642B
• 公開（公告）日: 2022-10-14
• 發明（設計）人: 賈兆紅;潘磊;唐俊
• 申請（專利權）人: 安徽大學
• 主分類號: G06F9/455
• 分類號: G06F9/455
• 代理公司: 合肥市浩智運專利代理事務所(普通合伙) 34124
• 代理人: 張祥

1.一種基于穩定匹配博弈理論的工作流調度方法，其特征在于：包括以下步驟：

步驟A：輸入工作流的DAG圖，表示為DAG＝(T,E)，T＝{t₀,t₁,...,t_n-1}代表了工作流中的n個任務集合，E代表了n個任務之間的依賴關系集合；如果則代表只有在任務t_i執行完成并將數據傳遞到t_j上時，任務t_j才能被執行；任務t_j是任務t_i的后繼節點，任務t_i是任務t_j的前驅節點；

虛擬機池V＝{VM₀,VM₁,…,VM_m-1}，表示m臺虛擬機的集合；

以及CCR數值，所述CCR數值為經驗值，其代表所述工作流的平均計算時間和平均聯絡時間的比值；

步驟B：計算每個任務的rank值，選擇每一層中具有最大rank值的任務加入關鍵路徑任務集合CP，所述步驟B中所述的任務rank值計算方法為：

其中，succ(t_i)為任務t_i的后繼節點集合，t_exit為沒有后繼節點的出口任務；表示任務t_i的平均計算時間，表示任務t_i與任務t_j的平均聯絡時間；

其中，s_i表示任務t_i的尺寸，p_k表示虛擬機VM_k的處理能力，ET(t_i,VM_k)表示任務t_i在虛擬機VM_k上的計算時間，TT_ij表示前驅節點t_i向后繼節點t_j傳輸的數據尺寸，B(VM_k,VM_l)表示虛擬機VM_k向虛擬機VM_l傳輸數據的帶寬，任務t_j在虛擬機VM_l上處理，當p＝k時，B(VM_k,VM_l)＝0，T_tran(t_i,t_j)＝0；

步驟C：基于穩定匹配博弈理論將任務分配到虛擬機上，得到調度方案；

步驟D：優化調度方案，遍歷所有任務，將使當前任務開始時間提前的前驅節點復制到當前任務所在的虛擬機上。

2.根據權利要求1所述的一種基于穩定匹配博弈理論的工作流調度方法，其特征在于：步驟B中DAG分層的方法為：

其中，t_i.level表示任務所在層，pre(t_i)表示任務t_i的前驅節點集合，t_entry表示沒有前驅節點的入口任務。