一種基于DAG的網絡流量調度器

時 洋 文 梅 費佳偉 張春元

(國防科技大學計算機學院 長沙 410073) (國防科技大學并行與分布式處理國防科技重點實驗室 長沙 410073)

為了滿足應用對于不同資源以及性能的需求，現在大家越來越趨向于將它們部署在數據中心上[1].但是，數據中心中的資源競爭也隨著任務數目的增加變得更加激烈，并且會導致任務完成時間(job completion time，JCT)的增加以及整個數據中心效率的降低.在應用競爭的資源中，網絡資源往往是最為關鍵的一種.有調研報告稱，在數據中心中，網絡傳輸時間占到了任務完成時間的50%[2].這種情況就對數據中心的網絡資源調度提出了要求，需要盡量通過調度來提升網絡的效率，從而加速分布式任務.

基于此，過去數十年來研究者們提出了很多網絡調度的技術.傳統的網絡調度算法大多聚焦在減少流完成時間[3-4]或者提升流之間的公平性[5-6]等方面；由于它們往往不考慮任務的具體網絡需求，所以無法捕捉到每個應用網絡需求的詳細特征.因此，它們在減少JCT以及提升網絡效率上的表現無法令人滿意.

意識到這個缺陷之后，研究者們開始針對具體的應用來設計網絡調度的算法.其中，coflow[7]的提出是向著任務感知的網絡調度邁出的關鍵一步.研究者發現，許多分布式任務是由一定數目的處理階段按照某種順序組織而成的，而這一類任務重要的一個性質就是2個連續階段中的后一個，無法在前一個向它傳輸的所有網絡流完成之前開始.基于這個特征，coflow被定義為2個計算階段之間所有網絡流的總和.相比于優化傳統的流傳輸指標，優化coflow的完成時間更接近于我們加速任務執行的目的.

然而，伴隨著現在的分布式任務越來越復雜，簡單的coflow抽象已經無法完全表達任務的網絡需求.比如，分布式計算框架TensorFlow[8]，PyTorch[9]，MxNet[10]都采用了一種基于有向無環圖(directed acyclic graph, DAG)的運行方式.在這一類任務的執行過程中，只要某一個計算任務需要的網絡傳輸完成，那么這個計算任務就可以立即開始計算.因此，從整個任務執行的角度來說，并不是所有的網絡傳輸都是完全等同的.所以，如果我們能更加精細地利用任務的這種需求來指導網絡調度，應當能夠取得更好的加速效果.

與此同時，我們也應當注意數據中心中任務的多樣性.并不是所有的任務都是基于計算圖或者可以將計算圖提供給網絡管理者的.比如說那些運行在Spark[11]框架上的任務、視頻、音頻以及文件傳輸任務等.這些任務的性能同樣也受到網絡資源的制約，因此如果我們僅僅關注那些提供了DAG的任務，其他任務的性能就會受到很大的負面影響.

綜合以上2點考慮，我們開始思考這個問題：鑒于不同任務對于網絡需求的差異性，我們能否設計一種任務感知的網絡調度器，可以通過減少任務的完成時間從而提升整個數據中心的工作效率.

為了探索這個問題，我們提出了一種基于DAG的網絡調度器JIT(just in time).JIT利用部分任務提供的DAG來針對性地需求分析與網絡調度，從而加速這些任務的執行；與此同時，對于其他的任務，JIT也會盡量滿足它們的網絡需求，從而達到提升數據中心整體性能的目的.本文的主要貢獻總結為3點:

1)通過對任務執行過程的細致分析，我們發現一些網絡傳輸可以在被推遲的同時不影響任務的整體完成時間.因此，我們提出最晚到達時間(latest arrival time, LAT)來描述這種特征.更進一步地，我們提出了一種協同考慮DAG與網絡資源狀況的啟發式算法來計算網絡傳輸的LAT.

2)首先構建了一個整數線性規劃模型(integer linear programming, ILP)來描述基于LAT的網絡調度問題.然后，我們通過數學分析發現這個模型可以通過變換成為一個同解的線性規劃模型(linear programming, LP).通過這個轉化，就可以采用數學求解器對調度問題進行快速求解.

