面向GPU 集群的動態資源調度方法

2023-06-07 03:40:26傅懋鐘胡海洋李忠金

計算機研究與發展 2023年6期

傅懋鐘胡海洋李忠金,2

1 （杭州電子科技大學計算機學院杭州 310018）

2 （浙江省北大信息技術高等研究院智能軟件技術與應用研究中心杭州 311215）

深度學習（deep learning，DL）技術已被廣泛應用于眾多業務場景，研發人員根據業務場景的目標特征構建深度神經網絡（deep neural network，DNN）模型，并在特定數據集上反復訓練，直至模型精度維持在一個預期的水平，從而達到在業務場景中對目標行為進行預測的目的.隨著業務場景的復雜程度提高，需要結構更加復雜且層數更多的DNN 模型來獲得更高的精度.同時，數據集的規模也在不斷地增長，導致訓練一個DNN 模型需要很長時間.因此，通過構建分布式深度學習（distributed deep learning，DDL）任務，在GPU 集群上對DNN 模型進行訓練，從而加快訓練的過程[1]，受到了工業界和學術界的廣泛關注.主流的機器學習框架，如PyTorch[2]，TensorFlow[3]，都對DDL 提供了完整的技術支持.

不同于大型公司或企業所部署的高性能計算中心[4-5]這類高度專業化的平臺，考慮到GPU 設備的成本和組建難度，眾多中小型企業、研究所和高校通常會采購GPU 服務器組建一個小規模的GPU 集群來處理多個用戶的DDL 任務，如圖1 所示.GPU 集群的計算資源有限，且各GPU 服務器的算力、內部通信方式等處于異構性質，如何對其進行高效的資源調度具有重要意義.

Fig.1 Application scenarios of GPU cluster圖1 GPU 集群的應用場景

現有的集群調度器，例如Yarn[6]，Mesos[7]，Kubernetes[8]，在對DDL 任務調度時表現出資源分配不當、運行效率不高的問題，從而無法滿足用戶需求.例如，在某實驗室使用Yarn 進行資源管理的GPU 集群[9]中，同一機架和跨機架分別采用InfiniBand 和以太網對GPU 設備之間進行互聯，由于GPU 設備間的帶寬差異，不同資源布局方式會導致DNN 模型的訓練效率不同，該集群上的歷史調度日志表明該集群的平均資源利用率僅有50%.此外，對于集群用戶而言，任務截止時間是衡量用戶滿意度的關鍵指標，根據文獻[10]中的研究得知，在大多數情況下，用戶可以接受在截止時間之前完成的任務，而當任務結束時間超過截止時間時，用戶對于集群的性能滿意度會大幅度下降.

基于以上分析，本文提出一種面向GPU 集群的動態資源調度（dynamic resource scheduling，DRS）方法，以解決異構GPU 集群環境下具有截止時間需求的多DNN 調度問題.DRS 考慮了帶寬差異和資源布局對任務訓練時間的影響，并結合截止時間需求指導資源方案的生成，其目標在于優化截止時間保證率和集群節點的資源利用率.

本文的主要貢獻包括4 個方面：

1）基于Ring-AllReduce 通信架構下的DNN 模型迭代特征和GPU 設備間的帶寬差異，構建了資源-時間模型，以計算不同資源方案下的任務運行時間.該模型能夠較為充分地體現分布式DNN 訓練的特征以及異構帶寬所帶來的影響.

2）根據資源數量、任務運行時間和任務截止時間構建了資源-性能模型，利用該模型篩選多個滿足截止時間需求的資源方案并得到最優方案，以提高資源利用效率.

3）結合資源-時間模型、資源-性能模型以及資源布局，設計了DRS 算法，進行DDL 任務的資源方案決策.再基于最近截止時間原則選擇調度任務，進行實際資源分配，以最大化截止時間保證率并提高集群節點的資源利用率.此外，還引入了遷移機制減少動態調度過程中出現的資源碎片.

4）在一個包含4 個節點，每個節點有4 個NVIDIA GeForce RTX 2080 Ti 的GPU 集群上，使用到達時間服從泊松分布的DDL 任務隊列，并對DRS 進行了對比實驗.結果表明，相較于對比算法, DRS 的截止時間保證率提升了39.53%，資源利用率達到了91.27%.

1 相關工作

隨著DL 技術的發展和大規模應用，許多專家和學者對GPU 集群資源調度上的優化指標進行了研究，現有相關工作主要從減少任務完成時間和提升集群性能指標這2 方面進行研究.

