[發明專利]實現動態工作流最優計算的海量異構服務器互連方法

在審

• 申請號: 202110375720.6
• 申請日: 2021-04-08
• 公開（公告）號: CN113176932A
• 公開（公告）日: 2021-07-27
• 發明（設計）人: 沈鴻;楊元昊
• 申請（專利權）人: 中山大學
• 主分類號: G06F9/48
• 分類號: G06F9/48;G06F9/50
• 代理公司: 廣州粵高專利商標代理有限公司 44102
• 代理人: 劉俊

本發明公開了實現動態工作流最優計算的海量異構服務器互連方法，包括以下步驟：S1：獲取DAG工作流中沒有前置依賴的任務，并將對應的任務請求發送至任務調度器；S2：任務調度器接收到任務請求后，將當下分布式系統中可利用資源和待分配任務作為強化學習算法的輸入，強化學習算法輸出任務執行的優先級并基于貪心算法依次將任務分配給邊際效益最大的服務器進行運算處理；S3：完成當前階段的任務分配后，若一個任務已經完成執行，則對應的服務器將向任務調度器發出異步通知，任務調度器再次在等待隊列的任務中選擇沒有前置依賴的任務，并開始新一輪的強化學習的任務調度與分配。本發明提高了任務調度的響應速度，增強了處理方法在復雜環境下的穩定性。

技術領域

本發明涉及分布式系統任務調度技術領域，更具體地，涉及實現動態工作流最優計算的海量異構服務器互連方法。

背景技術

任務調度問題是分布式計算領域中的基本問題。現實中，任務之間往往存在相互依賴關系，構成了一個工作流，它一般可由有向無環的任務圖(DAG)來表示。已有的技術有以下幾類：

隨機過程模型方法類：利用離散時間馬爾科夫隨機過程的遍歷性或平穩分布的方法進行DAG吞吐量的優化。雖然有理論證明，可以保證較好的性能，但往往需要較長的算法執行時間，不能夠快速地給出響應。

遺傳、進化，粒子群等啟發式方法：利用隨機搜索的辦法解決DAG任務調度中的優化組合問題。沒有理論證明，性能忽好忽壞不夠穩定。

現有技術中，公開號為CN111191934A，于2020年5月22日公開了一種基于強化學習策略的多目標云工作流調度方法，通過利用指針網絡對強化學習Agent進行改進形成改進后的深度強化學習算法構建基于強化學習策略的工作流調度模型，使得工作流調度模型能適用于不同大小、不同類型的云工作流調度問題，在保證較高時效性的同時，提升模型的泛化能力。該方案沒有充分考慮任務調度中的邊際效用及任務計算負載。

發明內容

本發明為克服上述現有技術中分布式系統中任務調度沒有充分考慮任務排序及邊際效用的缺陷，提供實現動態工作流最優計算的海量異構服務器互連方法。

本發明的首要目的是為解決上述技術問題，本發明的技術方案如下：

實現動態工作流最優計算的海量異構服務器互連方法，包括以下步驟：

S1：獲取DAG工作流中沒有前置依賴的任務，并將對應的任務請求發送至任務調度器；

S2：任務調度器接收到任務請求后，將當下分布式系統中可利用資源和待分配任務作為強化學習算法的輸入，強化學習算法輸出任務執行的優先級并基于貪心算法依次將任務分配給邊際效益最大的服務器進行運算處理；

S3：完成當前階段的任務分配后，若一個任務已經完成執行，則對應的服務器將向任務調度器發出異步通知，任務調度器再次在等待隊列的任務中選擇沒有前置依賴的任務，并開始新一輪的強化學習的任務調度與分配。

進一步的，步驟S1中強化學習算法通過n步比較法進行優先級排序處理，具體處理過程為：

設定待排序任務為k個，動作空間數為m，其中mk；

從第一個待排序任務開始每次依次選取m個進行排序，進行比較排序，直至K個全部排序完成。

進一步的，貪心算法的處理流程為：

對于給定優先級排序的任務，從第一個任務開始每個任務均遍歷所有主機，選擇一個主機j，使得主機j執行當前任務時邊際效用最大，則將該任務分配給主機j執行。

進一步的，貪心算法得到任務分配在主機上執行的方案，將該執行方案所得到的總效用作為強化學習的獎賞，返回強化學習算法的給策略梯度網絡進行對應的參數梯度更新。