3)通過基于真實任務的模擬驗證了JIT的確能夠提升數據中心的整體效率.實驗結果顯示，JIT可以將提供計算圖的應用加速1.55倍，同時減少對于其他任務的影響，從而提升數據中心的整體效率.

1 研究動機與JIT結構設計

1.1 研究動機

越來越多的分布式計算框架選擇采用DAG來驅動任務的執行.在這些框架里，一個任務會被分解為許多子任務，包括計算與網絡傳輸子任務.每個子任務就是任務DAG中的一個節點，而子任務之間的依賴關系就用節點之間的邊來表示.如果從節點j到節點i的邊存在，那么節點j就是節點i的一個前驅節點.一個子任務節點在它所有的前驅節點完成之前，是無法開始執行的.由于本文的關注點在網絡調度，所以從我們的角度來看網絡傳輸子任務是沒有前驅節點的.以圖1中的簡單任務為例，在這個任務中，T1，T2是2個網絡傳輸子任務，C1，C2是2個計算子任務.T1完成之后，C1就可以開始；類似地，C2需要等待C1和T2這2個任務的完成.

Fig.1 DAG of an example job

為了更加細致地研究這一類基于DAG的任務，我們利用TensorFlow 1.13運行了一系列典型的任務，觀察它們網絡傳輸的情況.圖2中以Inception任務(包含190個網絡傳輸)為例，展示出了我們的分析結果.在圖2中，2條曲線分別表示網絡數據傳輸完成與網絡數據被后續計算使用的時間.我們發現這2個時間之間存在一個很大的差值，這意味著即使網絡傳輸完成了，但是后續的計算仍然需要等待一段時間才能開始.我們在基于TensorFlow運行的其他任務以及其他基于DAG的框架中也觀察到了類似的結果.

Fig.2 Data waiting in TensorFlow

造成這一現象的原因是計算任務不僅僅需要等待它所需的網絡傳輸數據，也需要等待它所依賴的計算節點執行完成.我們以圖1為例：假設T1，T2均在時刻0完成了傳輸，那么C1可以立即開始執行；然而，C2由于需要等待C1完成，不能立刻開始執行.因此，T2仍需要等待C1的完成，才能被C2使用，這也就產生了圖2中的時間差值.基于此，我們發現一個計算任務所依賴的傳輸任務的完成時間，只要不晚于它所依賴的前驅計算任務的完成時間，那么就不會對這個計算任務的開始時間造成延遲.

1.2 最晚到達時間

為了描述我們在1.1節中發現的這種數據等待現象，我們提出了LAT的定義.LAT表示一個網絡傳輸在不會對它后續計算造成延遲的情況下的最晚到達時間.換句話說，如果一個網絡傳輸在它的LAT之前到達，那么它的后續計算任務需要等待它的前驅計算任務完成；反之，就需要等待這個網絡傳輸的到達.

根據LAT的定義，只要滿足網絡傳輸的LAT就足夠保證任務的完成時間不被推遲.基于LAT，我們可以將一部分網絡傳輸延遲，使得它們恰好在LAT之前到達.此時，就能夠減少這些傳輸的網絡資源占用，從而可以把釋放出來的網絡資源分配給其他的任務，達到提升數據中心整體效率的目的.

同以往研究者們提出的流最終期限相比[12-14]，本文提出的LAT有2個獨特的特征：1)流的最終期限通常是由用戶指定的，用來表示它們所必需滿足的完成時間.然而，LAT是與任務的具體特征以及集群資源狀況密切相關的.因此，我們需要在任務執行的同時完成對LAT的估計.2)最終期限通常用來表示一個流必需在某個時刻之前完成.未能滿足最終期限要求的流，就會被丟棄.但是，對于LAT來說，為了滿足任務的網絡要求，即使一個網絡傳輸未能滿足LAT要求，也需要繼續完成.

1.3 JIT設計

實現一個基于LAT的網絡調度器是充滿挑戰的，我們主要需要解決3個問題：

1)LAT的不準確估計會導致調度問題不可解或者JCT增加，因此，我們需要設計算法盡量準確地估計網絡傳輸的JCT；

