[發明專利]一種分布式計算任務的協同調度方法及裝置

有效

• 申請號: 201710078384.2
• 申請日: 2017-02-14
• 公開（公告）號: CN108427602B
• 公開（公告）日: 2021-10-29
• 發明（設計）人: 朱力鵬;胡斌;饒瑋;黃太貴;李端超;王松;靳丹;馬志程
• 申請（專利權）人: 全球能源互聯網研究院有限公司;國網安徽省電力有限公司;國網甘肅省電力公司;國家電網有限公司
• 主分類號: G06F9/50
• 分類號: G06F9/50;G06N3/12
• 代理公司: 北京安博達知識產權代理有限公司 11271
• 代理人: 徐國文

本發明涉及一種分布式計算任務的協同調度方法及裝置，所述方法包括：確定各任務在各資源上的期望完成時間，并建立期望完成時間矩陣；利用基因表達式編程算法確定各資源需處理任務個數；根據各任務的緊迫度和重要度確定各任務的評估值，并按各任務的評估值從大到小排序，獲取任務序列；根據所述期望完成時間矩陣和各資源需處理任務個數利用Min?Min算法依次將任務序列中的任務分配到各資源上；本發明提供的技術方案研究有效的任務調度方法，充分利用有效資源在最短的時間內完成提交的任務。

技術領域

本發明涉及分布式計算軟件領域，具體涉及一種分布式計算任務的協同調度方法及裝置。

背景技術

協同調度是在分布式計算環境中進行資源分配的一種重要技術，用于把用戶提交的多個任務分配到多個資源上同時處理，以此來滿足特定的性能要求。用戶任務的有效處理是新形勢下技術融合型發展和應用智能化理念的集中體現，在分布式系統中，任務的調度以及資源計算能力的均衡和計算節點的效率是衡量一個算法優劣的主要指標。如何在動態變化的多個虛擬機構間共享資源和協同解決，是目前任務協同調度中的一個大問題，通過協同調度可以提高任務在分布式計算環境中的性能，協同調度的方法廣泛應用于虛擬現實，虛擬儀器，以及大規?？茖W計算等領域。

目前，國內外任務調度策略研究主要有兩類：應用級任務調度和作業級任務調度。應用級任務調度由傳統資源環境下基于任務圖(DAG)的調度問題演化而來，通過將計算密集型應用抽象為粗粒度約束任務圖，采用經濟模型和數學規劃策略將其映射到網絡計算資源，從而提高應用性能。由于當前網絡環境存在高延遲、低帶寬等缺點，這方面的研究工作僅局限于參數掃描與松耦合迭代應用。國內針對任務的協同調度問題提出了基于模糊聚類的任務調度啟發式，基于粒子群算法的協同調度等作業級任務調度，研究對象協同作業時的性能優化問題，是高性能多個資源調度研究在網絡計算環境下的延伸。網絡環境下多個資源的任務協同調度為NP-hard問題，難以獲得多項式時間內的最優調度方法。影響任務執行時間的主要因素有任務的多樣性、各個資源的差異等。

發明內容

本發明提供一種分布式計算任務的協同調度方法及裝置，其目的是研究有效的任務調度方法，充分利用有效資源在最短的時間內完成提交的任務。

本發明的目的是采用下述技術方案實現的：

一種分布式計算任務的協同調度方法，其改進之處在于，包括：

確定各任務在各資源上的期望完成時間，并建立期望完成時間矩陣；

利用基因表達式編程算法確定各資源需處理任務個數；

根據各任務的緊迫度和重要度確定各任務的評估值，并按各任務的評估值從大到小排序，獲取任務序列；

根據所述期望完成時間矩陣和各資源需處理任務個數利用Min-Min算法依次將任務序列中的任務分配到各資源上。

優選的，所述確定各任務在各資源上的期望完成時間，并建立期望完成時間矩陣，包括：

記任務數為n，資源數為m，按下式構建m×n的期望完成時間矩陣E_m×n：

上式中，e_ij為第i個任務在第j個資源上的期望完成時間。

優選的，所述利用基因表達式編程算法確定各資源需處理任務個數，包括：

a.初始化種群，所述種群由m個資源和每個資源要處理的任務個數組成，其中，種群中染色體的頭長為p，尾長d＝p(l-1)+1，l為最大操作數；

b.根據種群個體的適應度函數值選擇種群中最優個體，保留最優個體并對當前子種群個體進行基因交叉、基因突變和重組，獲取新種群，其中，按下式確定種群個體的適應度函數：