為減少任務的完成時間，文獻[11]提出了基于GPU 集群的任務調度算法Optimus，該算法通過預測訓練過程中的模型收斂性，建立性能模型來估計模型的訓練速度，并利用貪心策略分配計算資源，最小化任務完成時間.然而，該工作僅考慮任務自身的完成時間，無法保證用戶需求的截止時間.文獻[12]構建了一個任務性能模型，以量化分布式訓練中不同并行方式下的模型分區形式和對系統可伸縮性的影響，確定任務的最優資源方案，使得任務的完成時間最小化.然而，該工作采用靜態配置的方式完成資源分配，不能根據集群負載和任務運行情況動態地調整資源分配方案.文獻[13]提出了基于強化學習技術的任務調度器Chic，通過集群調度日志不斷優化學習模型和決策任務的最優資源方案.然而，當集群規模擴展時需要收集新的日志并耗費額外時間重新訓練，導致該方法不能很好地擴展.文獻[11-13]的工作均以參數服務器（parameter server，PS）[14]方式作為分布式訓練的通信架構，本文則基于Ring-AllReduce[15]通信架構進行研究，它能夠減少GPU 之間的通信開銷.

文獻[16]提出了集群調度框架Gandiva，借助透明遷移和分時作業，使多個DDL 任務在不同時刻復用GPU 設備，從而提高資源利用率.然而，該工作以提升資源利用率作為優化目標，而不是最大化截止時間保證率.文獻[17]提出了基于云PS 架構的資源配置框架Cynthia，通過資源消耗的性能分析模型預測任務的完成時間，從而提供最優成本收益下的資源分配方案.然而，該工作關注的是資源成本需求，而不是截止時間需求.文獻[18]則設計了面向服務質量感知的動態調度框架GENIE，它借助負載預測估計任務的完成時間，得到預期運行時間內的最優資源方案，最大化集群服務質量.然而，該工作限制資源分配為對稱形式并遵循整合約束[19]來獲得PS架構的最優訓練效率[11]，導致集群中存在空閑的GPU設備無法立即使用，造成任務排隊延遲和資源利用率不足[20].

現有相關工作能夠較為有效地解決GPU 集群的資源調度問題，但其中嘗試結合資源分配、資源布局和截止時間需求的研究工作較少，對于異構環境下最大化截止時間保證率仍存在一定的局限性.本文提出的DRS 方法，基于Ring-AllReduce 通信架構，將資源配置、資源布局和截止時間需求相結合，能夠最大化截止時間保證率并提高集群節點的資源利用率.

2 系統模型

本節主要介紹異構GPU 集群場景下的動態資源調度模型、基礎模型、資源-時間模型、截止時間模型以及資源-性能模型，以及對目標函數進行了描述.

2.1 動態資源調度模型

本文提出的DRS 框架如圖2 所示.用戶提交含有截止時間需求的DDL 任務到達GPU 集群時，會被放置到一個等待隊列中.調度器在感知等待隊列有新的任務加入或者集群上有任務運行結束時，便執行調度算法，選擇DDL 任務至GPU 集群運行.在此過程中，首先利用時間模型獲取任務在不同資源方案下的運行時間；其次利用性能模型指導DDL 任務的最優資源方案生成；然后基于最近截止時間原則選擇調度任務；最后進行資源分配確定資源方案的物理資源位置，生成含有節點序號和GPU 數量的運行方案.借助機器學習框架API 在GPU 集群服務器上啟動任務運行腳本，完成資源調度過程.并引入遷移機制減少調度過程中出現的資源碎片.

Fig.2 DRS framwork圖2 DRS 框架

2.2 基礎模型

對于一個GPU 集群而言，需要提供自身所包含的節點數量和每個節點上的空閑GPU 數量等信息，以供調度算法進行決策.本文使用R={Nodei(s,cfree)|1 ≤i≤Nnode}來表示集群的資源列表，其中，Nnode是集群的節點總數，Nodei(s,cfree)表示節點對象，s和cfree分別表示節點對象的序號以及空閑GPU 數量.

當任務被提交到集群時，任務本身應包含DNN模型訓練的所有必需信息.本文將一個任務對象表示為t=〈Pmodel,Pdataset〉，其中Pmodel和Pdataset分別表示任務對象所攜帶的模型和數據集屬性.具體來說，Pmodel包含了模型名稱、模型結構和模型參數量Nparam等信息；Pdataset包含了數據集名稱、數據集大小Sdataset、批次大小Sbatch和迭代回合Nepoch等信息.

DDL 任務的一個資源配置方案則使用Rt={Nodei(s,cused)|1 ≤i≤Nnode}來表示，其中，cused表示任務在序號為s的節點上所使用的GPU 數量.

2.3 資源-時間模型