2)如引言所述，考慮到JIT調度器有2個調度的目標，我們需要為JIT的調度問題建立一個統一的模型；

3)考慮到JIT的實用性需求，我們需要在很短的時間內給出調度方案，同時保證方案的調度效果.

我們將在第2，3節中詳細介紹JIT是如何處理這些挑戰的.在圖3中，我們首先展示了JIT調度器的整體結構.

Fig.3 Architecture of JIT network scheduler

我們采用了中心式的架構來實現JIT.在求解調度策略之前，JIT從集群管理器與任務處獲取相關信息.在最開始，JIT需要獲取集群的基本信息，包含帶寬信息與網絡拓撲結構等.對于一個具體的任務，它需要將自己的DAG信息提供給JIT，包含網絡傳輸與計算任務的大小.相比于之前的工作[15]，JIT并不要求獲得額外更多的信息.JIT首先收集這些信息，然后基于DAG使用一個啟發式算法來計算LAT.具體的網絡調度策略則通過一個LP模型求解.JIT同時也針對實際應用場景對于求解速度的要求還進行了一些合理的簡化.最后，JIT將調度方案發送給各個機器.對于那些沒有提供DAG信息的任務，它們將占用剩余的網絡資源進行傳輸.這樣可以避免這些任務由于帶寬饑餓而無法正常完成.數據中心管理員可以選擇這一過程中具體使用的調度算法，來適應不同的場景需求.

2 LAT的估計

我們提出了一個啟發式算法來計算LAT，如算法1所示.這個算法的主要特點是同時考慮了DAG與網絡狀態，從而更準確地估計LAT.

算法1.LAT估計算法.

輸入：完成集合DoneSet=?，就緒集合ReadySet=?，待求集合TodoSet={所有網絡傳輸子任務}；

輸出：網絡傳輸i的預計LATli.

① while(TodoSet≠?或ReadySet≠?)do

② for網絡傳輸iinTodoSetdo

③ if for allj∈pred(i)andj∈DoneSetthen

④ReadySet←i;

/*將i放入ReadySet中*/

⑤ end if

⑥ end for

⑦ for網絡傳輸iinReadySetdo

⑧li=0

⑨ for網絡傳輸jinpred(i)do

我們在圖4中展示了一個示例任務的LAT計算過程.為了簡潔，我們這里只展示了一個任務的計算過程(多個任務的處理情況是完全一樣的).5個計算任務(圓形)的計算負載分別是L1=1,L2=2,L3=1,L4=2,L5=1. 4個網絡傳輸任務(方形)的大小為S1=1,S2=2,S3=2,S4=1.假設任務部署在機器3上，T1與T2是由機器1發送至機器3的，T3與T4是從機器2發送到機器3的.這里所有機器的入口與出口帶寬均設為單位1.

Fig.4 An example of LAT calculation

結合算法1來講，我們使用了3個集合來存儲網絡傳輸.DoneSet(存儲已經計算完畢LAT的傳輸)、ReadySet(存儲接下來準備進行計算的傳輸)以及TodoSet(存儲還沒有納入考慮范圍的傳輸).如果從一個網絡傳輸j所連接的計算任務到另一個網絡傳輸i所連接的計算任務之間有至少1條路徑，我們就稱j是i的一個前驅傳輸.傳輸i的所有前驅傳輸的集合我們記作pred(i).例如，在圖4中，pred(T1)=?，而pred(T4)={T1，T2，T3}.在最初，所有的傳輸都會被放入TodoSet，而其他2個集合此時均為空集.整個算法只有在所有傳輸計算完畢，也就是所有傳輸移動到DoneSet時才會終止.

算法1的第1步是將所有就緒的傳輸挑選出來.如果一個傳輸所有的前驅傳輸都已經完成了LAT的計算，那么它就進入了就緒狀態，也會從TodoSet移動到ReadySet.實質上，這個計算的順序就是網絡傳輸的一個拓撲排序.第2步，我們計算ReadySet中每一個傳輸的LAT，計算過程如算法1的行⑦～所示.傳輸i的任何一個前驅傳輸j，都會確定一個li的下界：lj，從j到i所需要的計算時間以及預計i的傳輸時間trans(i)之和.

