Kubeflow 異構算力調度策略研究

孫毅，王會梅，鮮明，向航

（國防科技大學電子科學學院，湖南 長沙 410000）

0 概述

機器學習被廣泛用于處理圖像分類、語音識別、異常檢測、預測等工作，通常需要處理大量的數據和進行復雜的計算，如大量的矩陣運算、卷積運算等。傳統的中央處理器（CPU）在處理計算密集型任務時會因為算力瓶頸使訓練時間過長，影響應用進度。而圖形處理器（GPU）適合進行并行計算，可以快速地處理大量數據和進行復雜的計算。因此，通常使用GPU 用于加速深度學習模型的訓練，從而提高效率和降低成本。隨著Docker 技術的發展，基于容器的資源虛擬化技術成為當前云計算主流的底層技術［1-2］。與傳統的虛擬機相比，容器具有輕量化、部署便捷、資源掛載靈活等特點。Kubernetes 是由谷歌開發的一套容器編排工具，可以自動化管理大規模的容器集群，成為云原生開發的主要選擇［3］。在Kubernetes 集群中，GPU 等異構算力資源以節點的方式加入到集群中，為集群提供異構算力。集群中的GPU 通過DevicePlugin 插件，以板卡為單位掛載給容器，實現對GPU 的調用。Kubeflow 是在Kubernetes 上運行TensorFlow 作業的一種簡單的方式，Google 將其擴展到一個多架構、多云框架，用于運行端到端機器學習工作流［4］。

在當前的Kubeflow 平臺中，GPU 調度存在以下問題：1）不支持任務優先級調度，GPU 上的任務通常以異步方式提交，先提交先執行，因此任務的執行順序無法人為干預，可能導致一些擁有高優先級的任務需要等待較長時間才能分配到算力；2）調度算法簡單，當前調度算法大多采用簡單的先來先服務（FCFS）或者循環調度算法，這些算法沒有充分考慮GPU 資源的利用率、任務的特性等因素，因此這些算法可能無法有效地利用GPU 資源，導致資源的浪費；3）不支持動態伸縮，調度器通常采用靜態分配方式，即在任務提交時將GPU 資源分配給各個任務，這種靜態分配方式可能導致GPU 資源的浪費；4）不支持細顆粒度分配，GPU 資源的分配單位為塊，當集群中的GPU 以整塊為單位掛載給某個容器后，集群其他容器無法使用該GPU。

此外，GPU 的使用還需要遵循一些規則和限制，例如不同的任務對GPU 資源的最低需求不同。在當前深度學習的算力研究中，主要內容包括算力資源需求、算力的彈性分配、GPU 的利用率優化、資源沖突避免機制等。目前，Kubernetes 集群中的負載均衡和GPU 調度研究主要可以分為4 類：基于預測負載均衡策略，基于訓練流程的GPU 分配策略，基于GPU 共享的調度策略和基于多指標的自定義負載均衡策略。

1）基于預測的負載均衡策略。文獻［5］構建了Knots，提出的基于相關性的預測（CBP）和峰值預測（PP）方案實現了動態獲取空閑計算周期，通過動態容器編排提高關鍵型和批處理工作負載資源利用率?；陬A測的負載均衡策略適合周期性任務，可以在峰值到來前提前對Pod 進行擴縮容，確保集群高可靠性，實現集群負載均衡。但是，機器學習任務突發性高，難以實現較好的預測。

2）基于訓練流程的GPU 分配策略。文獻［6］提出一種非侵入性的GPU 調度框架，結合自適應和彈性GPU 調度機制，使用訓練作業進度信息來確定在不同時間的GPU 分配策略。文獻［7］通過分析訓練過程中的短板效應，從多個維度綜合考慮模訓練的優先級，以實現資源搶占和釋放。文獻［8］提出一種用于分布式賬本技術（DLT）作業的QoS 感知聯合資源優化框架，將任務的生命周期劃分為提交、排隊和運行階段，并貪婪地將任務分配給主機，提高了作業的完成率和資源利用率。文獻［9］將調度問題轉化為最小代價二分問題的匹配問題，實現了不同計算速率負載的資源互換，在共享集群中實現資源的公平調度。文獻［10］提出了一種基于拓撲結構的GPU調度框架。該框架基于傳統Kubernetes 調度算法、不同的GPU 資源應用場景與基于資源訪問進行調度和動態調整成本樹以獲得最優調度效果。文獻［11］提出了一種基于機器學習的異構感知調度器，確保更高的GPU 內存利用率，減少了內存不足?；谟柧毩鞒痰腉PU 分配策略結合作業過程中的進度和集群等其他資源因素，能夠較好地解決GPU資源搶占問題，但是面對多任務請求時，因為板卡數量有限，無法做到有效支持。