在分布式深度學習場景下，模型訓練通常采用分布式數據并行[21]的方式來完成，如圖3 所示.分布式數據并行首先通過在多個GPU 設備上裝載完整的DNN 模型副本；然后將數據集均分為多個子數據集并分配到各個GPU 設備上，并保證每個GPU 設備上所持有的數據集各不相同；最后每個GPU 設備獨立地對DNN 模型副本進行迭代訓練，并在每次更新自身DNN 模型參數之前與其他設備借助網絡通信交換梯度參數，使用平均后的梯度參數對自身DNN模型權重進行更新.由于增加了DNN 模型對于數據集的吞吐率，因而實現了DNN 模型訓練加速的目的.Ring-AllReduce 通信架構能夠有效減少參數同步階段所需要的通信時間，目前已成為主流機器學習框架中分布式訓練模塊的默認選擇.該架構將參與訓練的所有GPU 在邏輯上以環形的方式相互連接，每個設備在環上都有各自相鄰的其他設備，參數同步時將自身參數發送給右鄰居設備，同時接收從左鄰居設備發送過來的參數，如圖4 所示.同一節點上的GPU設備借助PCIe（peripheral component interconnect express）和QPI（quick path interconnect）進行通信，節點和節點之間則借助InfiniBand 進行通信，其中虛線部分便是Ring-AllReduc 通信架構在邏輯上所組織的環形結構.后續的時間、性能模型和對比實驗中的DNN 模型訓練過程都將基于Ring-AllReduce 架構進行.

Fig.4 Ring-AllReduce communication architecture圖4 Ring-AllReduce 通信架構

采用分布式數據并行進行模型訓練的DDL 任務的實際運行時間主要由2 部分構成：第1 部分是在單個GPU 設備上的計算時間；第2 部分是參數同步階段所花費的通信時間.本文將DDL 任務在某個資源方案下的實際運行時間Trun表示為：

其中Tstep是模型訓練一個批次大小的數據集所花費的時間，Nstep是模型在一個迭代回合中可輸入的一個批次大小的數據集個數.隨著任務在集群上的運行時間的增加，Nepoch會逐漸減少，直至為0，此時DNN模型訓練結束.

Tstep由單個GPU 設備上的計算時間Tcal和設備間的通信時間Tcomm所組成，其計算公式為：

Nstep會隨著資源方案所包含的GPU 總數不同而發生變化，數量越多，則Nstep會相應地減少.Nstep，Sdataset，Sbatch和GPU 總數NGPU在分布式數據并行訓練過程中的關系為：

其中NGPU由資源方案上每個節點的cused累加得到，由于Sdataset和Sbatch保持不變，因此NGPU的增加會使得Nstep減少.

計算時間Tcal和模型計算量以及GPU 設備的物理環境有關，通過在真實環境下對模型進行少量迭代來獲得真實的Tcal值.通過將模型放置在單個GPU設備上進行若干批次的迭代，并記錄對應的運行時間，由于不涉及多設備通信，因此該運行時間僅包含Tcal.將單個GPU 設備上的計算時間Tcal表示為：

其中是若干次迭代的運行時間，是相應的迭代次數.在計算任務實際運行時間Trun時，對于深度學習這類長時間運行的任務來說，若干次迭代的時間可以被忽略不計.

如果不存在通信時間，那么任務的運行時間Trun和資源方案所包含的GPU 總數NGPU將為反比關系，即隨著NGPU上升，Trun將會成比例下降.而存在通信時間時，則會導致運行效率的下降.由于GPU 設備可能被部署在集群的多個節點上，因而設備間可能涉及跨節點通信.在本文中，根據文獻[15]中的理論，將Ring-AllReduce 通信架構下的通信時間Tcomm表示為：

其中B是設備之間的帶寬速度，如果資源方案所包含的GPU 設備都處于同一個節點上，則B就是節點內GPU 設備之間的帶寬，如果包含的GPU 設備跨多個節點，則B就是節點間的網絡帶寬.

2.4 截止時間模型

本文設用戶對于任務的截止時間需求由任務到達時間、任務優先級以及任務最大運行時間所組成，其中最大運行時間是任務僅在單個GPU 設備上的運行時間.由于任務結束時間和任務到達集群后的排隊時間、集群空閑資源情況以及所使用的資源調度算法有關，對于GPU 集群的用戶而言，在提交DDL任務時，通過指定任務優先級來表示任務的緊急程度比預估一個合理的截止時間要來得容易.為了簡化該問題，本文根據文獻[22]中的研究，定義若干任務優先級，將優先級轉換為任務的期望運行時間Texp，其計算公式表示為：

其中 α對應任務優先級，α值越小說明優先級越高，而則是任務在單個GPU 設備上的運行時間.

設任務的到達時間和運行開始時間分別為Tarr和Tstart，則任務的截止時間Tdl和運行結束時間Tend可分別表示為式（7）和式（8）：

當任務的截止時間Tdl和運行結束時間Tend滿足式（9）時，說明任務運行結束時滿足用戶的截止時間需求.

2.5 資源-性能模型

