Kubeflow 異構(gòu)算力調(diào)度策略研究

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

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

0 概述

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

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

此外，GPU 的使用還需要遵循一些規(guī)則和限制，例如不同的任務(wù)對GPU 資源的最低需求不同。在當(dāng)前深度學(xué)習(xí)的算力研究中，主要內(nèi)容包括算力資源需求、算力的彈性分配、GPU 的利用率優(yōu)化、資源沖突避免機(jī)制等。目前，Kubernetes 集群中的負(fù)載均衡和GPU 調(diào)度研究主要可以分為4 類：基于預(yù)測負(fù)載均衡策略，基于訓(xùn)練流程的GPU 分配策略，基于GPU 共享的調(diào)度策略和基于多指標(biāo)的自定義負(fù)載均衡策略。

1）基于預(yù)測的負(fù)載均衡策略。文獻(xiàn)［5］構(gòu)建了Knots，提出的基于相關(guān)性的預(yù)測（CBP）和峰值預(yù)測（PP）方案實現(xiàn)了動態(tài)獲取空閑計算周期，通過動態(tài)容器編排提高關(guān)鍵型和批處理工作負(fù)載資源利用率。基于預(yù)測的負(fù)載均衡策略適合周期性任務(wù)，可以在峰值到來前提前對Pod 進(jìn)行擴(kuò)縮容，確保集群高可靠性，實現(xiàn)集群負(fù)載均衡。但是，機(jī)器學(xué)習(xí)任務(wù)突發(fā)性高，難以實現(xiàn)較好的預(yù)測。

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

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

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

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

1 原理框架

1.1 Kubeflow 中的GPU 調(diào)度方式

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

圖1 Kubeflow 中的GPU 調(diào)度Fig.1 GPU scheduling in Kubeflow

GPU 調(diào)度可以通過一個模板文件對資源使用量進(jìn)行定義。

Kubeflow 的API 可以查詢GPU 資源的可用性和使用情況。用戶也可以使用Jupyter Notebook 來創(chuàng)建、編輯和運(yùn)行深度學(xué)習(xí)任務(wù)，在創(chuàng)建用于訓(xùn)練的Jypyter Notebook 時，系統(tǒng)會將整數(shù)塊的GPU 分配給對應(yīng)的Pod，當(dāng)GPU 資源分配完畢后，在需要生成新的訓(xùn)練環(huán)境時，對應(yīng)的Pod 會因為GPU 資源耗盡而生成失敗，一直處于Pending 狀態(tài)。

1.2 細(xì)顆粒度模型

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

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

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

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

1.3 調(diào)度模型框架

在任務(wù)提交時，將任務(wù)的資源請求量和資源優(yōu)先級傳遞給資源調(diào)度模型，以便進(jìn)行靜態(tài)調(diào)度，用于初始化的訓(xùn)練環(huán)境集群生成，如圖2 所示。

圖2 調(diào)度模型Fig.2 Scheduling model

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

當(dāng)新增Pod 時，根據(jù)優(yōu)先級加入隊列。在算力滿足的條件下，通過遺傳算法優(yōu)化新請求任務(wù)和已有任務(wù)的資源分配，完成新請求任務(wù)的調(diào)度部署。

2 算法設(shè)計

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

2.1 指標(biāo)選擇

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

其中：i表示節(jié)點(diǎn)序號；g、c、m分別表示節(jié)點(diǎn)的顯存總數(shù)、CPU 核心數(shù)、內(nèi)存總數(shù)；G、C、M分別表示集群顯存總數(shù)、集群CPU 核心總數(shù)、集群內(nèi)存總數(shù)。

歸一化處理后得到最終的權(quán)重矩陣W：

2.2 編碼方式

遺傳算法的基本元素包括基因型、染色體、種群和適應(yīng)度函數(shù)。

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

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

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