(1)

3 調度問題建模與分析

本節首先將JIT的調度問題建模為一個ILP問題；然后，為了快速求解這個問題，我們介紹了如何將這個初始ILP模型轉化為一個等價的LP模型.此外，我們還介紹了為了加速JIT的求解速度所采用的一些簡化措施.

3.1 問題建模

(2)

由于JIT的目標是提升整個數據中心的效率，所以我們不能忽視那些沒有提供DAG的任務.考慮到這個問題，我們將JIT中的調度問題建模，記為P1：

(3)

(4)

(5)

(6)

(7)

在P1中，式(3)旨在最小化所有鏈路在整個時間范圍內的最大帶寬占用.通過實現這個目標，JIT可以避免提供DAG的任務占用過多的網絡帶寬，從而將省下來的帶寬分配給未調度的任務.這樣，JIT不僅可以加速提供那些具有DAG的任務，還可以為那些沒有DAG的任務爭取更多的網絡資源.

伴隨著這個優化目標，JIT需要滿足4個限制條件.式(4)與式(5)表示的是每個機器上入端口和出端口的總帶寬使用不能超過鏈路最大帶寬C.式(6)限制了網絡傳輸必需在它的開始時間與LAT之間完成，同時通過滿足LAT要求保證了任務的性能.最后一個條件式(7)，限制了一個網絡傳輸在開始時間之前與LAT之后的傳輸速率為0.

3.2 向非線性模型轉換

模型P1很顯然是一個ILP模型，而ILP作為NP問題通常是很難求解的[16].但是，有一類特殊的ILP可以轉換為等價的LP問題.這一類ILP需要滿足2個條件:1)目標函數是可分離的凸目標函數;2)限制條件系數構成的矩陣形成一個全幺模矩陣[17].接下來我們將證明P1模型恰好滿足這2個條件.

3.2.1 可分離凸目標函數

如果一個函數可以記為用一個單變量表示的一組凸函數的和，那么它就是一個可分離的凸函數.為了將我們P1模型中的目標函數重建為可分離的凸函數，我們使用了Flutter[18]中定義的字典序以及字典序最小化問題2個概念，介紹如下：

定義1.對于一個包含K個元素的向量，用v表示這個向量的一個非增序排列，也就是說v1≥v2≥…≥vK.

定義2.對任意2個具有K個元素的向量p,q∈K，如果p1

定義3.字典序最小化問題lexminxh(x)表示求解向量h∈K的問題，其中h是由K個關于x的目標函數組成.更加具體一點，最優解h*在x*處取得，滿足h*=h(x*)?h(x)，?x∈K.

借由定義1～3，我們可以將模型P1轉換成為等價的字典序最小化問題的模型P2：

(8)

為了求解P2模型中的字典序最小化問題，我們構造了一個關于δ的函數，定義為

(9)

其中δu是δ中第u個元素.

關于構造的函數g(δ)，我們有2個引理:

引理1.g(δ)是一個凸函數.

證明. 根據式(9)，g(δ)是一系列|δ|δu的求和，而其中每一個|δ|δu顯然是凸函數.所以，g(δ)也是一個凸函數.

證畢.

引理2.?p,q∈K,p?q?g(p)≤g(q).

證明. 假設q-p中第1個正元素的索引為r，由于p，q中的元素均為整數，也就是說qr≥pr+1.

我們首先來證明p?q?g(p)≤g(q).我們可以將左側作差：

(10)

然后，對于g(p)≤g(q)?p?q，我們通過它的逆否命題(p?q)?(g(p)≤g(q))來證明，該逆否命題也等價于p?q?g(p)>g(q).這個等價形式可以通過將式(10)中的p，q交換而獲得簡單的證明.

證畢.

基于引理1和引理2，我們將原模型P2轉換為等價的P3模型：

(11)

同時滿足式(4)～(7).

3.2.2 全幺模矩陣

現在我們來檢查模型是否滿足第2個條件：模型限制條件所構成的系數矩陣是一個全幺模矩陣.如果一個線性模型的系數矩陣滿足全幺模的條件，那么就會確定一個極點為整數點的多面體，也就是說如果這個LP模型有最優解，那么一定是整數解.