3）基于GPU 共享的調度策略。文獻［12］針對圖形處理器-中央處理器（CPU-GPU）混合計算框架，將數據分割成大小不等的數據分片以適應CPU-GPU混合計算資源。文獻［13］提出一種GaiaGPU 方法，用于共享GPU 內存和計算資源容器。GaiaGPU 將物理GPU 劃分為多個虛擬GPU，并分配給容器作為彈性資源來提高資源利用率。文獻［14］提出了一個基于GPU 的框架ParSecureML，基于多方安全計算的機器學習算法來提高性能，并通過自適應GPU利用率，實現集群節點內CPU-GPU 細粒度協作及節點間通信的開銷壓縮。文獻［15］實現了KubeGPU，它擴展了Kubernetes，通過自適應共享策略實現GPU 共享。該策略使KubeGPU 能夠動態選擇GPU 虛擬化，根據可用的GPU 資源和容器的配置參數（如GPU 資源需求）部署容器，以實現良好的容器性能和系統吞吐量。文獻［16］提出兩種新型調度的多GPU 深度學習策略：搶占式GPU 共享和自適應批量重新分配，以最大限度地提高GPU 利用率并改進訓練效率?；贕PU 共享的調度策略有效解決了GPU 搶占的問題，可以將GPU 以vGPU 或者顯存分配的方式共享給多個Pod，但是在面對請求資源溢出時，仍然執行輪詢策略實施調度，不支持優先級調度策略。

4）基于多指標的自定義負載均衡策略。文獻［17］為了防止GPU 集群出現溫度熱點，使用非對稱劃分策略來劃分計算任務，比在計算節點之間調度子任務減少了節點之間的性能差異，提高了吞吐量。文獻［18］根據節點CPU 和內存的利用率給節點打分，加入網絡和磁盤I/O 指標，并賦予不同的權重，提高了集群所有節點的資源利用率。文獻［19］為解決多任務環境的自適應問題，提出一個可在CPUGPU 異構平臺調度多個內核的OpenCL 框架，通過隨機森林模型分析運行狀態，保證了系統執行效率。文獻［20］為了降低系統能耗，提高CPU-GPU 資源利用率，提出一種混合離子群優化（H-PSO）算法，將啟發式貪婪策略融入到仿生搜索優化技術中，實現異構資源的高效利用。文獻［21］利用設備插件機制收集每個節點上GPU 的詳細信息，并將GPU 資源指標提交給調度算法。在原有CPU 和內存過濾算法的基礎上增加自定義GPU 信息的過濾，從而篩選出符合用戶需求的可調度節點。文獻［22］設計了一種隨機局部搜索方法的變體，以降低異構調度的計算復雜度?；诙嘀笜说淖远x負載均衡策略較為靈活，可以根據不同的需求定義不同的指標，在資源滿足的情況下實現較好的負載均衡。但遇到突發性請求，無法解決資源請求溢出情況，仍需采用Kubernetes 集群原生策略。

為了更加高效地利用和管理Kubernetes 集群中的異構算力資源，解決突發性請求和資源溢出兩種特殊情況，實現集群負載均衡，本文提出一種基于優先級的改進遺傳算法異構資源調度方案，以提高整個集群資源的利用率和可靠性，加速模型訓練和部署。

1 原理框架

1.1 Kubeflow 中的GPU 調度方式

在Kubeflow 平臺中，GPU 資源的調度通常是通過Kubernetes 的GPU 插件實現的，它可以對GPU 資源進行管理和調度。當用戶提交一個GPU 任務時，Kubernetes 的GPU 插件會首先檢測系統中可用的GPU 資源，并根據用戶的要求為該任務分配一定數量（以塊為單位）的GPU 資源。GPU 插件會根據任務的需求和系統中GPU 資源的可用情況，選擇合適的GPU 設備掛載給對應的Pod。Kubernetes 集群使用DevicePlugin 插件機制來進行GPU 資源的調度，可以將特定類型的硬件資源注冊到Kubernetes 集群中，并提供API 接口來管理這些資源。當Kubernetes調度器需要為一個任務分配GPU 資源時，會通過DevicePlugin 接口來獲取可用的GPU 資源，并根據任務的需求選擇最適合的GPU 設備為任務分配，如圖1 所示。

圖1 Kubeflow 中的GPU 調度Fig.1 GPU scheduling in Kubeflow

