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）方案实现了动态获取空闲计算周期，通过动态容器编排提高关键型和批处理工作负载资源利用率。基于预测的负载均衡策略适合周期性任务，可以在峰值到来前提前对Pod 进行扩缩容，确保集群高可靠性，实现集群负载均衡。但是，机器学习任务突发性高，难以实现较好的预测。

2）基于训练流程的GPU 分配策略。文献［6］提出一种非侵入性的GPU 调度框架，结合自适应和弹性GPU 调度机制，使用训练作业进度信息来确定在不同时间的GPU 分配策略。文献［7］通过分析训练过程中的短板效应，从多个维度综合考虑模训练的优先级，以实现资源抢占和释放。文献［8］提出一种用于分布式账本技术（DLT）作业的QoS 感知联合资源优化框架，将任务的生命周期划分为提交、排队和运行阶段，并贪婪地将任务分配给主机，提高了作业的完成率和资源利用率。文献［9］将调度问题转化为最小代价二分问题的匹配问题，实现了不同计算速率负载的资源互换，在共享集群中实现资源的公平调度。文献［10］提出了一种基于拓扑结构的GPU调度框架。该框架基于传统Kubernetes 调度算法、不同的GPU 资源应用场景与基于资源访问进行调度和动态调整成本树以获得最优调度效果。文献［11］提出了一种基于机器学习的异构感知调度器，确保更高的GPU 内存利用率，减少了内存不足。基于训练流程的GPU 分配策略结合作业过程中的进度和集群等其他资源因素，能够较好地解决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 利用率并改进训练效率。基于GPU 共享的调度策略有效解决了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］设计了一种随机局部搜索方法的变体，以降低异构调度的计算复杂度。基于多指标的自定义负载均衡策略较为灵活，可以根据不同的需求定义不同的指标，在资源满足的情况下实现较好的负载均衡。但遇到突发性请求，无法解决资源请求溢出情况，仍需采用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）。

总的时间复杂度可以通过将每个步骤的时间复杂度相加得到。总的时间复杂度为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 资源进行研究，以实现机器学习任务在不同阶段下对资源的动态请求目的。