在分布式深度學習過程中，存在著帶寬敏感性[20]，即2 個NGPU相同的資源方案，會由于GPU 設備的布局方式不同而造成任務運行時間上的不同，這是由于設備間的帶寬差異所造成的.當資源方案所持有的GPU 設備都位于同一節點上時，其帶寬速度為GPU設備之間的直連帶寬；而當資源方案所持有的GPU設備位于不同節點上時，其帶寬速度則為節點和節點之間的網絡帶寬.由式（5）可知，在NGPU和Nparam不變的情況下，Tcomm隨著B的減少而增加，而當設備間的帶寬性能不足以支撐分布式訓練時，就會出現多機分布式訓練的運行時間比單機訓練的運行時間要來得長的情況.將式（2）（3）帶入到式（1）中，并要求多機訓練的運行時間比單機訓練的運行時間要來得短，則可以得到不等式：

其中不等式號左邊部分和右邊部分分別表示模型在多機和單機上訓練一個迭代回合的時間，化簡式（10）可得

故當模型在進行多機分布式訓練時，Tcomm，NGPU，Tcal只有符合式（11）才能達到模型訓練加速的目的.

為了更好地展示不同資源方案以及帶寬差異對任務性能的影響.在包含4 個節點，其中每個節點包含4 個NVIDIA GeForce RTX 2 080 Ti 的異構帶寬GPU集群上測量了多個DNN 模型在不同GPU 數量下的迭代回合時間.節點內設備借助PCIe 和QPI 進行互連，其平均帶寬速度為10 GBps；節點間設備借助InfiniBand進行互連，其帶寬速度為6 GBps.參與測量的模型信息如表1 所示，模型所采用的數據集為CIFAR-100[29]，批次大小統一為16，測量結果如圖5 所示.

Table 1 Deep Neural Network Model Information表1 深度神經網絡模型信息

Fig.5 Epoch time of the DNN model under different GPU numbers圖5 DNN 模型在不同GPU 數量下的迭代回合時間

如圖5（a）所示，在異構GPU 集群環境下，DNN模型的迭代回合時間總體上是隨著GPU 數量的增加而減少.其中，VGG-16 在GPU 數量為2 以及AlexNet在GPU 數量為2 和4 時，其迭代回合時間反而比GPU數量為1 時的迭代回合時間還要長.主要原因是DNN模型屬于參數量較多的一類模型，其通信時間比起參數量較少的模型要長，在迭代一個批次的數據時，大部分時間都花費在參數同步階段.故當帶寬性能存在瓶頸時，對于DNN 模型而言，增加少量GPU 設備所帶來的吞吐率上升并不足以抵消參數同步階段的通信開銷，從而導致多機訓練無法達到訓練加速的目的.由于可能出現此類資源方案的運行時間仍能滿足截止時間需求的情況，本文方法將采用式（11）對可用資源方案進行篩選，保留可進行有效分布式訓練的資源方案，減少出現資源浪費的現象.

圖5（b）（c）分別展示了在上述環境下，VGG-16和ResNet-50 在單節點設備和跨節點設備上的迭代回合時間.可以看出VGG-16 這類參數量多的模型對于帶寬的敏感性較強，在單節點上可以得到訓練加速的效果，而在相同GPU 數量的跨節點方案上由于沒有完全抵消通信開銷而無法得到訓練加速的效果.而ResNet-50 這類模型無論在單節點還是跨節點場景下都可以得到訓練加速的效果，只是在跨節點時由于帶寬性能較低，因而導致迭代回合時間略慢于單節點.故在異構帶寬GPU 集群中，調度算法在進行資源分配時應考慮不同模型在單節點和跨節點資源布局方式上的帶寬差異，過于追求減少當前任務的完成時間而選擇單節點資源方案時，可能會造成后續到達任務在需要單節點資源方案時的排隊延遲和資源利用率的下降.

基于上述分析，為了衡量任務在不同資源方案下的性能，并在滿足截止時間需求的多個資源方案中選擇運行效率最高的資源方案，充分發揮資源性能.本文將資源方案的性能公式定義為：

式（12）表明，如果一個資源方案使用的資源數目越少且能得到的任務運行結束時間越短，則發揮的資源性能越高.

2.6 目標函數

本文方法的目標是在一個資源有限且帶寬異構的GPU 集群上，對于一個到達時間服從泊松分布的DDL 任務隊列trace={t1,t2,…,tM}，在集群資源限制和任務截止時間需求上進行權衡，確定每一個DDL任務的執行順序以及最優資源方案，最大化截止時間保證率.本文將保證率Rtrace定義為：

其中Nsati和M分別表示任務隊列中滿足截止時間需求的任務數量和隊列中的任務總數.

故將本文方法的目標函數表示為：

3 本文方法