GPU 調度可以通過一個模板文件對資源使用量進行定義。

Kubeflow 的API 可以查詢GPU 資源的可用性和使用情況。用戶也可以使用Jupyter Notebook 來創建、編輯和運行深度學習任務，在創建用于訓練的Jypyter Notebook 時，系統會將整數塊的GPU 分配給對應的Pod，當GPU 資源分配完畢后，在需要生成新的訓練環境時，對應的Pod 會因為GPU 資源耗盡而生成失敗，一直處于Pending 狀態。

1.2 細顆粒度模型

GPU-Share 技術是一種可以將多個容器間的GPU 資源進行共享的技術。在GPU-Share 技術中，每個容器都可以訪問共享的GPU 資源，并在需要時獨立地使用GPU。由于顯存是GPU 中一個重要的資源，因此在GPU-Share 中需要對顯存進行合理的管理，以保證各個容器之間的資源共享和使用的公平性。

具體來說，GPU-Share 通過使用CUDA runtime API 提供的內存池技術來管理顯存。CUDA 內存池是CUDA runtime API 中的一種內存管理方式，它可以在顯存中為多個容器分配內存，并避免內存碎片的產生。在GPU-Share 中，每個容器都有一個獨立的CUDA context，而所有容器共享同一個CUDA device。當容器需要分配顯存時，GPU-Share 將通過內存池為容器分配內存。為了保證容器之間的顯存使用公平性，GPU-Share 會為每個容器分配一個顯存配額，并記錄每個容器已經使用的顯存量。當容器需要釋放顯存時，GPU-Share 會將釋放的顯存返回到內存池中，以便其他容器可以使用。除了顯存管理外，GPU-Share 還通過cgroups 和Kubernetes 的資源管理機制來限制容器的GPU 使用量，以避免某個容器占用過多的GPU 資源而影響其他容器的正常使用。

由于原生的DevicePlugin 插件只允許以塊為單位掛載GPU，既造成了算力資源的浪費，也限制了并行任務的執行。通過更換DevicePlugin 插件實現對顯存的細顆粒度劃分，并將一塊GPU 通過劃分的顯存分配給不同的Pod。與常規調度方式的模板文件相比，limits 字段下的鍵值對由nvidia.com/gpu：1 改為ucloud/gpu-mem：1。

此時，GPU 掛載的單位為GB，而原先的掛載單位為塊，也可以添加aliyun.com/gpu-core.percentage：30 鍵值對請求顯卡算力，可以使用nvidia-smi 命令查看顯存值大小。通過使用共享內存插件，實現了對GPU 算力的細顆粒度掛載使用。

1.3 調度模型框架

在任務提交時，將任務的資源請求量和資源優先級傳遞給資源調度模型，以便進行靜態調度，用于初始化的訓練環境集群生成，如圖2 所示。

圖2 調度模型Fig.2 Scheduling model

首先初始化Pod 任務隊列，當用戶向平臺提交任務請求后，動態調度模型根據優先級將其加入隊列，再根據隊列中任務的優先級進行集群算力評估，若集群算力剩余資源無法滿足高優先級任務的算力請求，則通過輪詢的方式，按照優先級從高到低的順序判斷，低優先級的任務加入到隊列中排隊等待。當優先級較高的任務資源請求溢出時，該任務進入隊列等待，從隊列中選擇優先級最高的任務進行調度，最大化資源利用率。

當新增Pod 時，根據優先級加入隊列。在算力滿足的條件下，通過遺傳算法優化新請求任務和已有任務的資源分配，完成新請求任務的調度部署。

2 算法設計

遺傳算法是一種基于自然選擇和遺傳機制的優化算法，具有全局搜索能力和較好的收斂性，通常用于求解優化問題，它受到生物學中遺傳和進化的啟發，通過模擬生物進化的過程求解最優解。本文所研究問題的核心是GPU 顯存資源的細顆粒度最優分配，基本思想是通過模擬自然選擇、交叉和變異等過程，逐步進化出最優解［23-25］，根據Kubeflow 平臺異構資源調度特點，設計一套基于異構資源權重的遺傳算法。

2.1 指標選擇

