一種基于DAG的網(wǎng)絡(luò)流量調(diào)度器

時(shí) 洋 文 梅 費(fèi)佳偉 張春元

(國防科技大學(xué)計(jì)算機(jī)學(xué)院 長沙 410073) (國防科技大學(xué)并行與分布式處理國防科技重點(diǎn)實(shí)驗(yàn)室 長沙 410073)

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

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

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

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

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

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

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

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

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

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

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

1.1 研究動(dòng)機(jī)

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

Fig.1 DAG of an example job

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

Fig.2 Data waiting in TensorFlow

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

1.2 最晚到達(dá)時(shí)間

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

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

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

1.3 JIT設(shè)計(jì)

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

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

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

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

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

Fig.3 Architecture of JIT network scheduler

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

2 LAT的估計(jì)

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

算法1.LAT估計(jì)算法.

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

輸出：網(wǎng)絡(luò)傳輸i的預(yù)計(jì)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

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

Fig.4 An example of LAT calculation

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

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

(1)

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

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

3.1 問題建模

(2)

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

(3)

(4)

(5)

(6)

(7)

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

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

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

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

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

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

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

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

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

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

(8)

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

(9)

其中δu是δ中第u個(gè)元素.

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

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

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

證畢.

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

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

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

(10)

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

證畢.

基于引理1和引理2，我們將原模型P2轉(zhuǎn)換為等價(jià)的P3模型：

(11)

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

3.2.2 全幺模矩陣

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

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

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

證畢.

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

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

(12)

(13)

(14)

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

(15)

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

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

(16)

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

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

3.4 其他簡化措施

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

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

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

結(jié)合這2種簡化機(jī)制，我們使JIT更加適合實(shí)際場(chǎng)景.

4 實(shí)驗(yàn)分析

4.1 實(shí)驗(yàn)設(shè)置

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

Table 1 Specifications of Evaluated Jobs

2)評(píng)判基準(zhǔn).作為比較，在實(shí)驗(yàn)中我們選取了3種調(diào)度器與JIT進(jìn)行比較.

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

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

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

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

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

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

(17)

剩余帶寬的比例為

(18)

4.2 實(shí)驗(yàn)結(jié)果

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

Fig.5 Comparison of speedup

Fig.6 Comparison of data waiting time

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

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

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

Fig.7 Data waiting time in Inception after optimization

為了評(píng)估另一個(gè)指標(biāo)剩余帶寬，我們?cè)趫D8中繪制了每個(gè)調(diào)度器在將DAG任務(wù)的資源分配結(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ò)資源，也減少了對(duì)于數(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)度之后的剩余帶寬更有利于其他的任務(wù)使用.

Fig.8 CDF of remaining bandwidth with different schedulers

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

Fig.9 JCT of background jobs

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

Fig.10 Scheduling effect of different α

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

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

5 相關(guān)工作

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

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

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

6 討 論

我們針對(duì)實(shí)際應(yīng)用中JIT可能遇到的問題進(jìn)行2點(diǎn)討論.

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

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

7 結(jié) 論

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