引理3.式(4)～(7)的系數構成一個全幺模矩陣.

首先，很容易確認我們模型的系數矩陣中所有元素不是0就是1，所以滿足第1個條件.

證畢.

3.3 等價LP的轉換

我們通過使用λ表示(λ-representation)技術[17]來獲得等價的LP模型.對于一個單變量w∈[0,C]∩，一個整數凸函數f:[0,C]∩→可以通過以下的方法進行線性化：

(12)

(13)

(14)

λs∈且λs>0,?s∈P,

(15)

其中,P為w所有取值的集合，在我們的問題中，P=[0,C]∩.顯然這會引入|P|個正實數變量λs并且利用這些新的變量定義了一個關于w的新組合.

?i,j∈M,?t∈T，

(16)

同時滿足式(4)～(7).

至此，原ILP模型P1轉化為等價的LP模型P4.我們可以使用LP求解器(比如Gurobi[19])來求解P4.為了表述的簡潔，我們默認JIT就是指一個采用類似求解器的調度器.

3.4 其他簡化措施

由于網絡傳輸的時間無法提前預知，因此JIT需要進行動態的求解；除此之外，一個分布式任務往往包含數百個網絡傳輸，求解一個這樣的LP模型往往需要數十秒的時間.這個時間量級對于實際場景中的網絡調度是難以接受的.基于此，我們做了2方面的針對性簡化使得JIT更加實用.

1)在LP模型中，一個任務的所有傳輸只有一部分會被納入計算.我們的建模揭示了具有較小LAT的網絡傳輸應該有更高的優先級，因此，我們可以將那些具有較大LAT的網絡傳輸看做背景流量，使用剩余帶寬進行傳輸.從DAG的角度來看，那些具有較小LAT的網絡傳輸正是在拓撲排序中比較靠前的部分.因此，我們引入了一個參數α，表示被納入LP模型中的網絡傳輸的比例(默認α=0.4，即選取拓撲排序中前40%的網絡傳輸).在4.2節中，對于α的影響也進行了討論.

2)調度器只有在某一個新的分布式任務提交第1個網絡傳輸時進行1次求解.基于對TensorFlow的運行測試，我們發現同一個任務的網絡傳輸幾乎都是同時開始的，這也支撐了我們的簡化.對于實際場景中其他沒有這種特征的任務，我們也可以采用其他的措施來降低調度開銷(比如每隔固定時間調度1次等).

結合這2種簡化機制，我們使JIT更加適合實際場景.

4 實驗分析

4.1 實驗設置

1)任務集.由于沒有公開權威的數據中心任務記錄，我們沿襲相關工作中采用已久的假設[20-21]，基于泊松分布來構建我們的任務隊列.我們選取了5種經典的深度學習任務來作為基于DAG的任務，它們分別是LeNet，AlexNet，VGG16，Inception，ResNet152.在我們的測試中，每一次的訓練迭代被視為一個任務.這些任務的相關信息總結在表1中.每一種任務的比例都是統一的25%.此外，為了驗證JIT提升數據中心性能的有效性，我們還在任務隊列中加入了一些文件傳輸的任務.這些任務的網絡傳輸大小是從{5 Gb,10 Gb,20 Gb,30 Gb,40 Gb}中選取的.所有網絡任務的發送和傳輸機器都是隨機指定的.

Table 1 Specifications of Evaluated Jobs

2)評判基準.作為比較，在實驗中我們選取了3種調度器與JIT進行比較.

① TensorFlow(v1.13).TensorFlow是一個具有代表性的基于DAG的計算框架.在它的實現中，如果一個網絡傳輸被接收機器請求，同時在發送機器上準備就緒，就會開始傳輸.在有多個網絡傳輸的情況下，它們的發送是按照隨機的順序完成的[22].

② Sincronia[23].這是一種基于coflow概念的網絡調度器.它證明了只要按照某種“正確”的順序發送coflow，不用管理coflow內部的網絡傳輸細節，就可以保證達到不超過理想時間4倍的平均coflow完成時間.它采用一種貪心策略來預測未完成coflow的傳輸順序.我們在模擬器中，按照相關的文獻說明，實現了這個調度策略.

