[發明專利]一種面向分布式流計算系統的動態任務調度優化方法

有效

• 申請號: 201710997546.2
• 申請日: 2017-10-24
• 公開（公告）號: CN107832129B
• 公開（公告）日: 2020-05-19
• 發明（設計）人: 吳松;金海;柳密
• 申請（專利權）人: 華中科技大學
• 主分類號: G06F9/48
• 分類號: G06F9/48
• 代理公司: 華中科技大學專利中心 42201
• 代理人: 李智;曹葆青

1.一種面向分布式流計算環境下的任務調度優化方法，其特征在于，包括如下步驟：

步驟1、依據當前周期內任務間的通信量預測下一周期內任務間的通信量；具體實現過程為：在采樣周期T內統計任務i發送給任務j的消息總數量記為任務i到j的通信量Traffic_T(i，j)，結合前一周期內任務i到j的通信量Traffic_last(i，j)預測下一個周期內任務i到j的通信量Traffic_{next(i，j)}：

Traffic_{next(i，j)}＝Traffic_last(i，j)×β+Traffic_T(i，j)×(1-β)

式中，β是比例伸縮常量；

步驟2、將下一周期內預測通信量最大的兩個任務組合為一個任務組；具體實現過程為：

從任務i的所有鄰居未訪問任務中，選取一個任務i與它之間的預測通信量最大的任務，將其與任務i組合為任務組parentTask，如果任務i的所有鄰居任務均已被訪問，僅將任務i獨立組合為任務組parentTask，完成第一層組合；

遍歷每一條數據流，如果數據流的源任務和目標任務屬于同一個parentTask，那么這條數據流在下一層組合時忽略；如果數據流的源任務和目標任務不屬于同一個parentTask，那么這條數據流將跨越兩個不同的parentTask，將這兩個paremTask之間的所有數據流的通信量之和作為這兩個parentTask在下一層組合時的預測通信量；從parentTask的所有鄰居未訪問parentTask中，選取一個與它之間的預測通信量最大的parentTask，將其與parentTask組合為下一層次的任務組parentTask，完成第二層組合；重復第二層組合方式，直到最終的任務組數低于閾值taskNumThreshold；

步驟3、啟動進程并以任務組為單位進行調度；具體實現方式為：選取當前負載小于進程平均預測負載的進程作為候選進程，從候選進程中選取當前負載最低的調度任務組；

所述進程平均預測負載的計算方式為：獲取當前啟動的進程總數W，將當前調度的k個任務組在下一周內的預測負載W_load_nexti求和得到預測總負載，依據進程總數和預測總負載計算每個進程worker的平均預測負載：

2.根據權利要求1所述的面向分布式流計算環境下的任務調度優化方法，其特征在于，所述在采樣周期T內統計任務i發送給任務j的消息總數量的具體實現方式：檢測系統中的任務發送隊列，記錄任務i發送的消息中攜帶的目標任務j的ID，通過ID更新對應的消息數量。

3.根據權利要求1或2所述面向分布式流計算環境下的任務調度優化方法，其特征在于，使用雙層哈希表保存任務i到任務j的通信量，映射關系為任務i的ID、任務j的ID、任務i發送給任務j的消息數量。

4.根據權利要求1所述的面向分布式流計算環境下的任務調度優化方法，其特征在于，所述任務在下一周內的預測負載W_load_nexti的獲取方式為：

在采樣周期T內統計任務i接收和發送的消息總數量W_load_T記為任務i的負載W_load_Ti，結合前一周期內任務i的負載W_load_Lasti預測下一周內任務i的負載W_load_nexti：

W_load_nexti＝W_load_lasti×α+W_load_Ti×(1-α)

式中，α是比例伸縮常量。