時 洋 文 梅 費佳偉 張春元

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

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

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

意識到這個缺陷之后，研究者們開始針對具體的應用來設(shè)計網(wǎng)絡(luò)調(diào)度的算法.其中，coflow[7]的提出是向著任務感知的網(wǎng)絡(luò)調(diào)度邁出的關(guān)鍵一步.研究者發(fā)現(xiàn)，許多分布式任務是由一定數(shù)目的處理階段按照某種順序組織而成的，而這一類任務重要的一個性質(zhì)就是2個連續(xù)階段中的后一個，無法在前一個向它傳輸?shù)乃芯W(wǎng)絡(luò)流完成之前開始.基于這個特征，coflow被定義為2個計算階段之間所有網(wǎng)絡(luò)流的總和.相比于優(yōu)化傳統(tǒng)的流傳輸指標，優(yōu)化coflow的完成時間更接近于我們加速任務執(zhí)行的目的.

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

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

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

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

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

2)首先構(gòu)建了一個整數(shù)線性規(guī)劃模型(integer linear programming, ILP)來描述基于LAT的網(wǎng)絡(luò)調(diào)度問題.然后，我們通過數(shù)學分析發(fā)現(xiàn)這個模型可以通過變換成為一個同解的線性規(guī)劃模型(linear programming, LP).通過這個轉(zhuǎn)化，就可以采用數(shù)學求解器對調(diào)度問題進行快速求解.

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

1 研究動機與JIT結(jié)構(gòu)設(shè)計

1.1 研究動機

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

Fig.1 DAG of an example job

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

Fig.2 Data waiting in TensorFlow

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

1.2 最晚到達時間

為了描述我們在1.1節(jié)中發(fā)現(xiàn)的這種數(shù)據(jù)等待現(xiàn)象，我們提出了LAT的定義.LAT表示一個網(wǎng)絡(luò)傳輸在不會對它后續(xù)計算造成延遲的情況下的最晚到達時間.換句話說，如果一個網(wǎng)絡(luò)傳輸在它的LAT之前到達，那么它的后續(xù)計算任務需要等待它的前驅(qū)計算任務完成；反之，就需要等待這個網(wǎng)絡(luò)傳輸?shù)牡竭_.

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

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

1.3 JIT設(shè)計

實現(xiàn)一個基于LAT的網(wǎng)絡(luò)調(diào)度器是充滿挑戰(zhàn)的，我們主要需要解決3個問題：

1)LAT的不準確估計會導致調(diào)度問題不可解或者JCT增加，因此，我們需要設(shè)計算法盡量準確地估計網(wǎng)絡(luò)傳輸?shù)腏CT；

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

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

我們將在第2，3節(jié)中詳細介紹JIT是如何處理這些挑戰(zhàn)的.在圖3中，我們首先展示了JIT調(diào)度器的整體結(jié)構(gòu).

Fig.3 Architecture of JIT network scheduler

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

2 LAT的估計

我們提出了一個啟發(fā)式算法來計算LAT，如算法1所示.這個算法的主要特點是同時考慮了DAG與網(wǎng)絡(luò)狀態(tài)，從而更準確地估計LAT.

算法1.LAT估計算法.

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

輸出：網(wǎng)絡(luò)傳輸i的預計LATli.

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

② for網(wǎng)絡(luò)傳輸iinTodoSetdo

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

④ReadySet←i;

/*將i放入ReadySet中*/

⑤ end if

⑥ end for

⑦ for網(wǎng)絡(luò)傳輸iinReadySetdo

⑧l(xiāng)i=0

⑨ for網(wǎng)絡(luò)傳輸jinpred(i)do

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

Fig.4 An example of LAT calculation

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

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

(1)

3 調(diào)度問題建模與分析

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

3.1 問題建模

(2)

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

(3)

(4)

(5)

(6)

(7)

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

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

3.2 向非線性模型轉(zhuǎn)換

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

3.2.1 可分離凸目標函數(shù)

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

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

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

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

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

(8)

為了求解P2模型中的字典序最小化問題，我們構(gòu)造了一個關(guān)于δ的函數(shù)，定義為

(9)

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

關(guān)于構(gòu)造的函數(shù)g(δ)，我們有2個引理:

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

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

證畢.

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

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

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

(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轉(zhuǎn)換為等價的P3模型：

(11)

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

3.2.2 全幺模矩陣

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

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

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

證畢.

3.3 等價LP的轉(zhuǎn)換

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

(12)

(13)

(14)

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

(15)

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

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

(16)

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

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

3.4 其他簡化措施

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

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

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

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

4 實驗分析

4.1 實驗設(shè)置

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

Table 1 Specifications of Evaluated Jobs

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

① TensorFlow(v1.13).TensorFlow是一個具有代表性的基于DAG的計算框架.在它的實現(xiàn)中，如果一個網(wǎng)絡(luò)傳輸被接收機器請求，同時在發(fā)送機器上準備就緒，就會開始傳輸.在有多個網(wǎng)絡(luò)傳輸?shù)那闆r下，它們的發(fā)送是按照隨機的順序完成的[22].

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

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

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

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

調(diào)度策略1相比于調(diào)度策略2的加速比為

(17)

剩余帶寬的比例為

(18)

4.2 實驗結(jié)果

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

Fig.5 Comparison of speedup

Fig.6 Comparison of data waiting time

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

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

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

Fig.7 Data waiting time in Inception after optimization

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

Fig.8 CDF of remaining bandwidth with different schedulers

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

Fig.9 JCT of background jobs

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

Fig.10 Scheduling effect of different α

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

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

5 相關(guān)工作

由于JIT的目標是在加速基于計算圖的任務，同時也減少對于其他任務的影響，它就與流調(diào)度和基于計算圖的優(yōu)化技術(shù)有重疊的部分.在這2方面都已經(jīng)有許多研究工作，本節(jié)介紹一些與JIT最為相關(guān)的工作.

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

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

6 討 論

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

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

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

7 結(jié) 論

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