③ TicTac[22].在這個網絡調度算法中，所有的網絡傳輸按照一個算法給定的順序依次進行傳輸.這個算法是依據任務的DAG圖來確定順序的.與JIT不同，TicTac沒有考慮多個任務的場景，它關注找到單個任務條件下的最優解.因此，在實際場景下，它的性能會受到影響.因此，我們采用了先入先出(first in first out, FIFO)+TicTac來處理多任務的情況.

3)實驗設置.我們模擬了一個包含100個機器額數據中心網絡，參照數據中心的普遍配置，機器的入端口和出端口帶寬都設為1 Gbps.我們采用了與TicTac[22]中類似的辦法，通過在TensorFlow v1.13中運行任務獲取相關的信息.此外，使用Gurobi v7.5.2作為我們的數學求解器.我們使用Python 3.6實現了一個基于流的模擬器來檢驗不同的調度策略對于任務性能的影響.

4)指標.本文旨在加速這些DAG任務的同時，降低它們的帶寬使用.因此，我們使用的評測指標主要是2個，加速比(speedup,S)以及剩余帶寬的比例(ratio of remaining bandwidth,H).

調度策略1相比于調度策略2的加速比為

(17)

剩余帶寬的比例為

(18)

4.2 實驗結果

在圖5中我們展示出了DAG任務在不同調度器下的加速比情況.可以發現，所有5種任務都在JIT的調度下取得了顯著的加速效果.總的來說，與初始的TensorFlow相比，這些任務的平均加速比為1.55；而對應到每一類任務，所取得的加速比則分別為1.34，1.53，1.70，1.81，1.39.這些任務獲取的加速效果不同的原因是傳輸的平均等待時間不同.如圖6所示，初始等待時間較長的任務，例如VGG16，就會獲得相對更好的加速效果.

Fig.5 Comparison of speedup

Fig.6 Comparison of data waiting time

至于使用coflow抽象進行調度的Sincronia，所取得的性能甚至要比初始的TensorFlow更差.這是因為coflow的抽象旨在使得coflow內部的傳輸都盡量同時完成，但是顯然基于DAG的任務中，網絡傳輸有明顯的優先級.與之對比的就是TicTac調度算法，它專注于使每一類任務都使用理想優先級進行傳輸.所以，在某些任務上，它甚至取得了比JIT更好的效果(比如LeNet，兩種調度器的加速比分別為1.40與1.34)；但是，5種任務的平均加速比卻只有JIT的81.4%(1.23相比于1.55).鑒于數據中心中往往有許多的任務并行執行，因此在實際應用場景中JIT就會更加實用.

圖6中比較了不同調度策略下的網絡傳輸等待時間.可以發現JIT可以顯著縮短網絡傳輸的等待時間.例如Inception中網絡傳輸在使用默認TensorFlow調度時，平均等待時間高達2.1 s；但是通過JIT的調度，這個時間減少了94.3%，只需要0.12 s.這個等待時間的大幅減少正好符合了我們讓網絡傳輸在正好的時間到達的初始目標.作為對比，Sincronia卻會使得這個等待時間增加，因為它會讓同一個任務的傳輸盡可能同時到達；這樣索引值比較大的傳輸甚至會等待整個任務的執行時間才會被使用.至于TicTac，在縮短等待時間上的效果遠不如JIT.作為一個考慮多任務的調度器，JIT可以更好地處理不同任務之間的網絡競爭.

為了能夠更加細致地分析JIT的性能，我們也在圖7中繪制了在Inception任務中每個網絡傳輸的具體情況.我們可以將其與圖2對比，網絡傳輸接收與使用時間之間的差異顯著縮小；這就意味著通過JIT的調度，網絡傳輸在完成后不需要等很久就會被使用，也會減少網絡資源的浪費情況.除此之外，這個結果也驗證了我們LAT計算算法的準確性以及JIT調度的有效性.

Fig.7 Data waiting time in Inception after optimization

