Page 132 - 《软件学报》2020年第10期

3108 Journal of Software 软件学报 Vol.31, No.10, October 2020

于整数线性规划的调度算法的局限性在于:(a) 算法开销较大,文献[18]通过实验证明,在同等规模下,
整数线性规划算法的求解时间开销均高于启发式算法和基于打分规则的调度算法;(b) 目标函数的构
造对调度质量至关重要,对多个优化目标进行量化表示具有一定的难度.
混部作业调度算法对比见表 3.
Table 3 Comparisons of hybrid job scheduling algorithms
表 3 混部作业调度算法对比
集群 资源 性能干
名称 调度器架构 算法类型 优化目标
异构性 预测 扰预测
Paragon [40] 集中式 异构 2 3 机器学习+启发式算法 减少干扰,提升作业运行效率
Prophet [34] 集中式 同构 3 3 启发式算法 减少 AI 作业间相互干扰,提升 GPU 利用率
Mage [39] 层次化 异构 2 3 机器学习+启发式算法 减少干扰,提升作业运行效率
Hawk [48] 集中式(在线作业)+ 同构 2 2 启发式算法 提升利用率,提升作业运行效率和稳定性
分布式(离线作业)
HySARC [49] 集中式 异构 2 2 启发式算法 提升资源利用效率
Spread-n-share [43] 集中式 同构 2 3 启发式算法 提升集群的整体利用率,提升作业性能
文献[47] 集中式 同构 3 2 打分规则 提升利用率,同时保证作业性能
Bubble-up [14] 集中式 同构 2 3 启发式算法 最小化作业间的干扰,提升利用率
Medea [18] 集中式 同构 2 2 整数线性规划 最小化亲和性违反数量/资源碎片/机器
使用数量,负载均衡
Cooper [51] 集中式 同构 2 3 启发式算法 资源公平性,提升作业运行效率,减少干扰
文献[52] 集中式 同构 3 2 打分规则 最小化干扰/提升利用率,提升作业效率

调度性能方面,当集群规模较小时使用集中式调度(centralized scheduling)即可满足作业对于调度延时的要
求,集中式调度的特点是所有作业由一个中央调度器进行调度,该方法的优点是全局信息共享,可获得较好的调
度质量,采用集中式调度的在离线混部作业调度算法有文献[14,18,34,40,43,47,49,51];当集群规模逐步扩大时,
中央调度器成为作业调度的性能瓶颈,分布式调度(distributed schedulig)和层次化调度(hierachical scheduling)
采用分治的思想,使用多个调度器共同承担作业调度的压力.分布式调度是指在一个集群中同时运行多个调度
器,每个调度器只负责将作业调度至集群中的部分节点,可以实现并发作业调度.分布式调度的优点是可用性和
吞吐率高,局限性在于各调度器无法感知集群的全局信息,因此可能产生次优的调度决策.层次化调度是集中式
调度和分布式调度的折中方案,层次化调度通常设置两层调度器,作业首先由顶层调度器调度至底层调度器,再
由底层调度器将作业调度至计算节点.每个底层调度器只管理一部分计算节点,因此缩小了调度算法的搜索空
间.文献[39]采用了层次化的调度方法;文献[48]采取了集中式化调度和分布式调度相结合的调度方法,在线作
业由集中式调度器调度以获得较高的调度质量,离线作业则由分布式调度器调度以获得较短的调度延时.

2.4 在离线混部作业资源管理
本节详细介绍在离线混部作业资源管理中的资源隔离技术和资源动态分配的相关研究工作.
2.4.1 资源隔离技术
混部集群单个节点通常会部署多个作业,如 Google 的混部集群有 50%的节点同时运行超过 9 个作业 [12] .
这些作业在运行过程中依赖系统中的多种共享资源,进而产生共享资源竞争.目前解决共享资源竞争的主要方
法是通过限制作业对于共享资源的使用量,进而减少作业之间在使用共享资源时发生冲突的可能性.但是,根据
排队论原理,多个作业在竞争同一资源时的排队时间是影响作业性能的重要因素,例如多个作业同时竞争
CPU、内存带宽、网络带宽等资源,在这种情况下仅对于作业做资源使用量限制并不能完全消除作业间的资源
竞争,因此还需要对作业进行优先级划分以减少高优先级作业在竞争共享资源时的排队时间(通常在线作业会
被分配高优先级).本文根据共享资源在系统中的层次将资源隔离技术分为操作系统层的资源隔离技术和硬件
层的资源隔离技术.
操作系统层的资源隔离技术对操作系统中的共享资源进行隔离,如:
(1) CPU 时间片资源.为解决多个作业对于 CPU 的竞争,最直接的方法是利用多核体系结构的特性(如图 3