來自論文Tiresias:A GPU Cluster Manager for Distributed Deep Learning
概述
給一個龐大的GPU集群，在實際的應(yīng)用中，現(xiàn)有的大數(shù)據(jù)調(diào)度器會導(dǎo)致長隊列延遲和低的性能，該文章提出了Tiresias，即一個GPU集群的調(diào)度器，專門適應(yīng)分布式深度學(xué)習(xí)任務(wù)，該調(diào)度器能夠有效率的調(diào)度并且合適地放置深度學(xué)習(xí)任務(wù)以減少他們的任務(wù)完成時間（JCT(Job Completion Time)），一個深度學(xué)習(xí)任務(wù)執(zhí)行的時間通常是不可預(yù)知的，該文章提出兩種調(diào)度算法，基于局部信息的離散化二維Gittins索引(Discretized Two Dimensional Gittins index)以及離散化二維LAS，對信息不可知并且能夠降低平均的JCT，在實驗中JCT能夠快5.5倍，相比于基于Apache YARN的資源管理
介紹
許多平臺提供方建立了GPU集群，共享給用戶來滿足日益增長的深度學(xué)習(xí)任務(wù)數(shù)量，根據(jù)Microsoft的跟蹤分析，至2016年深度學(xué)習(xí)任務(wù)數(shù)量每年增長10.5倍，高效的任務(wù)調(diào)度和智能的GPU分配是減少集群平均JCT并且最大化GPU利用率的關(guān)鍵因素.
通過觀察，得知現(xiàn)有的集群管理設(shè)計的兩個主要限制:
1. 由于訓(xùn)練時間不可預(yù)知的樸素調(diào)度
雖然最短優(yōu)先(SJF)和最短保持時間優(yōu)先(SRTF)可以被用于減少JCT，但是這兩個算法都需要任務(wù)的執(zhí)行時間，而深度學(xué)習(xí)任務(wù)的執(zhí)行時間通常是未知的，通常我們訓(xùn)練到誤差收斂為止。
我們可以做一個簡單的假設(shè)，即任務(wù)有平滑的誤差曲線，運行直到完成，在實際生產(chǎn)系統(tǒng)中可能并非如此。
目前內(nèi)部的解決方案繼承于Apache YARN的容量調(diào)度器，該調(diào)度器是為大數(shù)據(jù)任務(wù)構(gòu)建的，它只執(zhí)行基本的策略，例如非搶占的調(diào)度策略，結(jié)果是用戶會遭受長隊列延遲，甚至對于很小的任務(wù)都要等待數(shù)個小時。
2. 在任務(wù)布置方面過于激進的合并
現(xiàn)有集群管理器還嘗試將DDL任務(wù)合并到具有足夠GPU的最小數(shù)量的服務(wù)器上，舉個例子，一個需要16個GPU的任務(wù)在每個服務(wù)器都是4個GPU的集群中需要至少4個服務(wù)器，如果不能完全滿足則會被阻塞，在此之下的假設(shè)是網(wǎng)絡(luò)要盡量避免變成瓶頸或者浪費GPU周期
該文章提出了Tiresias，一個共享的GPU管理器，解決了上述的問題，即調(diào)度和放置的問題。為了保重Tiresias是實際可用的以及容易被部署，基于對生產(chǎn)任務(wù)的跟蹤的分析，訓(xùn)練細節(jié)的度量以及兩個簡單但有效的想法。除此之外，有意地讓Tiresias對用戶透明。
第一個想法
第一個想法是一個新的調(diào)度框架2DAS，可以當(dāng)任務(wù)的執(zhí)行時間不確定時減少JCT，在此框架下提出了兩種調(diào)度算法：
- Discretized 2D-LAS
- Discretized 2D Gittins index
Gittins索引策略是單服務(wù)器場景下用于優(yōu)化JCT的策略，其中JCT的分布是已知的。
同樣的，傳統(tǒng)的LAS((Least-Attained Service)算法也是被廣泛用于任務(wù)時間不可預(yù)知的場景下，例如數(shù)據(jù)中心的網(wǎng)絡(luò)調(diào)度。
上述兩個方案都是給任務(wù)一個優(yōu)先級，前者使用Gittins索引，后者直接應(yīng)用收到的任務(wù)(隨著時間會改變，任務(wù)會按照優(yōu)先級來進行調(diào)度)
使用上述策略到DDL調(diào)度問題會面對兩個挑戰(zhàn)：
- 當(dāng)計算任務(wù)優(yōu)先級的時候，我們需要同時考慮空間(GPU的個數(shù))以及時間(多久)兩個維度
- 由于優(yōu)先級會持續(xù)發(fā)生變化，任務(wù)會持續(xù)地被搶占，雖然當(dāng)開始和停止一個流是簡單的情況下，網(wǎng)絡(luò)是可以容忍的，但搶占一個任務(wù)是花費較大的，我們需要將數(shù)據(jù)和模型從內(nèi)存和GPU那復(fù)制回去。為了防止侵略性的任務(wù)搶占，應(yīng)用優(yōu)先級離散化于兩個上述算法，即一個任務(wù)的優(yōu)先級只能改變固定的值
綜上所述，有先驗的任務(wù)執(zhí)行時間的分布的情況下選用基于Gittins索引的算法，如果沒有先驗知識的話則選用LAS算法
第二個想法
第二個想法是使用模型結(jié)構(gòu)來盡可能地松弛化合并放置的約束，我們發(fā)現(xiàn)只有某些確定類型的DL模型是對是否合并是敏感的，敏感度是由于其張量大小分布的偏差。我們利用這種直覺將任務(wù)分成兩類：
- 對于合并敏感(高度偏差)
- 其他
我們實現(xiàn)了一個RDMA網(wǎng)絡(luò)分析庫，能夠通過網(wǎng)絡(luò)級別的活動判別分布式深度學(xué)習(xí)任務(wù)的模型結(jié)構(gòu)，通過利用這個庫Tiresias就可以智能地放置任務(wù)。
Tiresias首先在一個測試環(huán)境運行任務(wù)幾個迭代，然后根據(jù)之前度量的總結(jié)標(biāo)準(zhǔn)以確定最好的放置策略。
貢獻
- Tiresias是第一個對于信息不可知的GPU資源管理，也是第一個考慮了兩個維度(時間和空間)以及優(yōu)先級離散化的調(diào)度
- Tiresias使用一個簡單的，外部可觀察的，模型特殊的標(biāo)準(zhǔn)來判別什么時候放松worker的GPU合并的約束
- 該設(shè)計有實用性和易部署性，并且性能顯著提高
背景和動機
分布式機器學(xué)習(xí)(DDL)
這里，我們關(guān)注數(shù)據(jù)的并行化，數(shù)據(jù)的并行化是目前流行的分布式深度學(xué)習(xí)框架的公共部分。
如上圖所示，每一個Worker有一個GPU，運行本地的深度學(xué)習(xí)模型副本，訓(xùn)練集被劃分成等大小的部分分配給Worker們，所有的任務(wù)同步訓(xùn)練，一個被觀察到的事實是這樣的架構(gòu)能夠更快的收斂，相比于異步的分布式訓(xùn)練。
固定時間的迭代
深度學(xué)習(xí)訓(xùn)練是按迭代的方式工作的，在每一個輪次，worker要做一次前向和反向的計算，接著worker將本地的結(jié)果互相更新深度學(xué)習(xí)模型，稱之為模型聚集(Model Aggregation)，由于每一個迭代的計算時間都是差不多的，故迭代的時間是高度可預(yù)測的。
參數(shù)服務(wù)器架構(gòu)
參數(shù)服務(wù)器，簡稱PS(Parameter Server)，這種架構(gòu)是最流行的模型聚集的方法，參數(shù)服務(wù)器掌握主要的深度學(xué)習(xí)模型副本，使用從所有worker那里得到的本地結(jié)果來更新模型，然后worker在每個迭代的一開始拉回參數(shù)來更新本地的模型，一個深度學(xué)習(xí)任務(wù)可以有多個參數(shù)服務(wù)器。
測試和錯誤的探索
為了得到一個高質(zhì)量的模型，需要對超參數(shù)的各種組合進行探索，稱為超參數(shù)調(diào)優(yōu)(hyperparameter-tuning)，用戶可以用AutoML等搜索工具來進行高效的探索。在AutoML中，許多帶著不同超參數(shù)設(shè)置的深度學(xué)習(xí)任務(wù)被生成來訓(xùn)練相同的任務(wù)，其中的大多數(shù)由于隨機的誤差或者低質(zhì)量的提升會被消除。利用一開始測試階段的反饋，AutoML能夠搜索新的參數(shù)配置以及產(chǎn)生大量新的任務(wù)，當(dāng)然其中只有少數(shù)擁有較高的質(zhì)量。
挑戰(zhàn)
該文章主要針對分布式深度學(xué)習(xí)集群管理面臨的主要挑戰(zhàn)，這些挑戰(zhàn)來自于分布式深度學(xué)習(xí)訓(xùn)練的特性，并且并不特別針對Microsoft集群
不可預(yù)測的作業(yè)時間
現(xiàn)有的解決方案用于預(yù)測深度學(xué)習(xí)任務(wù)訓(xùn)練時間都假設(shè)：
- 擁有平滑的誤差曲線
- 到達他們的訓(xùn)練目標(biāo)并結(jié)束
然而，很多較弱的模型在訓(xùn)練錯誤的探索階段，它們的誤差曲線不像最好的模型那么平滑。
深度學(xué)習(xí)任務(wù)什么時候停止亦是不確定的。
通常來說，用戶會定義最大的迭代輪數(shù)以應(yīng)對當(dāng)模型到達不了預(yù)期的誤差的情況，即便如此，一個有效的資源管理設(shè)計也是不能依賴于誤差曲線進而預(yù)測任務(wù)的結(jié)束時間的。
過度侵略性的任務(wù)合并
在模型聚集階段嘗試減少網(wǎng)絡(luò)的通信在分布式訓(xùn)練中是一種通用的優(yōu)化，因為網(wǎng)絡(luò)可能是性能瓶頸并且浪費GPU周期。
然而，許多現(xiàn)存的GPU管理在放置分布式深度學(xué)習(xí)任務(wù)時盲目地遵從一個合并約束，特別地，他們將作業(yè)的所有組件（參數(shù)服務(wù)器和Worker）分配給相同或最小數(shù)量的服務(wù)器
一個分布式深度學(xué)習(xí)作業(yè)如果不能合并通常會等待，即使集群中有足夠的空閑資源，雖然這個約束是為了高性能，但是會導(dǎo)致更長的隊列延遲和低的資源利用。
為了理解這個約束的重要性，我們運行4個8GPU并發(fā)的任務(wù)，使用不同的放置策略(隨機，經(jīng)常性的合并)，在8個4GPU服務(wù)器集群上，每個任務(wù)使用8個參數(shù)服務(wù)器(和Worker數(shù)目一致)。
上述性能都以合并策略作為基準(zhǔn)進行標(biāo)準(zhǔn)化。Worker的位置主要影響了VGG系列和AlexNet。然而集群的操作者和用戶都不能告訴一個任務(wù)究竟屬于哪個類別。
搶占的時間開銷
現(xiàn)有的生產(chǎn)集群不能搶占，由于大量的時間開銷。 為了表現(xiàn)這個問題，我們?nèi)斯y試了在本地停止和重啟一個分布式機器學(xué)習(xí)任務(wù)。在停止階段，主要的Worker會記錄當(dāng)前的模型到共享的內(nèi)存，該記錄的文件當(dāng)重啟的時候會被載入。
潛在的收益
我們可以通過減輕兩個方面來獲得巨大的收益
1. 任務(wù)如果沒有確切的持續(xù)時間，就不能被很好地調(diào)度
我們可以通過日志學(xué)習(xí)到時間的分布，進而使用Gittins索引策略，該策略廣泛用于傳統(tǒng)的多臂老虎機問題，進而降低平均的JCT。即使沒有時間的分布，我們可以使用LAS算法。
2. 分布式深度學(xué)習(xí)任務(wù)應(yīng)該被經(jīng)常合并
雖然合并任務(wù)的位置可以最大程度減小通信的時間，但是我們發(fā)現(xiàn)有的分布式深度學(xué)習(xí)任務(wù)對于位置是敏感的
將智能的放置策略和調(diào)度策略結(jié)合，可以將平均JCT提高至少5倍
Tiresias的設(shè)計
主要是兩個模塊的設(shè)計，一個是調(diào)度器，一個是放置管理，以及用于學(xué)習(xí)任務(wù)特性的分析器
整體架構(gòu)
主要是圍繞兩個目標(biāo)，一個是用戶，一個是操作者
1. 最小化平均JCT
2. 高GPU利用率
Tiresias有額外的目標(biāo)來平衡上述兩個目標(biāo)
3. 任務(wù)不能無限的饑餓
給出一些實際的假設(shè):
- 在線的任務(wù)到達: 任務(wù)被用戶提交，一個任務(wù)的資源需求是給定的，但是優(yōu)先級是未知的。
- 未知的任務(wù)持續(xù)時間：由于非平滑的誤差曲線和不確定的停止，一個任務(wù)的持續(xù)時間無法預(yù)知，不過任務(wù)持續(xù)時間的分布是可以通過日志獲取。
- 未知的任務(wù)特性：一個用戶不知道也不能控制深度學(xué)習(xí)框架怎么分配tensor到參數(shù)服務(wù)器，以及相應(yīng)的偏差。
- All-or-nothing資源分配：資源服務(wù)器和Worker需要同時活躍
任務(wù)的生命周期: Tiresias目的是優(yōu)化先前的目標(biāo)，同時不需要對任務(wù)資源需求，持續(xù)時間等做任何的假設(shè)。
給出整體的架構(gòu)圖
調(diào)度
整個系統(tǒng)的設(shè)計目標(biāo)是，最小化平均JCT，增加集群利用率以及避免饑餓
我們觀察到搶占式的調(diào)度式必需的，需要應(yīng)用搶占來避免HOL(Head-of-line)阻塞，一些小的任務(wù)會被大的任務(wù)阻塞住。這是FIFO調(diào)度的缺陷，對于搶占的算法有許多，比如分時間片，SJF和SRTF。
Gandvia就是用分時間片來調(diào)度的。然而基于分時的算法目的在于公平分享達到隔離，并不是為了最小化JCT。而SJF和SRTF由于預(yù)測一個任務(wù)的持續(xù)時間很困難也不可行。只考慮GPU個數(shù)也不夠有效，需要同時考慮任務(wù)的持續(xù)時間。
為什么是二維調(diào)度
通過回顧基于時間或大小的啟發(fā)式方法，我們認(rèn)為在具有有限GPU資源的群集上調(diào)度DDL作業(yè)時，僅考慮一個方面（空間或時間）是不夠的。 在SRTF調(diào)度程序中，具有較短剩余時間的大型作業(yè)可占用許多GPU，從而導(dǎo)致許多小型但新提交的作業(yè)出現(xiàn)不可忽略的排隊延遲
如果調(diào)度程序是最小優(yōu)先（例如，GPU的數(shù)量），則即使大型作業(yè)接近完成也可能被小作業(yè)流阻塞。
這個圖比較的是:
- 最小優(yōu)先SF
- SRTF
- 最小保持服務(wù)優(yōu)先SRSF
其中前兩個是單維度的，第三個是考慮兩個維度，表將SRSF作為基準(zhǔn)進行標(biāo)準(zhǔn)化
可以看出SRSF是要比一維的調(diào)度策略要優(yōu)的
2DAS調(diào)度器
2DAS是對傳統(tǒng)LAS的擴展，同時考慮了時間和空間，它會賦予任務(wù)一個優(yōu)先級，這個優(yōu)先級和時間以及空間有關(guān)。
而這個優(yōu)先級函數(shù)有不同的情況，當(dāng)有沒有先驗知識的時候，即沒有任務(wù)持續(xù)時間的分布的時候，使用LAS算法，如果有先驗分布，則使用Gittins索引
我們將該算法和SRSF進行對比
由于SRSF是有充分的先驗知識，故平均JCT比較短為9.3，而Gittins是10，LAS是11.7
優(yōu)先級離散化
使用連續(xù)的優(yōu)先級會導(dǎo)致一系列的搶占和一系列的重啟，對于分布式深度學(xué)習(xí)任務(wù)來說，搶占和重啟的代價很高，過多的搶占會導(dǎo)致2DAS不可用，為了解決這個問題，基于傳統(tǒng)的多級別反饋隊列(MLFQ)算法實現(xiàn)優(yōu)先級離散化的框架
即，將原有的一個隊列變成K個隊列
給出一個任務(wù)的生命周期圖
放置
給定一個任務(wù)，需要參數(shù)服務(wù)器以及Worker，如果有足夠的資源，Tiresias需要知道是否在盡可能少的機器中合并一些任務(wù)的GPU或者去分發(fā)它們，前者在微軟的的生產(chǎn)集群中實現(xiàn)，故一個任務(wù)即使資源足夠也可能被放置在等待隊列。
該文章使用ILP，即瞬間線性規(guī)劃來優(yōu)化這個分配問題。
合并對于任務(wù)來說重要嗎?
深度學(xué)習(xí)模型中對于合并敏感的一般都有較大的張量， 原因是模型聚合中的消息大小與模型的結(jié)構(gòu)密切相關(guān)。 例如，TensorFlow中的模型由許多張量組成。 每個張量都被包裝為單個通信消息。因此，DDL中的消息大小分布取決于模型的張量大小分布。 張量大小通常分布不均勻; 有時存在巨大的張量，其中包含這些模型中的大部分參數(shù)。 因此，聚合較大的張量會更嚴(yán)重地受到網(wǎng)絡(luò)爭用的影響，而較小張量的傳輸往往會相互交錯。
利用這個直覺，設(shè)計了Tiresias的分析器，用于分析每個模型的偏差程度，再使用放置的算法
總結(jié)
與Apache YARN的容量調(diào)度程序（YARNCS）和Gandiva相比，Tiresias旨在最小化平均JCT。 與Optimus不同，Tiresias可以在沒有或具有部分先驗知識的情況下有效地安排工作（表2）。 此外，Tiresias可以根據(jù)Tiresias pro fi ler自動捕獲的模型結(jié)構(gòu)巧妙地放置DDL作業(yè)。
分析
給出JCT的優(yōu)化效果
平均JCT，Tiresias要高YARN-CS5倍左右，中位數(shù)JCT則最多高出27倍
GPU利用率看上去則差不多
長隊列延遲的效果