本節介紹了資源方案決策、實際資源分配、資源遷移機制以及DRS 算法.DRS 算法將遍歷等待隊列并執行資源方案決策得到每個任務的最優資源方案，再基于最近截止時間原則選擇調度任務，并執行實際資源分配.在集群運行過程中，引入資源遷移機制減少動態調度過程中資源碎片所帶來的影響.本節將分別對資源方案決策、實際資源分配和資源遷移機制進行介紹，并展示DRS 算法的偽代碼和復雜度分析.

3.1 資源方案決策

在資源方案決策部分，首先會為等待隊列中的每個任務基于集群空閑資源和資源布局生成可用資源方案列表，然后根據2.5 節中的性能模型并結合集群節點負載情況，確定每個任務的最優資源方案.資源方案決策的步驟有4 個：

1）獲取資源列表R，并設cfree＞0的資源節點數量為n，資源節點cfree的最大值為max(cfree)及其累加和為sum(cfree)，最后初始化一個單節點資源方案列表ls和一個跨節點資源方案列表lm.

2）生成cused從1～max(cfree)的資源方案Rt添加到ls中，如果n＞1，則再生成cused從1～sum(cfree)的資源方案Rt添加到lm中.根據式（1）和式（8）計算ls和lm中Rt的Trun和Tend，并根據式（11）過濾部分資源方案Rt.

3）根據式（12）得到ls中PRt≥0且PRt最大時的資源方案Rt，設為單節點預期方案；以及ls中Tend＞Tdl且Tend最小的資源方案Rt，設為單節點非預期方案.按照相同的思路從lm中得到跨節點預期方案和跨節點非預期方案.注意其中和可能不存在.

4）如果存在且集群存在0 ＜cfree＜NGPU的資源節點，說明當前任務存在跨節點資源方案可以利用局部資源并在Tdl內結束運行，此時設最優資源方案=.如果條件不成立但存在，則設=；如果仍不存在，說明集群當前空閑資源無法令當前任務在Tdl內結束運行，則先后對和以相同的思路選擇其一作為當前任務的.

3.2 實際資源分配

1）獲取資源列表R并按照節點的cfree升序排序.

3.3 資源遷移機制

由于無法預知將來提交到集群的任務情況，動態調度方法在根據當前資源做出資源方案抉擇時就可能出現僅有的跨節點資源被當前任務所使用，在一段時間后和其他任務運行結束后釋放的資源形成資源碎片的場景.結合2.5 節可知，資源碎片會造成單個資源節點的高性能無法被單個模型充分利用.

DDL 任務的特性允許中途停止模型訓練過程并在之后任意時間點重啟，比如利用PyTorch 框架可以通過參數設置設定模型權重文件的保存時機，該權重文件會保留目前已經訓練好的參數信息和迭代次數，之后可以基于該權重文件在先前已經訓練的基礎上繼續后續的訓練過程.基于DDL 任務的這項特性，本文通過引入資源遷移機制來減少資源碎片所帶來的影響，盡可能發揮單個節點的性能優勢.資源遷移的過程如圖6（a）（b）所示，其中陰影部分表示GPU 設備正處于運行狀態，空白部分則處于空閑狀態，虛線框部分為某個運行任務的實際資源配置.

Fig.6 Resource migration圖6 資源遷移

在每次執行任務調度之前，DRS 算法將分析已運行任務情況，決定是否進行資源遷移過程.將資源列表中處于運行狀態但運行設備數量不超過自身總設備數量一半的節點定義為可遷移節點Nodem(s,cfree)，當Nodem(s,cfree)數量超過Nnode的一半時，暫停全體運行任務并執行資源遷移過程.其步驟有2 個：

1）初始化任務列表ls和lm.遍歷運行任務隊列Qrun，將原處于單節點運行的任務t添加到ls中，將原處于跨節點運行的任務t添加到lm中.

2）將ls和lm中的任務t根據的NGPU降序排序.首先遍歷ls，對其中的任務t執行3.2 節中的實際資源分配過程，然后遍歷lm，對其中的任務t同樣執行3.2 節中的實際資源分配過程.

3.4 調度算法流程

每當有新任務到達且GPU 集群存在空閑資源或有任務運行結束時，調度器會根據調度算法選擇新的任務運行.算法接收等待任務隊列Qwait、資源列表R和當前時間Tcurr作為輸入參數，其中Tcurr以單位時間增加，當DDL 任務的到達時間Tarr=Tcurr時，將任務添加到隊列Qwait中，此時會根據式（7）預先計算任務的截止時間Tdl.本文將DRS 算法的具體步驟定義為：1）根據集群資源的負載情況，嘗試執行3.3 節的資源遷移過程.2）遍歷等待隊列Qwait，對任務t執行3.1 節的資源方案決策得到t的最優資源方案.3）初始化預期任務隊列Qexp和非預期任務隊列，如果任務的運行結束時間Tend和截止時間Tdl滿足式（9），則將任務t添加到隊列Qexp中，反之則添加到隊列中.將隊列Qexp中的任務t根據Tdl-Tend的值升序排序，此時排在隊頭的任務t在資源方案下的Tend越接近Tdl.將隊列中的任務t根據Tend的值升序排序，排在隊頭的任務t在資源方案下的Tend越接近Tdl.注意隊列Qexp可能為空.4）如果隊列Qexp不為空，則選擇排頭任務t作為調度任務t*，否則選擇隊列中的排頭任務t作為調度任務t*，并對t*執行3.2 節的實際資源分配過程.

