[發(fā)明專利]數(shù)據(jù)中心網(wǎng)絡中動態(tài)工作流的高效鏈路調(diào)度方法

有效

• 申請?zhí)枺?/td>: 202110373804.6
• 申請日: 2021-04-07
• 公開（公告）號: CN113127169B
• 公開（公告）日: 2023-05-02
• 發(fā)明（設計）人: 沈鴻;王鑫
• 申請（專利權(quán)）人: 中山大學
• 主分類號: G06F9/48
• 分類號: G06F9/48;G06N3/042;G06N3/08
• 代理公司: 廣州粵高專利商標代理有限公司 44102
• 代理人: 劉俊

本發(fā)明提供一種數(shù)據(jù)中心網(wǎng)絡中動態(tài)工作流的高效鏈路調(diào)度方法，所述的方法步驟如下：S1：使用有向無環(huán)圖神經(jīng)網(wǎng)絡同時處理已到來的n個coflow；S2：構(gòu)成J個不完整的作業(yè)DAG，并將這J個不完整的作業(yè)DAG作為一個大的無連通的有向無環(huán)圖輸入有向無環(huán)圖神經(jīng)網(wǎng)絡，輸出得到每一個節(jié)點的embedding向量；S3：通過步驟S2得到n個embedding向量，并將n個embedding向量作為深度強化學習中策略網(wǎng)絡的輸入，得到每一個節(jié)點的score，計算得到每一個節(jié)點的加權(quán)分數(shù)值；S4：根據(jù)當前不同job的部分DAG圖，找到當前所有入度為0的節(jié)點，經(jīng)過一個softmax操作計算基于加權(quán)分數(shù)值的每一個節(jié)點的概率，根據(jù)節(jié)點的概率排列得到coflow調(diào)度優(yōu)先級列表；S5：基于coflow調(diào)度優(yōu)先級列表進行優(yōu)先級調(diào)度任務。

技術(shù)領域

本發(fā)明涉及高性能計算領域，更具體地，涉及一種數(shù)據(jù)中心網(wǎng)絡中動態(tài)工作流的高效鏈路調(diào)度方法。

背景技術(shù)

現(xiàn)代并行計算平臺(如Hadoop、Spark、Dryad)已經(jīng)支持在數(shù)據(jù)中心處理大數(shù)據(jù)集。處理通常是由多個計算和通信階段組成的。計算階段涉及服務器的本地操作，而通信階段涉及數(shù)據(jù)中心網(wǎng)絡中的服務器之間的數(shù)據(jù)傳輸，以啟動下一個計算階段。這樣的中間通信階段對應用程序延遲有很大的影響。Coflow是一種被提出用來建模此類通信模式的抽象，它表示一組中間并行數(shù)據(jù)流，并在服務器之間傳輸，以啟動下一個階段。

對于具有單一通信階段的作業(yè)，最大限度地減少coflow的平均完成時間可以改善作業(yè)的延遲。然而，對于多階段作業(yè)，最小化平均Coflow完成時間可能不是正確的度量標準，甚至可能導致更糟糕的性能，因為它忽略了作業(yè)中Coflow之間的依賴關系：Starts-After和Finishes-Before。對于多階段作業(yè)而言，每個作業(yè)都由多個Coflow組成，通常用DAG(有向無環(huán)圖)表示，該DAG捕獲了Coflow之間的依賴關系(Starts-After)。

雖然對于單階段作業(yè)的Coflow調(diào)度研究很多，但對于多階段作業(yè)的Coflow調(diào)度以及Coflow之間的依賴關系在很大程度上被忽視了。多階段作業(yè)的Coflow調(diào)度問題已經(jīng)被證明是一個NP難問題。多階段作業(yè)的Coflow調(diào)度問題困難在于存在很多處理難點以及內(nèi)在的因素，包括如何處理不同的作業(yè)DAG，如何有效提取作業(yè)DAG的特征信息(包括節(jié)點信息，邊信息，依賴關系等)，以及不同job中的Coflow數(shù)量不同，單個Coflow中并行流的數(shù)量不同等因素。現(xiàn)有技術(shù)主要存在以下局限性：

現(xiàn)有的作業(yè)，包括啟發(fā)式和近似算法，都集中在單階段作業(yè)的Coflow調(diào)度。對于多階段作業(yè)的Coflow調(diào)度問題，在Aalo中，作者簡單討論了一個直接的啟發(fā)式方法來減少多階段作業(yè)的完成時間。人工調(diào)試的啟發(fā)式解決方案通過給定一些松弛條件簡化了問題，只確保一個粗略近似的NP難問題的最優(yōu)解決方案。

因此，我們思考，能否構(gòu)造不出無需人工指導的自適應調(diào)度模型，通過直接與環(huán)境進行交互，動態(tài)地調(diào)度來自不同job中的依賴Coflow，優(yōu)化加權(quán)作業(yè)完成時間之和，提升作業(yè)效率。權(quán)重可以為不同的作業(yè)捕捉不同的優(yōu)先級,在所有權(quán)重相等的特殊情況下，問題等價于最小化平均作業(yè)完成時間。

發(fā)明內(nèi)容

本發(fā)明為克服上述現(xiàn)有技術(shù)中存在的缺點和不足，提供了一種數(shù)據(jù)中心網(wǎng)絡中動態(tài)工作流的高效鏈路調(diào)度方法，其能動態(tài)地調(diào)度來自不同job中的依賴Coflow，而不需要依靠大量人工調(diào)試，使得加權(quán)作業(yè)完成時間之和最小化。

為解決上述技術(shù)問題，本發(fā)明的技術(shù)方案如下：一種數(shù)據(jù)中心網(wǎng)絡中動態(tài)工作流的高效鏈路調(diào)度方法，所述的方法步驟如下：

S1：使用有向無環(huán)圖神經(jīng)網(wǎng)絡同時處理已到來的n個coflow，若干個依賴關系的任務組成一個作業(yè)，采用DAG表示；

S2：構(gòu)成J個不完整的作業(yè)DAG，并將這J個不完整的作業(yè)DAG作為一個大的無連通的有向無環(huán)圖輸入有向無環(huán)圖神經(jīng)網(wǎng)絡，輸出得到每一個節(jié)點的embedding向量；