假設(shè)當(dāng)前有q個Pod，則一組Pod 的調(diào)度方案也就是一條染色體，可表示為（index（節(jié)點(diǎn)），index（節(jié)點(diǎn)），…，index（節(jié)點(diǎn)））共q個元素，如圖3 所示。

圖3 染色體Fig.3 Chromosome

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

圖4 編碼模型Fig.4 Coding model

2.3 優(yōu)選函數(shù)

適應(yīng)度函數(shù)是指用于評估染色體優(yōu)劣的函數(shù)。它通常由問題的目標(biāo)函數(shù)和約束條件組成。在Kubeflow 調(diào)度問題中，適應(yīng)度函數(shù)可以是某種調(diào)度策略的目標(biāo)函數(shù)，例如本文目標(biāo)為均衡所有節(jié)點(diǎn)的算力分配。

本文提出一種適合負(fù)載均衡的優(yōu)選函數(shù)概念。優(yōu)選函數(shù)的值越小，則表示染色體的質(zhì)量越好。調(diào)度的目標(biāo)是使整個集群的負(fù)載分配最優(yōu)，也就是盡可能使得各個節(jié)點(diǎn)負(fù)載均衡。Pod 的不同以及資源占用的不斷動態(tài)變化，則無法做到集群負(fù)載完全均衡，優(yōu)化目標(biāo)就是盡可能無限逼近這個最優(yōu)解。

標(biāo)準(zhǔn)差可以衡量一組數(shù)據(jù)的分散程度，標(biāo)準(zhǔn)差越小，說明數(shù)據(jù)越集中，反之說明數(shù)據(jù)越分散。集群負(fù)載均可以由各集群負(fù)載的標(biāo)準(zhǔn)差評價。標(biāo)準(zhǔn)差σ可以表示為：

2.4 改進(jìn)的遺傳操作

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

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

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

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

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

3 實驗結(jié)果與分析

本文在本地Kubeflow 平臺上進(jìn)行了實驗，評估算法的性能、效果和時間復(fù)雜度。實驗采用常見的AI 框架和深度學(xué)習(xí)模型對CPU、GPU 任務(wù)進(jìn)行調(diào)度測試。

3.1 實驗設(shè)置

實驗以自建3 節(jié)點(diǎn)Kubeflow 為平臺基礎(chǔ)，集群各節(jié)點(diǎn)配置如表1 所示。

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

結(jié)合實驗資源配置，代入式（8）可求得集群負(fù)載的權(quán)重矩陣為：

根據(jù)集群核節(jié)點(diǎn)資源上限，利用隨機(jī)函數(shù)隨機(jī)生成個位整數(shù)，用于表示Pod 的資源請求，手動設(shè)置優(yōu)先級參數(shù)。各Pod 具體信息如表2 所示。

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

3.2 負(fù)載情況

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

表3 集群負(fù)載情況 Table 3 Cluster load situation

如圖5 和圖6 所示，CPU 以核心數(shù)計算，GPU 顯存和Men 內(nèi)存因為調(diào)度顆粒度較細(xì)，負(fù)載均衡情況較CPU 好，且GPU 相對于整體資源占用較高，為部署深度學(xué)習(xí)任務(wù)的瓶頸。

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

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

3.3 時間復(fù)雜度分析

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

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

3.4 策略分析

在滿足整體資源可用及負(fù)載均衡的條件下，共篩選出36 條滿足任務(wù)需求的染色體。如圖7 所示，調(diào)度方案的適應(yīng)度函數(shù)呈現(xiàn)明顯的優(yōu)化趨勢。集群負(fù)載對比如表4 所示。

表4 集群負(fù)載對比 Table 4 Cluster load comparison

圖7 優(yōu)選函數(shù)值Fig.7 Preferred function value

本文策略相比于Kubernetes 原生調(diào)度策略提高了GPU 對多Pod 并行運(yùn)行的支持，實現(xiàn)了一塊GPU執(zhí)行多個Pod 的優(yōu)化目標(biāo)，并實現(xiàn)了較好的負(fù)載均衡。

4 結(jié)束語

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