在計算集群中，CPU 的算力通常以CPU 核心數量和頻率為指標，而GPU 的算力通常以顯存大小和CUDA 核心數為指標。通過替換Kubernetes 集群中的Nvidia.com/gpu 組件，使Kubeflow 平臺可以通過顯存分配算力，使Kubeflow 平臺在任務創建時可選擇CPU 核心數、GPU 顯存值、內存值。在算法中可選擇CPU 核心數、GPU 顯存值、內存值為評價指標。CPU 架構主要因處理不同指令集而設計，而GPU 架構更適合處理大規模并行任務，使得GPU 成為平臺調度時需要重點考慮的算力資源。Kubeflow 項目基于云部署，而不同云平臺的硬件配置不同，通過權重矩陣將Kubernetes 集群中Pod 所需和已占用的異構算力資源按照重要性賦權，以此獲得一個統一的算力評價指標。本文建立一個細顆粒度的資源調度模型，將GPU 顯存以GB 為單位進行劃分，并賦予集群資源不同權重比例，獲取Pod 調度的權重指標。模型包括4 個主要參數：請求量，優先級，權重系數和節點資源。請求量是指每個任務對CPU（NC）、GPU（NG）、內存（NM）的需求量。其中，NG是任務對集群GPU 資源中顯存的需求，NM是任務對內存的需求。優先級（P）是指每個任務的重要程度，權重矩陣W可表示為：

其中：i表示節點序號；g、c、m分別表示節點的顯存總數、CPU 核心數、內存總數；G、C、M分別表示集群顯存總數、集群CPU 核心總數、集群內存總數。

歸一化處理后得到最終的權重矩陣W：

2.2 編碼方式

遺傳算法的基本元素包括基因型、染色體、種群和適應度函數。

基因型是指單獨個體的基因組成，通常用二進制編碼來表示，例如在本文的調度問題中，每個基因表示一個Pod 在Kubernetes 集群中的調度方案，一個基因型通常由多個基因組成，可以為集群中任意一個節點。

染色體是指一個個體的基因型的集合，它可以看作是一個基因型的向量。在本文的調度問題中，一個染色體表示Kubernetes 集群中所有Pod 的調度方案。n個Pod 需要調度到Kubernetes 集群的某一個節點上，那么一個染色體包含n個基因，每個基因表示一個Pod 的調度位置。

Kubernetes 集群中往往存在多種異構算力資源，包括CPU、GPU 等不同的基礎算力，此外，集群中還可以擴展其他類型的算力資源，例如FPGA、ASIC等。為了解決異構計算節點的兼容性問題，利用集群計算節點的親和性、污點兩種標簽劃分Node 類別，在提高任務兼容性的同時最大化利用異構算力。本文以元組的形式對Pod 的調度部署進行編碼，編碼的長度隨Pod 數量的增加而增加。

假設當前有q個Pod，則一組Pod 的調度方案也就是一條染色體，可表示為（index（節點），index（節點），…，index（節點））共q個元素，如圖3 所示。

圖3 染色體Fig.3 Chromosome

在Kubeflow 的任務請求中明確了是否使用GPU 進行加速，即任務性質為CPU 的Pod 既可以調度到CPU 節點，也可以調度到GPU 節點，而當GPU任務調度到CPU 節點上時會調度失敗，如圖4 所示。種群是遺傳算法的另一個重要概念，是指由多個染色體組成的集合，每個染色體都代表一個可行解，而整個種群則代表了問題的解空間。在本文的調度問題中，種群的大小根據Kubernetes 集群節點數量和Pod 的數量，通常為幾十到幾百個染色體。先由系統隨機生成多個染色體，而后根據算力是否溢出進行取舍，得到該組染色體下的所有可行解，即獲得原始種群。

圖4 編碼模型Fig.4 Coding model

2.3 優選函數

適應度函數是指用于評估染色體優劣的函數。它通常由問題的目標函數和約束條件組成。在Kubeflow 調度問題中，適應度函數可以是某種調度策略的目標函數，例如本文目標為均衡所有節點的算力分配。

本文提出一種適合負載均衡的優選函數概念。優選函數的值越小，則表示染色體的質量越好。調度的目標是使整個集群的負載分配最優，也就是盡可能使得各個節點負載均衡。Pod 的不同以及資源占用的不斷動態變化，則無法做到集群負載完全均衡，優化目標就是盡可能無限逼近這個最優解。

標準差可以衡量一組數據的分散程度，標準差越小，說明數據越集中，反之說明數據越分散。集群負載均可以由各集群負載的標準差評價。標準差σ可以表示為：

2.4 改進的遺傳操作

遺傳操作一共有3 個大類，分別是選擇操作、交叉操作和變異操作。

1）選擇操作是指從種群中選擇個體作為下一代的父代。

2）交叉操作是指將兩個父代染色體的基因重新組合成新的子代染色體。

3）變異操作是指在種群中隨機選擇一個染色體，并隨機改變其中一個或多個基因，以產生新的個體。