本文將DRS 算法的偽代碼表示為：

3.5 復雜度分析

執行包含資源遷移過程的DRS 算法時間復雜度為O(nN)+O(mNG)=O(N(n+mG))，其中n，m，N，G分別表示運行任務數量、等待任務數量、節點數量和節點上的最大可用GPU 設備數量.

在隨機生成到達時間Tarr符合泊松分布的任務隊列時，本文設定集群默認的任務接收時間范圍為0～24 h.默認的任務抵達率λ=4，即平均每小時有4個任務到達集群.將任務隊列的任務優先級0.5，1，1.5 的默認比例分別設置為10%，30%，60%.

除DRS 外，本文還引入了常見的調度策略和具有代表性的GPU 集群資源調度算法進行對比.

1）EDF（earliest deadline first）[36].從等待隊列中選擇截止時間最小的任務并使用整體GPU 資源進行資源分配.

2）FIFO（first in first out）.從等待任務隊列中選擇到達時間最小的任務并使用整體GPU 資源進行資源分配.

3）Themis[37].將GPU 資源根據完成時間公平性分配給多個等待任務并將任務一次性調度至集群運行，盡可能保證任務之間具有相近的完成時間.

4）NoRM（no resource migration）.為了驗證DRS引入遷移機制的有效性，將DRS 中的遷移機制部分移除之后，再與DRS 比較各種性能指標.

本文方法的目標在于最大化截止時間保證率Rtrace，因此將Rtrace作為主要性能指標.除此之外，任務平均等待時間Twait和任務平均完成時間Tcomp同樣是重要的性能指標[38].后續實驗將從Rtrace，Twait，Tcomp這3 個指標對各個調度算法進行分析比較，Rtrace依據式（13）進行計算，Twait和Tcomp則各自根據Twait=(Tstart-Tarr)/M和Tcomp=(Tend-Tarr)/M計算得到，其中M是任務隊列中的任務總數.

4 對比實驗

本節首先在異構帶寬GPU 集群上對DRS 和多種調度算法進行對比；研究了任務抵達率、節點數量、緊急任務數量、任務接收時間和帶寬性能對于各個調度算法的性能影響；使用截止時間保證率、平均等待時間和平均完成時間作為性能指標.然后還對比了各個算法在運行過程中集群總體節點的資源利用率.最后分別介紹實驗準備和各個對比實驗，并對實驗結果進行分析.

4.1 實驗準備

本文的GPU 集群包含4 個節點，每個節點有4 個NVIDIA GeForce RTX 2 080 Ti，節點內的GPU 通過PCIe和QPI 進行互連，其平均帶寬速度為10 GBps；節點間設備借助InfiniBand 進行互連，其帶寬速度為6 GBps，因此GPU 之間的通信具有異構性質.GPU 服務器運行Ubuntu 18.04 操作系統和PyTorch 1.7.1 框架，其分布式訓練API 默認采用分布式數據并行的方式進行模型訓練，并采用NCCL（NVIDIA collective communication library）通信庫[30]實現Ring-AllReduce 通信架構.

為了提升DDL 任務的多樣性，在DNN 模型方面除了采用表1 當中的圖像分類模型，還引入了用于動作識別場景下的TSN[31], R（2+1）D[32], TSM[33], Slow-Only[34]等模型，圖像分類模型依舊采用CIFAR-100數據集，而動作識別模型則采用UCF-101[35]數據集.DDL 任務可攜帶的工作負載的具體信息如表2 所示，其中計算時間是模型在上述集群單個GPU 設備上訓練一個迭代回合的時間.

Table 2 Workloads表2 工作負載

4.2 任務抵達率

本節研究了任務抵達率 λ對于各個調度算法性能的影響.在保持任務隊列其他參數不變和控制 λ=2，4，6，8，10 變化的基礎上，進行了對比實驗，實驗結果如圖7 所示.

Fig.7 Algorithm performance at different arrival rates圖7 在不同抵達率下的算法性能

