[發明專利]一種基于分段排序及標準差調整因子的云計算任務調度方法

有效

• 申請號: 201710458109.3
• 申請日: 2017-06-16
• 公開（公告）號: CN107357652B
• 公開（公告）日: 2020-10-23
• 發明（設計）人: 高欣;王萍;趙兵;賈慶軒;王睿;梁躍
• 申請（專利權）人: 北京郵電大學
• 主分類號: G06F9/50
• 分類號: G06F9/50;G06F9/48;H04L29/08
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.一種基于分段排序及標準差調整因子的云計算任務調度方法，其特征在于包括以下步驟：

步驟1：基于任務的獨立性和異構的硬件計算節點，建立任務調度數學模型，確定預期執行矩陣ETC，具體為：

(1)根據任務數、任務規模和資源計算能力，得出任務列表和計算資源列表，計算出每一個任務在不同資源上的運行時間，構建ETC矩陣；ETC矩陣可以用來表達任務和機器的異構性，它是一種性能預測模型；n個任務在m個資源上的預測執行時間ETC是一個n×m的矩陣，矩陣的第i行表示任務i在每一個計算節點的預測執行時間；第j列則表示在第j項計算機上的各個任務的預測執行時間：

1≤i≤n；1≤j≤m

上述公式中，etc_ij代表任務i在第j計算資源上的預期執行時間，t_ij代表附加通信時間，e_ij代表任務i在計算節點j的運行指令時間，inputsize_i代表任務i額外附加信息，作為擴展使用，length_i代表任務i的任務長度，bandwidth_j代表計算節點j的通信帶寬，mips_j代表計算節點j的處理速度；

(2)確定并計算任務調度的目標和評價性能的標準-時間跨度和負載均衡；任務調度的目標是使得最慢完成的計算機的處理時間最短，也就是最小的時間跨度(如下公式中的λ_i代表任務i是否被調度到計算節點j，它的值為0或1，0代表沒有，1代表有):

態規劃的多階段決策組合優化方法，計算各個任務的平均預期執行時間，并以此為依據將負載均衡衡量一個系統的負載是否平衡，這里用各個計算節點負載的標準方差來判斷：

其中，m代表計算節點數，x_i代表第i個計算節點的負載量，代表所有負載的平均值，σ代表所有負載的標準差；

步驟2：利用動態規劃的多階段決策組合優化方法，計算各個任務的平均預期執行時間，并以此為依據將任務進行分段，使長時間執行的任務可以優先執行，縮短執行時間，具體為：

(1)根據任務獨立和計算節點異構的特點，計算將每個任務的平均執行時間e_i，將其作為排序的標準：

(2)將平均執行時間的長短作為排序標準，利用快速排序方法對任務排序；快速排序方法采用分治的策略，適用于大數據，且速度比較快，可以達到O(nlogn)，其步驟分為三步：

1)先從待排序的數組中取出一個數作為基準數；

2)分區過程，將比這個數大的數全放到它的右邊，小于或等于它的數全放到它的左邊；

3)再對左右區間重復第二步，直到各區間只有一個數；

(3)根據快速排序后的排序結果，按照平均執行時間值e_i大小順序對任務進行均勻分段，分為4-5段；分段主要是為了將長任務優先調度，同時也是提高負載均衡度；

步驟3：在各個分段中，計算每個任務在各個計算節點下運行時間的標準差，然后根據其大小，將標準差大的任務優先調度到最短完成時間的計算節點上，從而減少任務等待時間，具體為：

(1)段內任務進行標準差優先級調整；標準差可以反映任務在每個處理器上執行的離散程度，將此作為調整因子來縮短執行時間；利用之前求得的平均執行時間求得每個任務預期執行時間的標準差σ：

(2)計算每次調度中任務的mct_ij，構建MCT矩陣，MCT為n×m的預測最短完成時間矩陣，r_j為已調度的計算資源等待時間，mct_ij為第i行第j列所在任務的預測最短的完成時間：

mct_ij＝etc_ij+r_j

(3)依次對每個任務進行調度，直到所有的任務都結束，最后得到調度序列以及時間跨度、負載均衡等指標。