結合本文編碼方式和調度模型，在進行選擇操作時，根據優選函數值排序，保留1/2 的父代染色體，舍棄函數值較低的1/2。再對保留后的染色體進行多點交叉和多點變異操作，生成新的子代染色體。在子代染色體生成后，存在資源請求溢出的可能。區別于傳統的遺傳操作，在進行子代染色體迭代前需要進行算力判斷，確保每一輪迭代后的子代染色體算力請求不溢出。通過對子代染色體進行逐一判斷，如果算力溢出，則丟棄，算力滿足則保留。通過多輪迭代后，可獲取到一個優選函數數值最小的解，該解則為最優的調度方案。

3 實驗結果與分析

本文在本地Kubeflow 平臺上進行了實驗，評估算法的性能、效果和時間復雜度。實驗采用常見的AI 框架和深度學習模型對CPU、GPU 任務進行調度測試。

3.1 實驗設置

實驗以自建3 節點Kubeflow 為平臺基礎，集群各節點配置如表1 所示。

表1 Kubernetes 集群配置 Table 1 Kubernetes cluster configuration

結合實驗資源配置，代入式（8）可求得集群負載的權重矩陣為：

根據集群核節點資源上限，利用隨機函數隨機生成個位整數，用于表示Pod 的資源請求，手動設置優先級參數。各Pod 具體信息如表2 所示。

表2 Pod 請求信息 Table 2 Pod request information

3.2 負載情況

如表3 所示，各個Pod 按照調度算法部署到了集群的各個節點中，4、5、8、9 這4 個Pod 因為資源需求量大，在滿足優先級較高任務調度和最大化集群資源利用率的條件下，暫時處于隊列中等待，且盡可能實現負載均衡，此時集群的優選函數值為0.044。

表3 集群負載情況 Table 3 Cluster load situation

如圖5 和圖6 所示，CPU 以核心數計算，GPU 顯存和Men 內存因為調度顆粒度較細，負載均衡情況較CPU 好，且GPU 相對于整體資源占用較高，為部署深度學習任務的瓶頸。

圖5 原生策略負載情況Fig.5 Native policy load situation

圖6 集群資源分配Fig.6 Cluster resource allocation

3.3 時間復雜度分析

初始化一條n個Pod 的染色體的種群編碼需要遍歷整個序列，即初始化過程需要執行n次，每次賦值操作只需常量時間，因此時間復雜度可以表示為T（n）=nO（1），因為O（1）表示常量時間，所以T（n）可以簡化為T（n）=O（n），即初始化操作的時間復雜度為O（n）。同初始化操作，即單次適應度函數的時間復雜度為O（n）。適應度排序采用快速排序算法，根據最壞情況的分析，當每次選擇的基準數都使得左右兩個子數列的差距最大，即每次都選擇數列中的最大值或最小值作為基準數時，時間復雜度即為O（n2）。而對于平均情況和最好情況，時間復雜度都為O（nlogan）。算力判斷的時間復雜度同初始化，為O（n）。

總的時間復雜度可以通過將每個步驟的時間復雜度相加得到?？偟臅r間復雜度為3O（n）+O（nlogan），在增長率方面，O（nlogan）要比O（n）更高，則通過級別最高的時間復雜度O（nlogan）可知，總的時間復雜度為O（nlogan）。

3.4 策略分析

在滿足整體資源可用及負載均衡的條件下，共篩選出36 條滿足任務需求的染色體。如圖7 所示，調度方案的適應度函數呈現明顯的優化趨勢。集群負載對比如表4 所示。

表4 集群負載對比 Table 4 Cluster load comparison

圖7 優選函數值Fig.7 Preferred function value

本文策略相比于Kubernetes 原生調度策略提高了GPU 對多Pod 并行運行的支持，實現了一塊GPU執行多個Pod 的優化目標，并實現了較好的負載均衡。

4 結束語

遺傳算法在資源利用率和負載均衡方面作用較好。本文策略在短時間內完成了Pod 部署方案的生成，提出一個適合Kubernetes 集群異構算力資源統一度量的權重矩陣，將GPU 顯存細化的最小單位確定為1 GB，可滿足基礎實驗環境生成和基礎推理，對多樣化的針對性任務部署起到了較好的支持，同時解決了Kubeflow 平臺下一個GPU 只能提供一個訓練環境的問題，并充分利用了異構算力資源。下一步將對如何動態、精確地調整Pod 資源進行研究，以實現機器學習任務在不同階段下對資源的動態請求目的。