由圖7（a）可知，由于資源有限，所有算法的Rtrace隨著 λ的增大而減少，其中DRS 和NoRM 的表現要優于其他算法.EDF 由于只關心任務的截止時間需求，沒有考慮實際資源配置對于任務運行時間的影響，會導致在任務數量較多時，運行時間超過截止時間的等待任務比未超過截止時間的任務優先得到了調度.FIFO 僅考慮了任務的次序而忽視了截止時間需求，當任務隊列中預先到達的都是一些長時間任務時，則后續到達的任務在短時間內都無法得到資源，導致超過截止時間的任務都無法運行.Themis 僅考慮了資源配置對任務完成時間公平性的影響，導致在調度過程中，資源優先傾向后續到達的任務，先前到達的任務則無法得到足夠的資源在截止時間內結束運行.本文所設計的DRS 算法考慮了任務的截止時間需求和資源方案性能，實現了截止時間保證率和資源利用之間的權衡，在不同 λ下的Rtrace相較于EDF，FIFO，Themis，NoRM 能夠分別提升39.53%，41.41%，45.49%，3.11%的性能.DRS 通過引入遷移機制減少了動態調度過程中資源碎片帶來的影響，性能上要略優于NoRM，證明了引入資源遷移機制的有效性.

由圖7（b），圖7（c）可知，任務的Twait和Tcomp普遍隨著 λ的增大而增大，由于資源的有限性和任務的隨機性，因此在部分 λ值之間，Twait和Tcomp會有下降的趨勢，其中DRS 的性能表現最好.DRS 基于資源方案性能為任務分配合適的設備數量，減少資源浪費，將其余資源保留給后續到達的任務，使得后續任務能夠被及時響應，同時也為任務基于現有資源確定了運行效率最高的資源方案，故在Twait和Tcomp指標表現上能夠優于其他算法.

4.3 節點數量

本節研究了節點數量Nnode對于各個調度算法性能的影響.在保持任務隊列其他參數不變和控制Nnode=2，3，4 變化的基礎上，進行了對比實驗，實驗結果如圖8 所示.

Fig.8 Algorithm performance under different numbers of node圖8 在不同節點數量下的算法性能

由圖8 可知，隨著Nnode的增加，各個算法在Rtrace，Twait，Tcomp指標上都得到了優化，原因在于節點數量的增加使得各個算法可以為更多的任務執行資源調度.EDF，FIFO，Themis 在不同集群規模下依舊基于任務自身指標確定任務執行順序，而DRS 能夠在不同集群規模下基于集群資源情況和整體任務截止時間需求動態調整等待任務的執行順序，以最大化Rtrace為前提選擇被調度任務，故其性能表現最佳.另外，圖8（a）中，DRS 和NoRM 的性能幾乎一致，原因在于資源數量對于λ=4的任務隊列來說遠遠不夠，且隊列中的任務運行時間皆較長，故在集群運行過程中，資源節點幾乎都處于滿載狀態，資源碎片出現的頻率較低，減少了DRS 執行資源遷移的次數.

4.4 緊急任務數量比例

本節研究了緊急任務數量比例對于各個調度算法性能的影響.在保持任務隊列其他參數不變和控制任務優先級α=0.5時，進行了對比實驗，實驗結果如圖9 所示.

Fig.9 Algorithm performance under different numbers of urgent task圖9 在不同緊急任務數量下的算法性能

由圖9（a）可知，隨著α=0.5的任務數量比例增加，DRS 和NoRM 在Rtrace指標上都有所下降，原因在于部分任務的截止時間縮短，需要更多的資源來滿足這部分任務的截止時間需求，但是受到集群資源的限制，無法滿足所有任務的截止時間需求，對比其他算法DRS表現依舊出色.由圖9（b）（c）可知，FIFO 和Themis 在不同優先級比例下的Twait和Tcomp完全不變，原因在于二者并沒有考慮任務的截止時間需求，因此緊急任務比例的變化沒有影響到算法的調度決策.而EDF雖基于截止時間需求決策調度順序，但是沒有結合資源配置進行考慮，依舊使用全體資源作為任務的資源配置，因此在Twait和Tcomp指標上僅有細微的變化.

4.5 任務接收時間

本節研究了任務接收時間對于各個調度算法性能的影響.在保持任務隊列其他參數不變和控制任務接收時間上限在12，24，48，72 h 變化的基礎上，進行了對比實驗，實驗結果如圖10 所示.

Fig.10 Algorithm performance at different reception time圖10 在不同接收時間下的算法性能

由圖10 可知，隨著任務接收時間的增加，各個算法在Rtrace，Twait，Tcomp指標上性能逐漸下降，這是因為對于本文集群而言，長時間接收深度學習這類運行時間普遍較長的任務，由于資源的有限性，會導致等待隊列中出現任務堆積的現象而導致性能下降.可以注意到當任務接收時間范圍在[0,12]時，EDF 和FIFO 在Rtrace指標上都有不錯的性能表現，原因在于此時的資源數量對于任務隊列來說，足夠完成大多數任務的調度安排，并且使用整體資源能夠獲得最短的運行時間，故在Tcomp指標上二者性能和DRS 相近，但是隨著等待任務的堆積，沒有合理進行資源配置的EDF 和FIFO 的總體性能不如DRS，DRS 在長時間任務接收中會根據等待任務情況和集群負載動態調整任務的執行順序，故DRS 對集群長時間接收任務的場景適應性最好.