為了評估另一個指標剩余帶寬，我們在圖8中繪制了每個調度器在將DAG任務的資源分配結束后剩余網絡帶寬的CDF圖.從圖8中，我們觀察到2方面內容:1)4種調度器剩余帶寬的最小值分別為0.173，0.175，0.173，0.334.顯然JIT的調度策略使用了更少的網絡資源，也減少了對于數據中心網絡的壓力；2)相比于其他3種調度器，JIT的剩余帶寬更加均衡，大致都在0.334～0.793.而初始TensorFlow調度下的剩余帶寬就不均衡得多，從0.173到幾乎為1的情況都有.考慮占比50%的情況，JIT與TensorFlow的剩余帶寬分別為0.665與0.556.這也意味著JIT調度之后的剩余帶寬更有利于其他的任務使用.

Fig.8 CDF of remaining bandwidth with different schedulers

為了更加直接地檢驗JIT在緩解網絡壓力上的效果，我們在圖9中展示了作為背景文件傳輸任務的完成時間.相比于在一個空的數據中心中的運行時間，這些任務在JIT下完成時間分別增加了1.20，1.30，1.45，1.75，2.10倍.而這些任務在4種調度器下的平均完成時間增加為2.23，2.05，2.23，1.56倍.Sincronia同樣可以減少任務時間的增加幅度，但是效果沒有JIT明顯.我們同樣也注意到JIT在緩解時長增加上的效果伴隨著文件大小的增加而減少.這是因為相比于較大的文件傳輸任務，小的任務可以更加有效地利用JIT的剩余帶寬.圖9的結果確認了JIT在緩解網絡壓力、提升數據中心整體效率的效果.

Fig.9 JCT of background jobs

如3.4節中所述，我們通過只選取一定比例(默認α=0.4)的網絡傳輸來優化JIT的計算速度.因此，我們在這里重點分析α的取值對于JIT調度性能的影響.α的取值分別為0.1,0.2,0.3,0.4,0.5,0.6，對應的測試結果展示在圖10中.當α從0.1增加到0.6，我們可以清楚地觀察到加速效果獲得了提升(加速比從1.09增加到1.62)；同時，剩余帶寬從48.2%減少到32.4%.這是因為一個較大的α值會將更多的網絡傳輸納入LP模型之中，相應的JIT就可以更加準確精細地控制網絡傳輸，但是會消耗更多的網絡資源.通過測試，我們選擇了0.4作為默認的α值.這是因為當α>0.4時，加速效果的提升并沒有之前那么明顯，但是求解復雜性會繼續上升.因此，我們為了性能以及效率的平衡選取了這個取值.

Fig.10 Scheduling effect of different α

在設計JIT的過程中，實用性一直是我們關注的一個重點，也就是說JIT應該有較短的求解時間.因此，我們在圖11中記錄了求解LP問題的耗時.在圖11中，任務的數目(我們選取的是VGG16)從10增加到80，運行時間通過多次測試求得平均值.從圖11中看出JIT的求解過程是相當高效的：甚至在任務數目增加到70時，求解時間依然小于1 s.這個時間在實際應用場景下是可以接受的，也支持了JIT擴展到更大規模的可能性.JIT的可擴展性主要來自2個方面的原因：1)我們將其建模成為了一個高效的LP模型；2)我們對其進行了針對性的求解時間優化.

Fig.11 Computation time of JIT linear program at different scales

5 相關工作

由于JIT的目標是在加速基于計算圖的任務，同時也減少對于其他任務的影響，它就與流調度和基于計算圖的優化技術有重疊的部分.在這2方面都已經有許多研究工作，本節介紹一些與JIT最為相關的工作.

1)流調度技術.傳統的流調度技術目標往往是減少流完成時間[3-4]、提升流之間的公平性或者維持整個網絡的負載均衡[5-6].但是，這些工作都忽視了任務級別的網絡需求，因此難以提升任務的性能.意識到這個缺陷之后，Varys[15]意圖通過減少一個任務中2個計算階段之間所有流(也就是coflow)的最大完成時間來加速任務的執行.在這之后，如何基于任務的具體特征來進行網絡調度的工作也逐漸增多.Tian等人[24]提出在多階段的任務中，coflow之間也是存在依賴關系的，并為此提出了一個近似調度算法；Im等人[25]發現在某些任務中，即使一個coflow只完成了一部分，對于任務來說也是有意義的，所以他們的目標是尋求最大化coflow的部分吞吐量；此外，Tian等人[26]還提出了一種新的流量抽象MacroFlow，用來定義coflow傳輸到同一個機器的流的集合，并通過這個抽象來加速每一個機器上的任務執行；Xu等人[13]研究了有deadline和沒有deadline的coflow在一起的混合調度問題.與以往這些工作不同，JIT通過對于任務網絡需求更加細致的分析，從而提供更高效的調度方案.

