基于两阶段深度强化学习和图神经网络的多目标云工作流调度
《IEEE Access》:Multi-Objective Cloud Workflow Scheduling With Two-Stage Deep Reinforcement Learning and Graph Neural Networks
【字体:
大
中
小
】
时间:2026年03月10日
来源:IEEE Access 3.6
编辑推荐:
摘要:在现代云计算中,云工作流调度是一个关键挑战,需要在动态条件和冲突目标(如工期、能源消耗和QoS延迟)下进行智能的任务与资源分配。传统方法往往无法有效处理复杂的任务依赖性和多目标权衡问题。本文提出了一种新颖的动态调度方法2SD-GAT,该方法结合了两阶段深度强化学习(DRL)
摘要:在现代云计算中,云工作流调度是一个关键挑战,需要在动态条件和冲突目标(如工期、能源消耗和QoS延迟)下进行智能的任务与资源分配。传统方法往往无法有效处理复杂的任务依赖性和多目标权衡问题。本文提出了一种新颖的动态调度方法2SD-GAT,该方法结合了两阶段深度强化学习(DRL)和图神经网络(GNN)来优化云工作流的执行。该方法将工作流建模为有向无环图(DAG),并使用基于近端策略优化(PPO)的两阶段代理来顺序选择任务和分配虚拟机(VM)。图注意力网络(GAT)编码器捕获工作流结构,而基于偏好的奖励函数则实现了工期、能源消耗和QoS延迟之间的权衡探索。该代理在合成数据和真实世界数据集上进行了训练。与随机、启发式和进化基线的比较评估表明,所提出的方法在超体积(Hypervolume)和逆生成距离(IGD)指标上始终表现更好,同时保持了较低的决策延迟。值得注意的是,在动态条件下,该方法在真实世界云跟踪数据上实现了26.8%的超体积增益,并将IGD降低了4.5倍,证明了其在实时多目标云调度中的有效性和可扩展性。CCBY - IEEE并非该材料的版权所有者。请通过https://creativecommons.org/licenses/by/4.0/获取全文文章和API文档中的规定。
第I节 引言
云计算已成为一种变革性的范式,提供了可扩展且灵活的计算资源,推动了各个行业的技术进步[2]。然而,云服务的快速增长加剧了能源需求,数据中心在全球范围内消耗了大量电力[3]。因此,高效的资源管理不仅对性能至关重要,也对可持续性具有关键意义。虚拟化在此领域发挥着核心作用,它使得在共享基础设施上执行各种工作负载成为可能。其中,作为有向无环图(DAG)建模的工作流应用程序由于其复杂的任务依赖性而面临独特的调度挑战[4]。为了管理这些工作负载,云平台依赖于调度器将任务分配给虚拟机(VM),同时优化多个通常相互冲突的目标,如工期、能源消耗和延迟[1]。
云系统中的调度是一个NP难的组合优化问题[5]。传统方法,如静态启发式和元启发式算法,往往难以适应现代云环境的动态特性。这些方法通常假设对任务和资源有完整的先验知识,但由于运行时的不确定性(如可变执行时间和资源故障[6][7]),这种情况在实践中很少出现。此外,现有解决方案未能充分解决基于DAG的工作流中固有的复杂依赖性问题,同时平衡多目标。这一限制凸显了需要能够实时导航性能与能源效率之间权衡的自适应、智能调度策略的必要性。
云调度还涉及多个经常相互冲突的目标:最小化工期、能源消耗、延迟、成本等[8]。其中,工期和能源消耗尤为重要。随着云基础设施的增长和能源密集型AI工作负载的增加[9],优化电力使用成为实现全球可持续性目标(如《巴黎协定》[10][11]的关键关注点。
最近的研究探索了深度强化学习(DRL)作为动态调度问题的有希望的解决方案[12]。在DRL中,代理通过与环境交互并接收反馈来学习最佳的任务放置策略。虽然现有的DRL应用程序通常针对独立任务,但工作流需要多层次的决策,包括工作流选择、任务排序和VM分配。最近,图神经网络(GNN)因其在图结构数据中捕获依赖性的能力而受到关注。尽管将GNN与DRL结合用于云环境中的工作流调度的研究仍有限,但GNN在相关领域(如灵活作业车间调度问题(FJSSP)中取得了成功,它们有效地模拟了复杂的任务依赖性[13][14][15]。这表明,将GNN与DRL相结合可以增强动态工作流调度中的决策能力,从而制定出尊重任务依赖性和执行约束的优化调度。
云工作流调度通常涉及多目标优化(MOO),在性能、能源效率和其他目标之间进行权衡。MOO寻找的不是单一的最优解,而是一组非支配解的帕累托前沿[16]。超体积(HV)和逆生成距离(IGD)等指标用于评估解决方案的质量和多样性[17]。
我们的主要创新贡献是将DRL代理与GNN结合用于工作流调度。这种独特的集成利用了GNN的结构学习能力,在DRL框架内编码复杂的任务依赖性。为了有效处理调度复杂性,我们采用了两阶段决策方法,将问题分解为任务选择和VM分配。这种两阶段公式特别有益,因为它解决了同时进行任务-资源映射时固有的大规模动作空间问题,这通常会阻碍平面DRL模型的收敛。通过解耦决策过程,代理可以学习出更具效率的策略,具有更好的收敛性能,减轻维数灾难,并在动态云环境中实现有效的顺序决策。具体而言,所提出的方法将GNN编码器与基于PPO的两阶段DRL代理结合起来,利用基于偏好的奖励实时导航工期、能源消耗和QoS延迟之间的权衡。
本研究由以下研究问题(RQs)指导:
RQ1:所提出的两阶段DRL框架通过分解任务选择和VM分配,如何减轻维数灾难并提高收敛性能,相比传统的启发式和元启发式基线?
RQ2:基于偏好的多目标奖励公式能否有效地在工期、能源消耗和QoS延迟等冲突目标之间进行权衡,生成多样化的帕累托最优解集?
RQ3:GNN编码器的集成在多大程度上能够有效表示复杂的工作流依赖性,并增强代理在不同DAG结构中的泛化能力?
第II节 文献综述
云工作流调度采用了多种算法范式,从传统的启发式和元启发式方法到最近基于学习的方法。这些研究在如何建模工作流依赖性、处理运行时不确定性以及处理工期、成本、能源消耗和服务质量(QoS)等多目标权衡方面有所不同。在本节中,我们重点介绍与动态多目标工作流调度直接相关的代表性研究,并将我们的两阶段DRL + GNN方法与此进行对比。
A. 经典和启发式工作流调度
早期关于异构系统中工作流调度的研究主要使用确定性启发式方法,这些方法假设对工作流和资源有完整的了解。一个关键的参考是异构最早完成时间(HEFT)算法[18],它使用向上排名指标对DAG任务进行排序,然后将每个任务分配给使其最早完成时间最短的VM。HEFT因其简单性和在异构平台上的强大工期性能而被广泛用作基线,但它忽略了能源消耗和其他优化目标。
一些变体扩展了HEFT风格的列表调度,以在全局工作流截止日期下分配任务,旨在最小化按使用量计费的云资源的货币成本。MOHEFT[20]和FDHEFT[21]将列表调度进一步扩展到多目标设置中,在任务排序和资源选择期间使用加权权衡或模糊支配策略同时优化工期和成本。然而,尽管有这些扩展,基于HEFT的方法仍然受到其静态优先规则的根本限制,在高度动态的环境中或处理复杂的多目标权衡时效果较差。
节能和可持续性方面的启发式方法也被探索。MHRA[22]结合了几种经典调度规则,共同最小化工期和能源消耗。CETSA[23]在动态环境中同时处理成本、能源和工期,而RMREC[24]专注于在动态电压和频率调整(DVFS)下重新映射关键任务,以在预算约束下减少能源使用。通用集群调度器(如Tetris[25]和FERPTS[26])在多资源打包和能源效率方面提供了强大的基线,但它们不是原生的DAG感知的,通常针对作业级别而不是工作流级别进行优化。
总体而言,这些启发式研究为特定目标集提供了高效且通常具有竞争力的调度方案。然而,它们通常每次运行只产生一个解决方案,难以调整以适应许多冲突的目标,并且难以适应动态条件,如工作负载突发、VM故障或运行时不确定性。
B. 元启发式和进化多目标调度器
为了更好地应对工作流调度的组合性质和冲突目标的存在,许多研究采用了元启发式搜索。粒子群优化(PSO)已被广泛应用:Pandey等人[27]最小化了执行和数据传输成本,而Rodriguez和Buyya[28]针对科学工作流在截止日期约束下最小化成本。后来的PSO变体(如IMPSO[29]和HPSO[30]结合了领域特定的操作符(受免疫启发的机制、空闲时隙重用),以在严格的成本和时间限制下提高收敛性。Greedy-Ant[31]使用蚁群优化(ACO)针对基于DAG的工作流,通过蚁群系统迭代强化有前景的任务-VM映射来最小化工期。这些群体智能方法在探索大型搜索空间方面有效,但可能导致高决策延迟,使其不太适合在线调度。
进化算法(EAs)被广泛用于多目标工作流调度。NSGA-II[32]和NSGA-III[33]是最受欢迎的框架,许多研究将它们适配到云工作流中。KMEWSA[34]结合了工作流的结构特征以加快收敛速度。EMWSA[35]和TETS[36]专注于在DVFS基础资源上的能源感知调度,明确地在工期和能源之间进行权衡。FBGA[37]为私有云中的实例密集型工作流引入了基于批处理的进化。除了基于支配的EAs之外,MOEA/D[38]将多目标调度问题分解为一组标量子问题,这些子问题被协同优化。尽管MOEA/D不是针对工作流的,但其分解策略使其成为具有许多冲突标准的多目标工作流的强大候选者。然而,尽管它们具有灵活性,但基于EA的方法通常收敛速度慢,计算开销高,对运行时动态的反应能力有限,因此不太适合大规模云环境中的实时调度。
这些元启发式研究表明,可以获得多样化的帕累托近似解集,其中许多使用超体积和逆生成距离[17]等指标进行评估。然而,它们通常假设离线或批量调度,依赖于手工制作的解决方案表示,并且在动态环境中计算开销较高。
C. 用于云调度的深度强化学习
更近期的工作将云调度视为一个顺序决策问题,并应用深度强化学习(DRL)。在工作流导向的设置中,DQTS[39]使用深度Q学习来调度DAG任务,同时实现工期最小化和负载均衡的双重目标。作者结合了基于熵的奖励融合和经验回放,表明DRL可以在合成工作流上超越启发式基线,尽管他们的帕累托分析仅限于这两个目标,并排除了能源考虑。DRL-Cloud[40]将工作流调度和VM分配 formulized 为一个半马尔可夫决策过程,旨在在硬截止日期和动态电价下减少工期、能源消耗和任务拒绝率。LowCarbon[41]通过DRL解决了碳排放、能源成本和QoS惩罚的联合优化问题,但没有包括工期或基于帕累托的多目标平衡。DeepEnergyJSV2.0[42]使用基于PPO的调度器来最小化混合工作负载的能源消耗,仅关注单一目标。GNN-Flat[43]使用GNN对工作流图进行建模,并使用平面DRL框架来优化工期和能源。然而,其单一级别的代理在高维平面观察空间上操作,随着工作流规模和结构复杂性的增加,会导致可扩展性和泛化问题。
其他DRL研究关注大规模或分层控制。[44]中的分层DRL框架使用全局代理进行VM分配,使用局部LSTM代理进行服务器级电力控制,提高了能源和延迟,但它既不建模工作流结构也不优化工期。MARL[4]提出了一个多代理演员-评论家架构,用于由可再生和不可再生能源供电的地理分布式数据中心,显示出减少棕色能源使用和工期的好处。HITS[45]引入了一个两级DRL调度器,首先选择VM集群,然后使用Double DQN选择VM,根据集群负载调整其奖励函数以平衡成本、逾期时间和负载,但它没有考虑工作流驱动的调度或能源消耗。
尽管不是严格针对工作流的,但一些工作为多资源集群提供了有影响力的DRL调度器。DeepRM[46]及其扩展DeepRM+[47]从类似图像的集群状态学习作业调度策略,以最小化平均减速和周转时间等指标。ADRL[48]结合了异常检测和DRL来处理工作负载激增,同时保持SLA遵守。其他变体考虑了隐私感知的训练(DRL+FL [49])或移动边缘卸载(IDRQN [50])。尽管这些工作共同展示了DRL在云和集群调度中的巨大潜力,但大多数基于DRL的调度器通过标量奖励函数(例如,加权和)来处理目标,而且大部分文献仅优化单一主要目标,如完工时间或能量。因此,使用HV或IGD进行帕累托前沿评估的情况很少;在表1中考虑的DRL方法中,DQTS明确考虑了帕累托前沿,但仍为部署提取单一解决方案。这种以标量化为中心的设计可能会掩盖权衡,并且当操作者偏好改变时难以调整策略 [51]。
表1 代表性云调度研究(Wo = 以工作流为导向,Dyn = 动态,Onl = 在线)
基于Graph Neural Network(GNN)的调度和研究差距
Graph Neural Networks(GNNs)最近已成为处理结构化数据的强大工具,并已成功应用于FJSSP文献中的调度问题。Lei等人在[13]中提出了一个多动作GNN框架,该框架可以直接对作业-机器图进行推理,并且性能优于传统调度器。在后续工作中,Lei等人[56]引入了一种用于动态FJSSP的分层方法,利用GNNs处理随机作业到达。这些研究表明,GNNs比手工制作的特征更有效地编码了复杂的优先级约束和机器灵活性。
然而,在云工作流调度中,GNN的集成仍然有限。据我们所知,GNN-Flat [43]是唯一一篇将GNN与DRL结合用于基于DAG的云工作流的研究。它使用了一个扁平的动作空间,其中代理直接选择任务-VM对,并且在没有任何真实世界云追踪的情况下对合成工作负载进行评估。此外,与多目标基线(如MOHEFT、NSGA-II或MOEA/D)的比较并不全面,该方法也没有明确设计为产生多样化的帕累托最优解。
在更广泛的DRL文献中,很少有调度器利用图编码器来完全利用工作流的DAG结构,而采用多目标、帕累托感知的方式更是少见。大多数方法要么忽略依赖性(例如,独立任务模型),要么将工作流简化为队列,从而丢失了可以指导更明智决策的结构信息。
这些观察结果突出了激励我们工作的三个主要差距。首先,缺乏明确针对云工作流的多目标帕累托前沿的基于DRL的调度器,这些调度器使用HV和IGD等指标。其次,现有的DRL方法很少通过GNN利用DAG结构,这限制了它们在不同工作流之间的泛化能力。第三,之前的基于GNN的方法依赖于扁平的动作空间,这些空间随着任务和VM数量的增加而扩展性较差。相比之下,我们的研究结合了GNN编码器和一个两阶段PPO基础的DRL代理,将任务选择与VM分配解耦。它明确探索了完工时间、能量和QoS延迟之间的权衡,并使用基于帕累托的指标在合成和真实世界云追踪上进行性能评估。
第三部分 方法论
图3展示了2SD-GAT研究中采用的DRL方法论的架构概览。该过程从在各种参数配置下生成合成数据集开始。模拟的云环境为训练提供了基础,DRL代理通过与环境交互执行调度动作并接收奖励、更新状态和环境观察作为反馈。通过迭代学习,代理旨在优化多个目标:最小化完工时间、降低能耗以及与QoS相关的惩罚,后者被建模为高优先级任务的累积延迟。
图1. 数据中心运行的系统模型。图片来自[1]。
随后各部分的结构如下。首先介绍了支撑数据集生成和模拟环境的形式化模型。然后介绍了在奖励公式中起关键作用的下界启发式方法。接着讨论了数据预处理和特征提取过程。然后详细介绍了强化学习框架,接着是为多目标优化设计的基于偏好的奖励函数。最后,详细阐述了代理架构和模型设计,特别强调了GNN(特别是Graph Attention Network(GAT)的集成。
A. 问题建模
在这项研究中,工作流被表示为DAG,这通常用于建模任务之间的依赖性[40]。DAG是一个无环图G=(V,E),其中V是顶点(任务)的集合,E?V×V是表示任务之间依赖性的有向边的集合。对于任何有向边(u,v)∈E,任务u必须在任务v开始之前完成。
完工时间是调度工作流的关键指标,代表完成工作流中所有任务所需的总时间。给定一个表示工作流的DAG G=(V,E),工作流的完工时间M定义如下(1)。
M=maxJi∈VtendJi(1)
\begin{equation*} M = \max \limits _{J_{i} \in V}t^{\text {end}}_{J_{i}} \tag {1}\end{equation*}
这里,tendJi表示任务Ji∈V的完成时间。tendJi的值可以如下推导(2)。
tendJi=tstartJi+TJi,VMk(2)
\begin{equation*} t^{\text {end}}_{J_{i}}= t^{\text {start}}_{J_{i}} + T_{J_{i}, \text {VM}_{k}} \tag {2}\end{equation*}
在这个表达式中,tstartJi表示调度器将任务Ji分配给虚拟机VMk的时间,TJi,VMk表示任务Ji在VMk上的执行时间。为了使调度决策有效,任务必须与选定的VM兼容。这种兼容性是根据用户指定的资源要求来确定的——例如,任务可能需要具有某些内存容量、核心数量或其他硬件特性的VM。这些约束被视为用户资源要求的一部分,调度器必须严格执行以确保服务合规。因此,任务的分配受到满足相应兼容性标准的VM的限制。
在这项研究中,任务与虚拟机之间的兼容性是基于内存和核心数量要求来确定的。只有满足以下条件时,任务Ji才能被分配给VMj:RmemJi≤RmemVMj和RcoreJi≤RcoreVMj,其中RmemJi和RcoreJi分别表示任务的内存和核心要求,RmemVMj和RcoreVMj表示VMj上可用的内存和核心数量。当这些条件得到满足时,可以使用(3)计算执行时间TJi,VMj。
TJi,VMj=LJiSVMj(3)
\begin{equation*} T_{J_{i}, \text {VM}_{j}}= \frac {L_{J_{i}}}{S_{\text {VM}_{j}}} \tag {3}\end{equation*}
这里,LJi是任务Ji的长度,SVMj是VMj的CPU速度。假设VM在任务执行期间以恒定的CPU速度SVMj满负荷运行。
总能耗是云调度中的关键指标,代表数据中心在给定时间段内所有主机使用的累积能量。总能耗表示为Etotal(4)。
Etotal=∫T0Ptotal(t)dt
\begin{equation*} E^{\text {total}}= \int _{0}^{T}P^{\text {total}}(t) {\,}dt \tag {4}\end{equation*}
这里,Ptotal(t)表示时间t的数据中心总功耗。它通过(5)计算为所有NH主机的功耗之和。
Ptotal(t)=∑i=1NHPHi(t)
\begin{equation*} P^{\text {total}}(t) = \sum _{i=1}^{N^{H}}P_{H_{i}}(t) \tag {5}\end{equation*
主机Hi在时间t的功耗PHi(t)由其利用率UHi(t)决定,该利用率在阈值UlowHi和UhighHi之间变化。在这些阈值下的相应功率值分别为PlowHi和PhighHi。假设利用率和功率之间存在线性关系,PHi(t)可以如下表示(6)。
PHi(t)=PlowHi+(PhighHi?PlowHi)?UHi(t)?UlowHiUhighHi?UlowHi
\begin{equation*} P_{H_{i}}(t) = P_{H_{i}}^{\text {low}}+ (P_{H_{i}}^{\text {high}}- P_{H_{i}}^{\text {low}}) \cdot \frac {U_{H_{i}}(t) - U_{H_{i}}^{\text {low}}}{U_{H_{i}}^{\text {high}}- U_{H_{i}}^{\text {low}}} \tag {6}\end{equation*}
为了简化,使用空闲时的功率(PidleHi)和峰值利用率(PpeakHi),上述方程可以简化为(7)。
PHi(t)=PidleHi+(PpeakHi?PidleHi)?UHi(t)
\begin{equation*} P_{H_{i}}(t) = P_{H_{i}}^{\text {idle}}+ (P_{H_{i}}^{\text {peak}}- P_{H_{i}}^{\text {idle}}) \cdot U_{H_{i}}(t) \tag {7}\end{equation*}
主机Hi的利用率UHi(t)受到在其上运行的VM的影响。让VMactiveHi,t表示时间t时主机Hi上的活动VM。利用率UHi(t)由(8)给出。
UHi(t)=∑VMj∈VMactiveHi,tSVMjSHi
\begin{equation*} U_{H_{i}}(t) = \sum _{\text {VM}_{j} \in \text {VM}^{\text {active}}_{H_{i},t}} \frac {S_{\text {VM}_{j}}}{S_{H_{i}}} \tag {8}\end{equation*}
这里,SVMj是VMj的CPU速度,SHi是主机Hi的CPU速度。
本研究还通过基于优先级的模型纳入了任务延迟敏感性。为了简化,考虑了两类任务:低优先级和高优先级。预计调度器在调度决策时会优先考虑高优先级任务。为了定量捕捉这种行为,我们定义了QoS惩罚分数(Q)如下(9)。
Q=∑Ji∈VQJi
\begin{equation*} Q = \sum _{J_{i} \in V} Q_{J_{i}} \tag {9}\end{equation*}
这里,QJi表示任务Ji的QoS惩罚分数,定义在(10)中。
QJi=tstartJi?RpriorityJi
\begin{equation*} Q_{J_{i}} = t^{\text {start}}_{J_{i}} \cdot R^{\text {priority}}_{J_{i}} \tag {10}\end{equation*}
在这个公式中,tstartJi表示任务Ji的开始时间,RpriorityJi∈{0,1}是一个二进制优先级权重,表示任务是高优先级(1)还是低优先级(0)。这种优先级在工作流级别分配,意味着给定工作流中的所有任务继承与其父工作流相同的优先级。
目标是找到一个最优的调度策略,以最小化完工时间(M)、总能耗(Etotal)和QoS惩罚(Q)。这个多目标优化问题如下公式化(11)。
minimize?(M,Etotal,Q)
\begin{equation*} \text {minimize}~\left ({{ M, E^{\text {total}}, Q }}\right) \tag {11}\end{equation*
这个优化受到以下约束:
- 任务必须满足DAG定义的任务优先级约束
- 任务必须满足内存要求,RmemJi≤RmemVMj
- 任务必须满足核心数量要求,RcoreJi≤RcoreVMj
B. 下界启发式方法
在这项研究中,下界启发式方法提供了完工时间、能耗和QoS惩罚分数的基线估计,这些估计随后用于制定奖励函数。这些下界作为乐观估计,确保实际的完工时间、能耗和QoS惩罚分数始终大于或等于这些值。
时间t的完工时间下界估计是通过确定工作流DAG中所有任务的最大估计完成时间来计算的。对于每个任务Ji,完成时间下界取决于其调度状态。如果任务已安排,则使用其实际完成时间。对于未安排的任务,完成时间下界通过评估所有兼容的VM并考虑父任务的可用性和VM的准备情况来计算。
正式地,完工时间下界估计表示为Mestt,定义如下(12)。
Mestt=maxJi∈VMestJi,t
\begin{equation*} M^{\text {est}}_{t}= \max \limits _{J_{i} \in V}M^{\text {est}}_{J_{i}, t} \tag {12}\end{equation*}
这里,MestJi,t表示任务Ji的估计完成时间下界。这是使用(13)递归推导的。
MestJi,t=?????????????????
\begin{align*} M^{\text {est}}_{J_{i}, t}= \begin{cases} \displaystyle t^{\text {end}}_{J_{i}} \\ \displaystyle \hspace {4cm} \text {如果} ~J_{i} ~\text {已安排}, \\ \displaystyle \min \limits _{\text {VM}_{j} \in \text {VM}^{\text {cmp}}_{J_{i}}}\left ({{ \max \limits _{J_{k} \in J^{\text {par}}_{J_{i}}}\left ({{M^{\text {est}}_{J_{k}, t}, M_{\text {VM}_{j}, t}}}\right) + T_{J_{i}, \text {VM}_{j}}}}\right) \\ \displaystyle \hspace {4cm} \text {否则}. \end{cases} \tag {13}\end{align*}
在这个方程中,VMcmpJi表示任务Ji的兼容VM集合,JparJi表示Ji的父任务,MVMj,t是VMj的当前完成时间,如(14)所定义。
MVMj,t=maxJk∈JschVMj,t
\begin{equation*} M_{\text {VM}_{j}, t}= \max \limits _{J_{k} \in J^{sch}_{\text {VM}_{j},t}}M_{J_{k}} \tag {14}\end{equation*}
这里,JschVMj,t指的是时间t之前安排在VMj上的所有任务,MJk是任务Jk的完成时间,如(2)所定义。
时间t的活跃能耗下界估计是使用运行作业所引起的能耗(忽略空闲功耗)来计算的。如果任务已安排,则其活跃能耗基于任务的执行时间和分配的VM。对于未安排的任务,活跃能耗估计为在兼容VM上的最低可能能耗。
正式地,活跃能耗下界估计表示为Eestt,定义在(15)中。
Eestt=∑Ji∈VEestJi,t
\begin{equation*} E^{\text {est}}_{t}= \sum _{J_{i} \in V}E^{\text {est}}_{J_{i}, t} \tag {15}\end{equation*}
这里,V表示所有任务,EestJi,t是任务Ji的估计活跃能耗。这一成本在公式(16)中定义。如果任务Ji被安排在虚拟机VMk上,则E^{\text {est}}_{J_{i}, t}等于E_{J_{i}, \text {VM}_{k};否则,E^{\text {est}}_{J_{i}, t}等于所有在VMj上执行的E_{J_{i}, \text {VM}_{j}中的最小值。在这个表达式中,EJi,VMj表示当任务Ji安排在VMj上时消耗的活跃能量,它是使用公式(17)计算得出的。
在时间t,QoS惩罚分数的下限估计是通过估计每个任务的最早可能开始时间,并根据其优先级进行加权来计算的。对于已安排的任务,开始时间已经是已知的,可以直接使用。对于未安排的任务,通过评估所有兼容的虚拟机并考虑父任务的可用性和虚拟机的准备情况来计算最早的可行开始时间。这种估计提供了在理想调度条件下的累积QoS惩罚分数的下限。正式地,QoS惩罚分数的下限估计表示为Q^{\text {est}}_{t}。
为了确保模型更快地收敛,输入数据被预处理成适合强化学习框架的结构化格式。预处理步骤处理任务级别、虚拟机级别和任务依赖图。输入特征信息见表2。
强化学习(RL)是机器学习中的一个范式,在这种范式中,代理与环境交互,通过试错来学习最优动作。代理以奖励的形式接收反馈,这些反馈指导其学习以随时间最大化累积奖励。状态(s)表示环境的当前条件。状态为代理做出决策提供了必要的信息。动作(a)是代理在给定状态下做出的选择。奖励(r)是环境在每个动作后提供的标量反馈信号,指示动作的即时收益。目标是随时间最大化累积奖励。策略(π)通过将状态映射到选择每个可能动作的概率来定义代理的行为。策略可以是确定性的(π(s)=a)或随机的(π(a|s)=P(At=a|St=s))。值函数(V(s))估计代理从给定状态s开始,遵循策略π可以获得的预期累积奖励。动作值函数(Q(s,a))估计在状态s中采取动作a然后遵循策略π的预期累积奖励。
在复杂的调度环境(如云任务调度)中,可以使用两阶段强化学习将决策过程分解为多个层次。常见的两阶段架构涉及顺序操作的代理:任务代理选择下一个要调度的任务,而虚拟机代理选择最适合执行所选任务的虚拟机。这种解耦的结构简化了动作空间,减少了组合复杂性,并允许在每个层次上进行专门的学习。类似的两阶段方法也应用于FJSSP,其中一个代理选择下一个操作,另一个代理确定执行该操作的机器,有效地处理了在复杂约束下的任务-机器分配。
在研究中,PPO被应用于云工作流调度问题,代理的目标是最小化多个目标。奖励Rt被设计为反映多目标优化框架的重点,对较长的制作时间、较高的能源使用和延迟的任务进行惩罚。为了规范化这些奖励段,采用了一种规范化方法。奖励函数在公式(24)中给出,其中Mestt、Eestt和Qestt分别是状态St在时刻(12)、(15)和(19)下的制作时间下限、活跃能耗下限和QoS惩罚分数下限的估计值。参数α、β和γ平衡了最小化制作时间和能耗的重要性。
需要注意的是,这些下限用于奖励的规范化和调整,而不是作为优化目标本身。因此,学习过程主要依赖于动作之间的相对性能差异,而不是界限的绝对严格性。即使估计值松散或不完美,它们仍然提供了一个一致的乐观参考尺度,可以稳定不同规模和特征的工作流中的奖励幅度。在实践中,这使得DRL策略对中等的估计误差具有鲁棒性,因为次优的界限可能会影响规范化尺度,但不会改变底层的环境转换或真实的目标评估。
C. 数据预处理
为了确保模型更快地收敛,输入数据被预处理成适合强化学习框架的结构化格式。预处理步骤处理任务级别、虚拟机级别和任务依赖图。输入特征信息见表2。
D. 强化学习框架
RL是机器学习中的一个范式,在这种范式中,代理与环境交互,通过试错来学习最优动作。代理以奖励的形式接收反馈,这些反馈指导其学习以随时间最大化累积奖励。状态(s)表示环境的当前条件。状态为代理做出决策提供了必要的信息。让St表示时间t的状态。动作(a)是代理在给定状态下做出的选择。奖励(r)是环境在每个动作后提供的标量反馈信号,表示动作的即时收益。目标是随时间最大化累积奖励。让Rt+1表示在状态St下采取动作At后收到的奖励。策略(π)通过将状态映射到选择每个可能动作的概率来定义代理的行为。策略可以是确定性的(π(s)=a)或随机的(π(a|s)=P(At=a|St=s)。
在DRL文献中,近端策略优化(PPO)是一种流行的算法,旨在提高连续和离散动作空间中策略更新的稳定性和效率。PPO通过使用剪辑的替代目标迭代更新策略来优化策略,这防止了大的策略更新,并确保了稳定学习。PPO中的目标函数在公式(23)中定义。
E. 基于偏好的奖励函数
为了在多目标优化中生成帕累托前沿,获得一组反映不同目标之间权衡的多样化解决方案是至关重要的。在本研究中,这是通过引入基于偏好的奖励函数来实现的。在训练过程中,每个代理都被分配了一组偏好权重,表示其对特定目标的重视程度。这使得相同的架构可以在不同的目标优先级下进行训练,产生一系列解决方案。当这些代理结合起来时,它们有助于构建帕累托前沿,覆盖目标空间的不同区域。奖励函数被定义为估计的制作时间变化、能耗变化和QoS惩罚分数变化的加权组合,如公式(25)所示。每个目标的偏好权重由λ1、λ2和λ3表示,并在训练期间为每个代理固定。数学上,标量奖励Rt+1是三个规范化目标变化的线性组合,由偏好向量加权。这种公式允许代理学习一个优化特定加权目标组合的策略,通过训练具有不同偏好向量的多个代理,可以获得多样化的一组帕累托最优策略。代理架构和模型设计
为了进一步直观地理解代理的决策过程,可以将调度过程视为一个动态的项目管理问题,在这个问题中,工作流有向无环图(DAG)随着任务的调度和完成而演变。在每个决策步骤中,代理观察更新后的任务状态(例如,就绪和已调度指示器)、虚拟机(VM)状态以及当前的依赖结构。这些信息由图注意力网络(GAT)编码,以生成任务嵌入,这些嵌入反映了任务的局部属性和全局结构角色,如下游深度和依赖关系的影响。例如,在一个简单的工作流中,必须先完成预处理任务后,两个后续任务才能开始,因此最初只有预处理任务被标记为就绪状态。一旦预处理任务完成,后续任务就变得就绪,图状态也会随之更新。然后GAT会重新计算当前DAG的嵌入,使策略能够重新评估哪个任务对未来的完工时间、能源消耗和QoS目标有更大的影响。任务执行器根据这些信息选择一个任务,而VM执行器则根据当前的VM条件和目标权衡将其分配到合适的资源上。
与固定的启发式方法不同,学习到的策略不是一种僵化的基于规则的程序。它是为长期累积奖励而优化的,因此可能会选择一些虽然不是立即最优但能随着时间的推移带来更好整体调度性能的行动。
图4展示了2SD-GAT训练架构中的整体数据流。环境暴露出观察结果,包括任务特征、VM特征和工作流依赖图,这些信息同时被发送给任务执行器、VM执行器和评论家。任务执行器首先选择下一个要调度的任务,然后将其传递给VM执行器以确定最合适的虚拟机。组合后的行动(包括选定的任务和虚拟机)被应用于环境,环境反过来返回下一个观察结果和一个标量奖励信号。评论家接收环境的观察结果和相应的奖励,并计算用于生成优势信号的价值估计。这些优势估计以及来自两个执行器的策略输出都被传递给PPO优化器。PPO随后更新评论家和两个执行器的参数[58]。
图3. 用于2SD-GAT算法的强化学习(RL)方法论。
图4. 用于2SD-GAT的RL框架。
图5. 任务执行器网络架构。
1) 第一阶段:任务执行器网络
任务执行器负责在每个时间步骤中从工作流DAG中选择下一个要调度的任务Ji。其输入包括任务特征矩阵Xtask∈RNt×Ft、VM特征张量Xvm∈RNt×Nv×Fv以及任务依赖图A∈{0,1}Nt×Nt,其中Nt是任务的数量,Nv是VM的数量,Ft和Fv分别是任务和VM特征的维度。
任务执行器的核心子组件是图神经网络(GNN),它使用多层图注意力网络(GAT)实现。这个GNN处理工作流DAG以生成任务嵌入,捕捉任务的局部属性和全局结构依赖关系。相同的基于GAT的任务编码器随后被VM执行器通过汇总的任务上下文ptask重新使用。
每个任务Ji表示为一个节点,其输入特征向量xi∈RFt,由表2中列出的任务级别的特征F1i,t至F6i,t组成。这些特征编码了任务的调度状态及其对优化目标的估计影响,为GNN提供了丰富的描述性基础以便进行表征学习。
任务依赖关系在工作流DAG中以有向边的形式表示。边(Ji,Jj)表示Ji必须在Jj开始之前完成。这些依赖关系存储在邻接矩阵A中,其中Ai,j=1表示从Ji到Jj的有向边。由于将任务分配给VM会在该VM上引入新的优先级约束,因此矩阵会在每个DRL时间步骤t更新,以包含原始的工作流边和这些动态引入的依赖关系。
尽管这些边除了二进制连通性之外不携带额外的特征,但GAT架构利用其注意力机制隐式地推断出每个依赖关系的重要性。这在工作流调度中特别有益,因为某些依赖关系(如处于或靠近关键路径的依赖关系)对完工时间和整体性能有不成比例的重要影响。与使用统一聚合重量的传统GNN不同,GAT动态计算注意力系数,决定了每个邻居对节点更新表征的贡献程度。这使得模型能够强调结构上重要的关系,并突出显示调度顺序更为关键的任务。
选择GAT的另一个理由是其强大的泛化能力。因为注意力权重是从节点特征和学习到的嵌入中计算得出的,所以编码器能够自然适应不同深度、宽度和结构复杂性的工作流DAG。动态注意力计算在学习过程中也会不断发展,使GNN能够随着表征变得越来越丰富而改进其整合前后置任务信息的方式。这种基于GAT的编码器的有效性通过第四节C中提出的消融研究得到了验证。
此外,编码器对不断演变的工作流DAG的理解通过关键的状态指示输入得到加强,特别是任务就绪(F1i,t)和任务已调度(F2i,t)状态特征,以及每次调度决策后更新的依赖边(Ai,j,t)。这些信号使GAT能够不断重新评估哪些节点和优先关系在任务通过不同调度阶段时最具影响力。在每个DRL时间步骤中,GAT作用于当前的邻接矩阵Ai,j,t,从而在更新后的图上重新计算任务嵌入,确保每个决策都基于最新的工作流拓扑。因此,网络保持了工作流的最新结构视图,帮助代理即使在引入新约束修改图拓扑时也能保持稳定的收敛性。
设xi∈RFt为任务Ji的输入特征向量。在一个有L层的GAT中,第l层的输出嵌入是通过使用(28)[59]中定义的学到的注意力权重聚合来自邻居N(i)的信息计算得出的。
h(l)i=σ∑j∈N(i)α(l)ijW(l)h(l?1)j??,h(0)j=xj (28)
注意力系数α(l)ij是使用共享注意力机制计算的,该机制对相邻节点嵌入的连贯线性投影应用LeakyReLU激活函数[59]。
经过L层后,每个任务Ji的最终任务嵌入表示为htaski=h(L)i∈RE。这些嵌入通过均值池化聚合来生成全局任务级上下文向量(任务池)ptask∈RE(使用(29))。均值池化层通过对所有任务的元素进行平均来聚合任务嵌入。给定N个任务嵌入,通过对任务维度进行平均获得全局上下文表示。我们采用均值池化是因为它的简单性和稳定的聚合行为。
ptask=1/Nt∑i=1Nthtaski (29)
为了纳入关于VM可用性的信息,计算每个VM的平均VM特征。设Xvmi,j∈RFv表示虚拟机j相对于任务i的特征向量。平均VM特征表示xvm, avgj∈RFv按(30)计算。
xvm, avgj=1/Nt∑i=1NtXvmi,j,?j∈[1,Nv] (30)
这些特征通过VM编码器网络传递,该网络是一个多层感知器(MLP),以生成VM嵌入hvm, avgj∈RE。每个MLP层由仿射变换和非线性激活组成。第l层的仿射变换使用(31)计算,激活输出使用(32)计算。
z(l)h(l)=W(l)x+b(l)=ReLU(z(l) (31)
(z(l)) = W^{(l)} x + b^{(l)} (31)
(h(l)) =ReLU(z^{(l)}) (32)
通过MLP后,结果VM嵌入使用均值池化聚合形成VM级上下文向量(VM池)pvm, avg∈RE(见(33)。
pvm, avg=1/Nv∑j=1Nvhvm, avgj (33)
对于每个任务Ji,任务嵌入htaski与全局上下文向量ptask和pvm, avg连接起来形成组合表征etaski(见(34)。
etaski=[htaski∥ptask∥pvm, avg] (34)
这个向量通过解码器MLP传递,该MLP为每个任务输出一个标量分数staski。然后使用二进制掩码对这些分数进行掩码处理,以识别可调度任务[13]。掩码后的分数s~taski在(35)中定义。
s~taski={staski?∞如果Ji已经准备好被调度,否则为-∞ (35)
最后,使用softmax函数从掩码后的分数中获得任务策略πtaski(见(36)。
πtaski=exp(s~taski)∑Ntj=1exp(s~taskj) (36)
在训练期间从这个分布中抽取选定的任务Ji,或者在评估期间选择概率最大的任务。
2) 第二阶段:VM执行器网络
VM执行器负责选择适当的VM VMj来执行任务执行器选定的任务Ji。它使用相同的VM编码器架构(在III-F1中描述的MLP),但输入特征的选择不同:由于任务已经选定,VM执行器只考虑与选定任务Ji相关的VM特征片Xvmi∈RNv×Fv。
这些特征通过VM编码器网络传递,为每个VM j生成VM嵌入hvm,ij∈RE(在所选任务i的上下文中)。然后通过均值池化计算汇总的VM级上下文向量pvm,i(见(37)。
pvm,i=1/Nv∑j=1Nvhvm,ij (37)
为了将全局上下文纳入决策过程,每个VM嵌入hvm,ij与任务级汇总向量ptask(由基于GAT的任务编码器计算)和VM级汇总向量pvm,i连接起来,形成每个VM的组合表征evmj(见(38)。
evmj=[hvm,ij∥ptask∥pvm,i] (38)
这些组合向量通过解码器MLP传递,为每个VM生成一个标量分数svmj,该分数代表选择该VM执行任务Ji的可能性。为了强制任务-VM兼容性约束,这些分数使用二进制掩码进行掩码处理。掩码后的分数在(39)中定义。
s~vmj={svmj,?∞如果VM可调度且与Ji兼容,否则为-∞ (39)
最终VM选择策略πvmj是通过类似于(36)的方式对掩码后的分数应用softmax函数计算得出的。在训练期间,从这个概率分布中抽取VM;在评估期间,选择概率最大的VM。
3) 评论家网络
评论家网络估计状态价值函数V(s),该函数表示从状态s开始并遵循当前策略的预期累积回报。这个价值估计用于PPO中计算优势函数并指导策略更新。
评论家接收与执行器相同的观察结果,包括任务特征、VM特征和任务依赖图。任务特征使用与任务执行器中相同的基于GAT的编码器进行编码,以生成汇总的任务表征ptask。同样,虚拟机(VM)的特征是在所有任务中取平均值,并使用共享的多层感知机(MLP)编码器进行编码,以获得合并的VM表示pvm, avg。这两个上下文向量被连接起来,形成批评者输入嵌入,如公式(40)所定义。ecritic=[ptask∥pvm, avg](40) \begin{equation*} e^{\text {critic}} = \left [{{ \mathbf {p}^{\text {task}} {\,}\| {\,}\mathbf {p}^{\text {vm, avg}} }}\right ] \tag {40}\end{equation*} 这个组合嵌入通过MLP处理,输出一个标量值预测V(s),代表从当前状态预期的回报。需要注意的是,批评者网络不与演员网络共享参数。虽然任务演员网络和VM演员网络在内部共享它们的编码器和解码器参数,但批评者使用的编码器是独立参数化的。这种设计允许批评者学习一个稳定且专用的价值估计表示,而不受策略网络优化动态的影响。
**G. 合成数据集生成**
在每次训练或评估迭代中,都会根据一组可配置的参数生成一个新的合成工作流数据集,这些参数控制DAG结构、任务工作负载和主机特性。这确保了代理能够接触到多样化的工作流模式和资源条件,防止了对固定工作流集的过拟合。以下描述了构建这些合成数据集的方法。
每个工作流都被建模为一个DAG,使用Erd?s-Rényi G(n,p)方法[60]生成,其中n表示节点(任务)的数量,p表示任意两个节点之间存在边的概率。为了确保高连通性并避免孤立顶点,p被定义为log(n+?)/n,其中?是一个小的正常数[61]。每个DAG中的任务数量n是从[1,Nmaxtask]范围内均匀抽样的。每个DAG都添加一个起始节点以保证完全连通性。每个数据集的生成方式是使所有工作流中的任务总数等于Ntask。
每个任务的计算工作负载(长度)是从以Lmintask+Lmaxtask/2为中心的正态分布中抽样的,标准差为Lmaxtask-Lmintask/6。抽样值被剪裁到[Lmintask,Lmaxtask]范围内。每个工作流中的VM数量是从[1,Nmaxvm]中随机选择的。物理主机的数量是从[1,Nmaxhost]中随机选择的,每个VM被随机分配到一个主机上。VM内存和CPU核心的分配是从[0,1]范围内均匀抽样的。任务资源需求也从这个范围内抽取,要求每个任务至少与一个VM兼容。VM CPU速度是从[Sminvm,Smaxvm]范围内抽样的。主机级别的特性,包括空闲和活跃功耗,是从SPECpower基准测试套件[62]中获得的。主机硬件特性的完整配置总结在表3中。
**H. 真实世界数据集生成**
与合成数据集生成类似,真实世界数据集也是使用一组可配置的参数生成的。然而,这些参数不是从预定义的分布中抽样得到的,而是直接从真实世界统计数据中得出的,以确保生成的特性反映了实际的分布。
对于任务和VM特性的生成,使用了Google集群使用跟踪v3[63]数据集。该数据集提供了2019年5月八个不同Borg单元的运营数据。鉴于数据集的规模很大,分析仅限于美国/纽约时区的数据,特别是2019年5月1日之后和5月7日之前的任务。为了确保管理的可行性,随机抽取了100,000条记录来确定任务和VM的统计数据。此外,只考虑了运行时间小于300秒的任务,因为300秒代表了最大测量长度。利用这些提取的统计数据,通过应用适当的缩放因子得出了任务长度、资源需求和VM的配置。这种调整是必要的,因为Google跟踪中的许多值出于隐私原因被混淆了。用于生成真实世界数据集的最终配置参数总结在表4中。
**尽管真实世界数据集参数是从Google集群使用跟踪统计数据中得出的,但数据集本身是从聚合摘要中生成的,而不是直接从跟踪回放中生成的。因此,原始跟踪中存在的细粒度时间行为,如突发性、高峰与非高峰工作负载动态以及复杂的依赖结构可能无法完全保留。这种设计选择是为了能够生成大量随机化但统计上基于数据的训练和评估数据集,以确保可控性和可重复性。包括了一个敏感性分析(IV-D),以验证学习到的策略在训练过程中对偏好权重的变化是否一致响应,提供了跨配置的额外鲁棒性证据。探索全保真跟踪回放和更丰富的依赖模型仍然是未来工作的方向。**使用线性-分支-合并-下沉DAG结构来模拟任务依赖关系。图8中展示了此类DAG的代表性示例。选择这种结构进行模拟是因为它反映了生产云工作流中常见的基础模式,包括提取-转换-加载(ETL)过程、机器学习管道和数据编排系统。它有效地捕捉了顺序依赖关系和并行执行路径——这两个是真实世界工作流的两个基本特征。此外,这种结构涵盖了[64]中定义的工作流模式1(顺序)、2(并行分割)和3(同步)。**
**III-G. 主机特性**
主机特性是从SPECpower基准测试套件[62]中得出的,如第III-G节所述。为了模拟真实的云环境,本研究模拟了两个关键动态行为方面:随机VM故障和不准确的任务长度估计。因此,使用了带有额外动态属性的真实世界数据集配置变体来模拟真实的操作不确定性。
VM故障可能在运行过程中由于各种原因发生,例如系统崩溃、硬件故障或计划维护[65]。为此,引入了参数来控制VM故障的频率和时机。为了简单起见,只模拟了单VM故障,确保在任何给定时刻,没有超过一个VM被标记为不可用。为了避免死锁或无法调度的情况,对于任何任务来说,唯一的兼容选项VM被排除在故障事件之外。
在实际场景中,任务执行时间通常在调度之前进行估计,但由于数据变化、算法复杂性或系统级波动,这些估计可能与实际运行时间不同[6]。为了反映这一点,引入了估计任务长度和实际任务长度之间的随机偏差,从而捕捉到运行时预测中常见的不确定性。
**I. 调整奖励函数参数**
在训练之前调整了奖励函数权重α、β和γ,以确保没有奖励组件被过分强调。这种调整是通过使用随机调度算法来驱动调度器,并收集多个样本的奖励组件来执行的。根据这些观察结果,计算出平均值并用作归一化因子,使得在随机调度条件下每个奖励项的贡献大致相等。
**J. 仿真环境**
训练和测试的仿真都是使用使用NumPy和PyTorch实现的自定义Python仿真环境进行的。该环境模拟工作流DAG执行、资源约束、任务调度和能源消耗,并支持动态场景,如VM故障和任务长度不确定性。训练和所有评估都是在配备有Intel Core i7-14650HX CPU、16GB RAM和NVIDIA RTX 4060 Laptop GPU(具有8GB VRAM)的笔记本电脑上进行的,运行的是支持CUDA 13.0的PyTorch 2.6。
**K. 代理训练**
1) 在合成数据集上的代理训练
强化学习代理使用基于CleanRL框架[66]实现的PPO算法进行训练。权重使用PyTorch/PyTorch Geometric提供的默认初始化方案进行初始化(根据层类型使用Kaiming或Xavier)。训练是在固定数量的剧集中进行的,每个剧集代表一个完整的调度场景。在每个剧集结束时,使用PPO算法更新代理的策略,以保持探索和利用之间的平衡。用于训练的超参数总结在表6和表7中。为了清晰和可重复性,表6还报告了随机种子、并行环境数量和总训练时间步数。
**图9显示了具有相等偏好权重(λ1=λ2=λ3=1)的代理训练曲线,随着训练的进行,剧集回报增加。训练结果表明,PPO算法结合基于GAT的架构有效地学会了在处理动态任务到达和依赖关系时最小化制作时间和能源消耗。**
2) 在真实世界数据集上的代理训练**
为了展示微调和使用真实世界场景训练代理的好处,使用了第III-H节中描述的真实世界数据集进行了额外的训练。任务数量(Ntask)、每个工作流的最大任务数量(Nmaxtask)、VM的最大数量(Nmaxvm)和主机的最大数量(Nmaxhost)保持表5中指定的值。所有训练参数也保持表6中指定的值,除了奖励缩放因子α、β和γ。这些参数使用第III-I节中概述的方法重新调整,它们的更新值在表8中提供。
**图9显示了具有相等权重的代理在训练期间的剧集回报。**
**L. 代理评估**
为了评估RL代理,使用表9中给出的属性生成了一个合成数据集。在评估期间,变化了工作流和任务的最大数量,以评估模型在多种场景下的性能。
**此外,还使用了一个真实世界数据集进行了评估,记为DSreal。这个数据集是根据第III-H节描述的方法得出的。用于生成这个数据集的参数总结在表10中。**
**表10总结了用于生成真实世界数据集的参数。**
还使用了一个扩展的版本的数据集,记为DSdyn,用于模拟动态执行条件,包括随机VM故障和不准确的任务长度估计。用于引入这些动态行为的特定参数列在表11中。**
**M. 对比算法**
2SD-GAT算法与一组多样化的基线算法进行了对比,以全面评估其在多个目标和调度场景中的性能。表12总结了比较算法,这些算法涵盖了静态和动态调度策略,以及单目标和多目标优化方法。**表12总结了比较算法**
在单目标静态算法中,HEFT和FERPTS代表了由于在最小化制作时间方面的效率而被广泛采用的良好建立的启发式方法。Min-Min和Max-Min启发式方法分别通过优先处理执行时间最短和最长的任务来提供对比策略。这些方法作为评估基本调度行为的有用基准。
对于动态单目标调度,包括了Round-Robin、Least-Loaded-First、Random和Weighted Dynamic Scheduling等算法。这些算法以在线方式运行,反映了实时云环境中使用的实际策略,特别是在不确定性和变化的工作负载下。**
**为了与其他最先进的多目标优化技术进行基准测试,评估包括了MOHEFT、NSGA-II、NSGA-III和MOEA/D。这些进化算法旨在近似帕累托前沿,涵盖冲突的目标,如制作时间、能源消耗和QoS惩罚。它们为评估2SD-GAT在产生多样化和高质量权衡方面的有效性提供了强有力的比较基础。**
**此外,还包括了GNN-Flat[43]作为基于学习的基线,以便与2SD-GAT进行更接近的架构比较。GNN-Flat使用相同的数据集和训练预算进行了重新训练,以确保公平的比较。然而,由于其更简单的架构和平坦的动作空间,在给定的训练预算(200,000时间步)内,它没有完全收敛。**尽管包括了GNN-Flat,但仍能够洞察架构和动作空间设计选择如何影响多目标学习性能。所有算法都在相同的数据集(DSsyn1、DSsyn2、DSsyn3、DSreal、DSdyn)和相同的实验条件下进行了测试。DRL方法(GNN-Flat和2SD-GAT)使用相同的数据集和模拟环境进行训练(见第III-K1节和第III-K2节)。为了保持公平性,在适用的情况下,基线算法也被提供了相同的输入特征和系统级信息。
**评估指标**
2SD-GAT算法的结果与第III-M节中描述的基线方法进行了比较。由于问题的多目标性质,简单的标量比较(如完成时间、能耗或QoS惩罚)是不充分的。相反,采用了MOO中的标准指标来评估每种算法的性能。其中一个主要指标是超体积(Hypervolume),它衡量了由获得的Pareto前沿所主导的目标空间的体积,并由一个预定义的参考点界定[16]。较高的超体积值表示各个目标之间的权衡覆盖更好。参考点的选择是为了确保所有评估方法中的解都能被它所支配,从而保证公平比较。超体积的正式定义见公式(41):
$$
HV(S, r) = \text{volume} \left( \bigcup_{x \in S} [f_1(x), r_1] \times \cdots \times [f_m(x), r_m] \right)
$$
这里,$S$ 是获得的Pareto前沿,$r$ 是参考点,$f_i(x)$ 表示解 $x$ 的第 $i$ 个目标值。
另一个广泛采用的指标是反向生成距离(Inverted Generational Distance, IGD),它评估Pareto前沿的收敛性和多样性[16]。IGD计算每个点在已知参考Pareto前沿中的平均距离到评估解集中的最近点的距离。较低的IGD表明解集更接近真实的Pareto前沿。IGD的定义见公式(42):
$$
IGD(P^*, S) = \frac{1}{|P^*|} \sum_{x^* \in P^*} \min_{x \in S} \| x - x^* \|
$$
这里,$P^*$ 是由所有算法的非支配解聚合而成的参考Pareto前沿,$S$ 是正在评估的解集。
除了这些基于Pareto的指标外,还考虑了决策延迟(Decision Latency),即做出单一调度决策所需的时间。由于本研究关注动态调度场景,因此调度决策需要实时或接近实时地计算。因此,较低的决策延迟反映了该方法在现实世界云系统中的更好实用性。
最后,为了分析算法之间的支配关系,比较了每种方法产生的Pareto前沿。在三目标设置下,展示了所有三个目标对的Pareto前沿的2D投影,以说明不同维度上的权衡和支配关系。
**第四节:结果与分析**
**A. 合成数据集的结果**
本节全面评估了2SD-GAT在合成工作负载条件下的表现,与一系列基线方法进行了对比。表13报告了三个复杂性逐渐增加的合成数据集的结果。相应的可视化结果见图11和图12,其中展示了Pareto前沿和多目标指标的比较。
**表13 合成数据集的2SD-GAT与基准方法的性能比较(最佳值以粗体显示,第二佳值以下划线显示)**
**图10. 其他代理在训练期间的 episodic return(回报)**
**图11. 合成数据集的调度器的Pareto前沿**
**1) 小规模工作负载**
如图11所示,2SD-GAT的Pareto前沿与几个基线有显著重叠。由于任务数量相对较少(50个),调度复杂性较低,大多数算法的表现都相当不错。尽管如此,2SD-GAT仍能够匹配或超过经典启发式算法和多目标进化算法的性能。从条形图和表13可以看出,2SD-GAT实现了最高的超体积值((4.958±0.040)×10^10),表明其Pareto前沿涵盖了更大且更优的目标空间部分。GAT-Flat的结果变化较大,可能是因为它最初是为优化能耗和完成时间而设计的;将其扩展到包括QoS可能会降低其在相同迭代预算下的训练效果。虽然NSGA-III的IGD略好(164.818),但其决策延迟明显更高(1.060秒),相比之下2SD-GAT为0.070秒。这种权衡突显了2SD-GAT的实时效率:它在计算成本的一小部分下实现了接近最优的Pareto性能。
**2) 中等规模工作负载**
在图11中,2SD-GAT的Pareto前沿明显优于所有基线。此外,2SD-GAT产生的Pareto前沿始终位于同一区域内,突显了该方法的随机稳定性。对于完成时间/能耗的投影,该前沿覆盖了广泛的权衡范围,表明该方法可以灵活适应不同的优化偏好。在另外两个投影上,2SD-GAT的解决方案占据了其他调度器产生的解决方案的大部分。表13显示,2SD-GAT实现了最高的超体积((6.605±0.105)×10^12)和最低的IGD(4457.338±704.960),优于所有其他方法。这些结果表明,2SD-GAT的Pareto前沿不仅分布广泛,而且靠近参考Pareto前沿。决策延迟异常低(0.083秒),显著优于基于进化的调度器,如NSGA-II(22.512秒)、NSGA-III(21.954秒)和MOEA/D(20.210秒)。这说明2SD-GAT能够有效扩展到更大的工作负载,同时在动态环境中保持其实用性。
**3) 大规模工作负载**
对于最大的合成数据集(1000个任务),2SD-GAT产生的Pareto前沿继续优于基线,证明了它在所有目标配对中的广泛覆盖和强大支配能力。这证实了2SD-GAT的可扩展性,并且能够很好地泛化到其训练条件之外的情况。
根据表13,2SD-GAT在所有方法中实现了最高的超体积((7.506±0.033)×10^15)和最低的IGD(28790±3029),反映了其生成高质量、多样化且分布均匀的Pareto最优解的能力。尽管由于任务数量众多引入了计算复杂性,决策延迟仍仅为0.244秒,这比基于MOEA的方法(延迟超过1000秒)有显著优势。在这个规模上,GNN-Flat的表现差异很大,可能是因为在给定的训练预算内未能完全收敛。这种对比进一步强调了2SD-GAT的可扩展性,并证实了它在生成最优权衡方面的有效性,同时也适用于大规模、动态调度场景的实时使用。
**B. 真实和动态数据集的结果**
本节评估了2SD-GAT在真实世界工作负载条件下的表现,包括有无动态干扰的情况。表14报告了这两个数据集的定量结果。相应的可视化结果见图13和图14,展示了Pareto前沿和多目标指标的比较。评估了两种版本的2SD-GAT代理:一种在合成数据上训练的代理,称为2SD-GAT(Syn);另一种在没有动态场景的真实世界数据上训练的代理,称为2SD-GAT(Real)。
**表14 真实世界数据集的2SD-GAT与基准方法的性能比较(最佳值以粗体显示,第二佳值以下划线显示)**
**图12. 合成数据集的调度器的超体积/IGD/决策延迟(超体积越高越好,IGD/决策延迟越低)**
**图13. 真实和动态数据集的调度器的Pareto前沿**
**1) 真实世界数据集**
在图13中,2SD-GAT(Real)模型生成的Pareto前沿在所有基线方法中占据了大多数解决方案,表现出强烈的扩散性和高质量的权衡。仅在合成数据上训练的2SD-GAT(Syn)模型也表现具有竞争力,并且优于几种经典和启发式方法。然而,其性能略低于2SD-GAT(Real)模型。这个结果是预期的,可能是由于数据分布的差异。合成训练数据在结构和工作流模式上有所不同,因为它依赖于Erd?s-Rényi G(n,p)图,而真实数据集由分支-并行-合并的有向无环图(DAG)组成,后者更好地反映了实际的云工作负载。这种差异自然会导致IGD在领域转换时的下降,而不是表明严格的数据集特异性。这些结果验证了在特定问题上微调RL代理的好处。尽管2SD-GAT(Real)模型是在小规模的真实数据集(50个任务)上训练的,但它能够有效泛化到本次评估中的250个任务工作负载,表明该架构能够很好地适应目标领域。
根据表14和图14,2SD-GAT(Real)方法实现了最佳的超体积((1.678±0.014)×10^10)和IGD(2108.377±347.929),表明其Pareto前沿质量优越。2SD-GAT(Syn)模型紧随其后,超体积为(1.509±0.032)×10^10),IGD为第二佳(1057.388±115.391)。重要的是,尽管在不同的数据集上训练,合成训练的模型仍然是总体上的第二佳,表明了合理的跨领域泛化能力。两种模型的决策延迟都保持在0.1秒以下,显著优于基于进化的基线算法,如NSGA-II(21.223秒)和MOEA/D(20.093秒),进一步证实了2SD-GAT方法在实时调度中的实用性。
**2) 动态真实世界数据集**
真实数据集的动态变体通过模拟的虚拟机(VM)故障和不准确的任务长度估计引入了运行时不确定性。如图13所示,2SD-GAT(Real)模型继续保持强大性能,其Pareto前沿在所有基线中占据主导地位,并在所有投影中表现出广泛的覆盖范围。2SD-GAT(Syn)模型 também 表现良好,尽管没有明确针对动态场景进行训练,但其鲁棒性得到了验证。相比之下,静态调度算法在面对环境变化时难以适应,需要频繁重新计算和重新调度。这反映在它们的性能指标上:MOHEFT、NSGA-II和MOEA/D的决策延迟较长,范围从1秒到超过190秒不等。它们的IGD分数也下降,表明在动态条件下的解决方案质量较差。
如表14所述,2SD-GAT(Real)模型实现了最佳的超体积((7.425±0.207)×10^8)和IGD(237.332±48.518),显示出强烈的适应性和对环境变化的鲁棒性。2SD-GAT(Syn)模型实现了第二佳的超体积((5.933±0.170)×10^8)和相当的IGD(237.332±48.518),表明即使在具有不同统计分布和工作流结构的数据集上训练,也能有效泛化。尽管经过微调,2SD-GAT(Real)的性能提升仍然明显优于2SD-GAT(Syn),但两者之间的性能差距不大。NSGA-II实现了第三佳的超体积(5.855×10^8),表明它在目标空间生成了分布良好的解决方案。然而,其较高的IGD(1066.093)表明这些解决方案与真实的Pareto前沿相差较远,反映了较弱的收敛性,以及较差的多样性。此外,其极端的决策延迟(超过3分钟)限制了其在实时或动态调度场景中的实用性。相比之下,2SD-GAT(Syn)和2SD-GAT(Real)在整体解决方案质量和决策延迟方面都优于所有其他基线,使其更适合实际部署。
**C. 消融研究**
为了评估GAT基础编码器在提出的2SD-GAT框架中的贡献,通过用两种替代架构替换Task Actor中的GAT组件进行了消融研究:图同构网络(GIN)[68]和多层感知器(MLP)。这些变体分别称为2SD-GIN和2SD-MLP,保留了两阶段调度架构的所有其他组件。这确保了任何性能差异仅来自于用于处理工作流依赖关系的图编码器的选择。
GIN基线代表了一种强大的基于消息传递的GNN,具有注入式聚合功能,能够区分结构不同的邻域。然而,与GAT不同,它在聚合过程中对所有邻居应用相同的权重,因此无法调节不同依赖关系的相对重要性。MLP基线完全移除了显式的图建模,仅基于每个任务的特征向量操作,并依赖于DRL代理来学习隐式的结构线索,而不需要专门的消息传递机制。这两种替代方案构成了比较关注基于注意力的聚合的好方法。
这三种架构(2SD-GAT、2SD-GIN和2SD-MLP)都使用第III-H节中描述的DSreal真实世界数据集配置进行了评估,确保每个模型在评估过程中遇到相同的工作流结构、任务特性和VM配置。这项消融研究的详细结果见表15,图15提供了视觉比较。
**表15 2SD-GAT、2SD-GIN和2SD-MLP调度器的性能比较(最佳值以粗体显示,第二佳值以下划线显示)**
**图14. 真实和动态数据集的调度器的超体积/IGD/决策延迟(超体积越高越好,IGD/决策延迟越低)**
定量结果揭示了几项关键见解。首先,尽管2SD-MLP在某些单一目标指标(如最佳QoS惩罚)上表现出竞争力,但其多目标(MO)性能始终落后于2SD-GAT。具体来说,2SD-GAT获得了最大的超体积((4.125±0.031)×10^10)和最低的IGD(306.060±51.785),显示出更好的Pareto前沿覆盖率和收敛性。相比之下,尽管2SD-MLP是第二好的性能,但其IGD明显较低(954.055±157.106),超体积也较低((4.092±0.036)×10^10)。2SD-GIN变体在所有MO指标上的表现都明显不如2SD-GAT和2SD-MLP,具有最低的超体积((4.005±0.055)×10^10)、最高的IGD(1184±473.192)和最差的QoS惩罚(7675)。这种性能下降与GIN的架构限制有关:虽然它保留了表达性强的邻域聚合能力,但其均匀加权方式使得它无法区分关键和不太关键的依赖关系,而这在具有异构结构瓶颈的工作流程有向无环图(DAGs)中尤为重要。所有方法的平均决策延迟几乎相同(0.083、0.087和0.085),表明基于注意力的聚合并没有引入可测量的运行时开销。实际上,这表明2SD-GAT在保持竞争优势的同时,提供了显著更高的解决方案质量。总体而言,这些消融研究结果加强了GAT作为两阶段DRL架构中编码器的适用性。
D. 敏感性分析
在基于偏好的多目标强化学习中,验证学习到的策略是否能一致地响应训练期间使用的偏好权重的变化非常重要。由于所提出的框架中的每个代理都是使用固定的偏好向量(λ1,λ2,λ3)进行训练的,预期行为是增加分配给特定目标的权重应该使学习到的策略朝向反映该目标偏好的性能结果。为了评估这一点的实际效果,对训练后的代理进行了事后敏感性分析。该分析考虑了偏好权重与结果性能指标(制作周期、能源消耗和QoS惩罚)之间的映射。共有26个在不同偏好组合下训练的代理在同一测试工作流程上进行了评估,产生了形式为(λ1,λ2,λ3)?(M,E,Q)的配对数据。为了量化每个目标对其相应偏好权重的响应强度,我们为每个性能指标分别拟合了一个线性回归模型,使用偏好权重作为自变量。这产生了一阶近似公式,如(43)所示:
y=β0+βMλ1+βEλ2+βQλ3,(43)
回归系数在表16中给出,图16提供了线性趋势的视觉解释。
表16 偏好权重(λ1,λ2,λ3)与性能指标之间的线性敏感性模型
图15. 消融研究的Pareto前沿/超体积/IGD/决策延迟(超体积越高越好,IGD/决策延迟越低)。
从定量上看,制作周期模型显示λ1具有负面影响(βM=?6.89),证实了更强的制作周期偏好一致地推动策略更快地完成调度。相比之下,λ2的正系数(βE=17.31)表明关注能源的代理倾向于产生更长的调度计划,这是采用更为保守或节能的分配策略的自然结果。能源消耗表现出最强且最易解释的敏感性模式。与λ2相关的大型负系数(βE=?40.60)表明优先考虑能源的代理显著减少了资源使用。同时,λ1和λ3的较小正系数(分别为1.97和1.44)表明关注制作周期或QoS的代理倾向于使用稍微多一些的资源。高决定系数(R2=0.75)表明偏好权重解释了能源使用的大部分变化。QoS惩罚对λ2和λ3都有强烈响应。λ3的大型负系数(βQ=?263.61)表明增加QoS偏好显著降低了QoS惩罚,而λ2的正系数(βE=461.78)表明节能调度显著增加了QoS惩罚。这种权衡与在资源节约限制下运行的代理的预期行为一致。决策延迟对偏好权重的敏感性可以忽略不计,这反映在极小的系数(都在10^-3或更小)和低R2值(0.0656)上。这表明偏好选择不会显著影响代理计算调度决策所需的时间,表明延迟主要由架构因素而非行为因素决定。
总体而言,敏感性分析表明2SD-GAT框架对偏好向量的变化反应稳定且可解释。
E. 计算成本和训练时间
所有实验都是在第III-J节描述的硬件上进行的。每个代理训练了200,000个环境步骤。在所有经过训练的偏好条件代理中,DSreal的平均训练时间为16.07±1.18分钟。由于Pareto前沿是用具有不同偏好向量的26个代理构建的,因此总顺序训练预算约为7小时。这个成本与偏好向量的数量成线性关系,但通过并行训练可以大幅降低,因为代理是完全独立的。重要的是,这种训练成本仅在线下发生一次。在推理时,学习到的策略产生的调度决策的平均延迟约为每个决策0.067秒,与典型的工作流程执行时间相比可以忽略不计。因此,所提出的方法在实现广泛Pareto前沿覆盖的同时,保持了实际的可部署性。
第五节 讨论
A. 研究问题分析
本研究解决了关于2SD-GAT框架设计和有效性的三个关键研究问题。研究发现总结如下:
RQ1:两阶段DRL效率。将调度问题分解为单独的任务选择和虚拟机分配阶段,将动作空间复杂性从O(N×M)降低到O(N)+O(M)。这种结构优势使得收敛速度更快,性能优于启发式和元启发式基线方法,后者通常产生较弱的结果,同时计算时间显著增加。
RQ2:多目标权衡。基于偏好的奖励公式使代理能够有效地平衡制作周期、能源消耗和QoS延迟。使用多样化的偏好向量进行训练产生了广泛的Pareto前沿,在超体积和IGD指标上均优于基线方法。这证实了2SD-GAT奖励设计能够在动态多目标环境中成功地引导代理找到多样化、高质量的解决方案。敏感性分析进一步表明,该框架对偏好权重的变化反应稳定且可解释。
RQ3:基于GNN的依赖性表示。GNN编码器对于捕捉工作流程DAG的拓扑结构至关重要。与固定输入模型不同,GNN能够在形状和复杂性不同的工作流程中泛化。在未见过的真实世界轨迹上的强劲性能表明,编码器成功捕获了关键的结构信息。消融研究进一步验证了这一设计选择:用GIN或MLP替换GAT会导致多目标性能下降,从而确认了基于注意力的图编码在两阶段DRL架构中的适用性。
B. 与现有研究的比较分析
为了将2SD-GAT的贡献置于上下文中,表17提供了与几项最近使用机器学习和强化学习的云工作流调度研究的比较分析。该表总结了关键方面,包括优化目标、决策模型、动态环境的支持、结构建模(例如,DAG意识)和Pareto意识。
因此,2SD-GAT通过整合两阶段DRL和基于GNN的过程,在文献中填补了一个重要空白,其中任务选择和资源分配是分开的,并通过GNN和MLP的组合来实现。此外,基于偏好的奖励调优使该方法能够在不同环境中进行评估和应用,这体现在得到的Pareto前沿上。因此,这为未来的研究提供了一个非常有前景的方向。
C. 研究局限性和未来研究方向
然而,尽管有其优势,本研究也观察到了一些局限性。一个主要问题与两阶段代理的计算开销有关,因为两阶段PPO结构增加了训练时间,特别是对于具有数百个任务的大型工作流程DAG。随着工作流程规模扩展到数千个任务和大量的虚拟机池,这种开销可能会转化为增加的推理延迟,在极端情况下,简单的启发式方法可能会提供更有利的成本效益 trade-off。虽然这种开销远低于平面动作空间方法(例如[43]),并且在基于DRL的调度器中很常见,但它仍然会导致明显的性能成本。
另一个局限性在于每个训练实例中使用固定的基于偏好的奖励权重(λ1, λ2, λ3)。虽然这种策略有效地产生了一组多样化的Pareto最优解,但它需要训练具有不同偏好设置的多个代理以覆盖整个权衡空间。一个更灵活的替代方案是根据作为输入提供的偏好向量来条件化策略,使单个代理能够在推理时根据所需的目标权重调整其行为。这种方法将允许单个代理在偏好配置之间进行泛化,显著减少重新训练的需求。因此,开发基于偏好的策略是未来工作的一个关键方向。
此外,尽管使用了合成和真实世界轨迹数据集,但模拟环境必然抽象了一些系统级因素,如网络延迟、虚拟机启动时间和来自共位作业的干扰。这些简化在工作流调度研究中很常见,但将它们纳入考虑将使评估更接近生产云平台的操作条件。未来的工作将探索纳入更丰富的系统级动态,包括网络延迟、虚拟机启动延迟和来自共位工作负载的干扰,以更好地近似生产云环境。当前的QoS公式也简化了,因为延迟是通过任务开始时的二进制优先级机制来建模的。更具有表现力的约束,如抖动限制、突发截止时间或基于百分位的延迟保证,可以提供更真实的服务级期望表示。
另一个重要的未来研究方向是建模更丰富的资源动态。虽然研究通过单一虚拟机故障事件来模拟虚拟机不可用性,但真实的云系统表现出更丰富的不确定性形式,包括资源容量的波动、部分性能下降以及主机或机架之间的相关性故障。捕捉这些行为将更准确地反映真实世界环境中的变化。此外,当前框架假设了一组固定的虚拟机供应。将其扩展到包括动态资源供应,如弹性扩展或成本意识虚拟机获取,将允许调度器共同考虑任务放置和资源扩展。
另一个方向是扩展2SD-GAT框架到多样化的云相关环境,如边缘-云混合环境或边缘计算,这将增强模型在真实世界多租户调度场景中的适用性。
最后,尽管本研究相对于选定的基线展示了强大的性能,但在统一的实验设置下系统地对更广泛的当代DRL调度方法进行基准测试仍然是未来研究的一个重要方向。将比较扩展到包括多样化的模型架构、训练协议和工作负载特性,将能够进行更清晰的跨方法泛化分析,并提供对不同DRL调度范式相对优势和限制的更深入洞察。这些努力还将支持更标准的评估实践,并促进未来研究之间的公平比较。
第六节 结论
云工作流调度是一个关键且具有挑战性的NP难问题,需要在动态运行条件下同时优化相互冲突的目标,如制作周期、能源消耗和QoS延迟。现有方法往往无法充分模拟复杂的任务依赖性或有效平衡这些多目标权衡。为此,本研究提出了2SD-GAT,这是一个新颖的动态调度框架,它结合了两阶段深度强化学习和图神经网络。通过将调度问题分解为任务选择和虚拟机分配阶段,并利用图注意力网络(GAT)来捕捉工作流结构,所提出的方法实现了智能、自适应的决策制定。
在合成和真实世界数据集上的广泛评估中得到的关键发现表明,2SD-GAT显著优于传统的启发式方法和最先进的DRL基线。具体来说,它在Pareto最优解方面实现了更快的收敛速度和更高的多样性,在动态条件下,超体积增加了26.8%,IGD降低了4.5倍,同时保持了低决策延迟。
尽管存在一些限制,例如两阶段PPO架构的培训成本增加和对固定偏好权重的依赖,该框架显示出很大的扩展潜力。未来的研究将探索基于偏好的策略、更丰富的系统级不确定性模型以及动态资源供应,以及更广泛的部署场景,如边缘-云环境。这些方向旨在进一步增强2SD-GAT的实际适用性,并增强其在多样化的真实世界云环境中的运作能力。