4.6 帶寬性能

本節研究帶寬性能對于各個調度算法性能的影響.保持任務隊列其他參數不變，并控制工作負載中為AlexNet，VGG-16 這類模型占比由表2 的1/5 提升為1/3 生成限定任務隊列.將限定任務隊列和隨機任務隊列進行了對比實驗，實驗結果如圖11 所示.

Fig.11 Algorithm performance under different task queues圖11 在不同任務隊列下的算法性能

由圖11（a）可知，EDF 和FIFO 在限定任務隊列上性能表現不如隨機任務隊列.通過2.5 節可以了解到對于AlexNet，VGG-16 這類參數量大但計算時間少的模型來說，在此時的集群環境下，GPU 數量的大幅提升對于這類模型的訓練效率來說沒有其他模型來得明顯.EDF 考慮了截止時間，對于限定任務隊列來說，1/3 比例任務的截止時間都較小，故EDF 提前了這部分任務的執行順序，但也導致了其他任務的延后訓練.FIFO 沒有改變任務的執行順序，但由于任務性能提升不明顯，故這部分任務在到達集群后沒有及時得到調度，即使分配了全體資源也無法在截止時間內結束訓練.Themis，NoRM，DRS 在限定任務隊列的性能表現上都比隨機任務隊列要好，其原因在于限定任務屬于短時間任務，分配適當數量的資源并不會延長過多的運行時間，因此能盡快釋放資源到其他任務以滿足截止時間需求.由圖11（b）（c）可知，Themis，NoRM，DRS 在限定任務隊列上的性能都比隨機任務隊列優化明顯，也是由于同樣的原因.

DRS 在資源方案選擇上會過濾無效的資源方案，并考慮單節點和跨節點之間的帶寬差異，優先選擇能夠利用局部資源運行的跨節點資源方案，為后續需要單節點完整性能的任務提供條件，特別是AlexNet和VGG-16 這類工作負載，因此DRS 在限定任務隊列上的綜合表現最好.

4.7 資源利用率

本節對比了在各個調度算法的決策下集群總體節點的資源利用率，即單位時間內處于運行狀態的設備數量和總數量的比值.節點的資源利用率越高，表明動態調度過程中出現的資源碎片越少，節點性能發揮越充分.實驗結果如圖12 所示，本文記錄了FIFO，Themis，NoRM，DRS 在默認任務隊列下的性能表現.

Fig.12 Resource utilization rates in cluster nodes圖12 集群節點的資源利用率

由圖12（a）可知，FIFO 幾乎全程保持了最高的資源利用率，原因在于FIFO 每次調度時都為任務分配全體資源，并且任務數量能夠保證每次調度時都存在等待任務，此結果和原因對于EDF 也同樣適用.由圖12（b）可知，Themis 出現了間歇性的最高資源利用率，原因在于資源配置對于不同工作負載的性能影響不會完全相同，當一次性調度多個作業時，即使追求完成時間公平性，仍會出現部分任務的運行時間要遠大于其他任務的時間，導致較早結束運行的任務所釋放的資源出現了空閑現象.而由圖12（c）（d）可知，NoRM 和DRS 僅在集群運行過程的后半段出現了資源利用率逐漸下降的情況，這是因為后續到達集群的任務較少時，仍選擇性能最高的資源方案，沒有完全利用剩余的空閑資源，而DRS 因為額外引入了資源遷移機制，因此在集群運行的后半段過程中下降趨勢相比NoRM 更加平緩，二者在默認任務隊列上的總體節點資源利用率分別達到了79.13%和91.27%.

5 結束語

本文針對異構帶寬GPU 集群上對于具有截止時間需求的DDL 任務的資源調度問題，提出了一種面向GPU 集群的動態資源調度方法DRS.通過資源-時間模型得到不同資源方案下的任務運行時間，然后通過資源-性能模型對資源方案進行性能分析并選擇最優的資源方案，將資源分配、資源布局和截止時間需求相結合，最大化集群的截止時間保證率.另外，還引入了遷移機制來減少動態調度過程中產生的資源碎片.在實際的GPU 集群上進行的對比實驗證明DRS 具有可行性和有效性.在未來工作中，我們將對DRS 進一步優化，考慮集群設備的能耗問題以及設備故障后的容錯問題，嘗試結合集群調度日志研究資源伸縮的可能性.

作者貢獻聲明：傅懋鐘實施實驗方案和論文撰寫；胡海洋負責論文的修改；李忠金負責論文方案的提出和論文修改.