2)基于計算圖的任務的優化.伴隨著集群規模的增加，網絡越來越容易成為性能的瓶頸，這對于現在很多基于計算圖的框架來說尤為突出.為此，研究者們提出了很多優化手段，大致可以分為2類：數據壓縮[27-29]與網絡調度[22,30-35].其中，第2種的目標是通過網絡調度來提升性能，因此也與我們的工作更加相關.在TicTac[22]中，作者依據DAG圖指定每一個任務中網絡傳輸的嚴格順序.但是，對于多任務場景下存在的網絡競爭沒有考慮.Wei等人[32]通過優先傳輸對于模型收斂更加重要的網絡傳輸來加快任務執行，但是他們沒有充分挖掘DAG所提供的信息.BytePS[34]在多種不同框架中實現了它們提出的單任務調度策略，但是它與TicTac一樣沒有考慮多任務的處理.MLNet[35]則旨在通過控制流量來緩解網絡擁塞.與以上的調度技術相比，JIT更深層次地挖掘了DAG所提供的網絡需求信息，并且基于此，提出了LAT來指導網絡調度.

6 討 論

我們針對實際應用中JIT可能遇到的問題進行2點討論.

1)LAT估計準確性對于JIT性能的影響.由于網絡的動態性以及復雜性，很難達到對于LAT的準確估計.在我們的實驗中(圖7)，可以看出在JIT調度之后，網絡傳輸的完成時間與使用時間也是不完全相等的.但是相比于其他調度手段，JIT已經大大減少了它們之間的差異，從而縮短了任務的完成時間.此外，在實際的使用中，我們還可以通過周期性地計算LAT來進行調度、提升對于網絡資源情況的掌握程度等來提高LAT預測的準確率以及提升JIT的調度效果.這也是我們未來工作的一個方向.

2)JIT對于極短流的處理.由于JIT是一個集中式的網絡調度器，因此對于那些傳播時間很短的網絡流，也稱為極短流，并不是很適用.相比于很短的傳輸時間，計算以及調度的開銷就顯得更加突出.但是我們注意到，JIT在滿足DAG任務網絡傳輸需求的同時最小化了它們的帶寬占用，以期將更多的帶寬分配給其他的網絡流，從而提升數據中心的整體性能.因此，我們可以換一個角度，將這些極短流作為背景流量處理，通過JIT的調度，提升它們的網絡資源分配，從而達到整體調度的目的.

7 結 論

在數據中心中，網絡帶寬通常都是稀缺資源.目前我們大多通過減少傳輸數據的大小或者流完成時間進行優化.但是由于缺少對于網絡傳輸與計算之間關系的清晰認識，這些手段往往難以有效提升網絡資源的利用效率.比如，實際情況下網絡傳輸完成之后甚至還需要繼續等待一段時間才會被后續的計算使用.基于我們對于DAG任務的觀察，在本文中提出了一個新的JIT調度器.JIT的目標是通過減少傳輸完畢后的等待時間來加速任務的執行.為了達到這個目標，我們提出了LAT縮短傳輸的等待時間，同時減少任務的網絡資源占用.我們設計了一個同時考慮網絡狀況以及DAG信息的啟發式算法來計算LAT.基于LAT，將整個調度問題建模為一個ILP模型，目標是在滿足LAT的同時減少網絡占用.通過數學分析，我們成功地將初始的ILP模型轉化為了等價的LP模型，并且還針對性地利用合理簡化將JIT的運行時間減少至不到1 s.通過詳實的實驗分析，我們展示了JIT可以提供1.55的加速比，同時有效減少它們的網絡占用，從而成功提升數據中心的整體效率.