GNN-RL：基于图神经网络和强化学习的多目标高性能计算调度

《Future Generation Computer Systems》：GNN-RL: Multi-objective HPC scheduling with graph neural networks and reinforcement learning

　　

高性能计算（High-performance computing, HPC）系统在计算需求达到百亿亿次（exascale）级别且工作负载日益异构化的背景下，面临日益严峻的资源分配挑战。传统调度方法难以有效管理多样化且波动的工作负载，而近期的机器学习方法未能充分捕捉作业、资源与系统状态之间的复杂交互。研究人员提出了GNN-RL框架，该框架集成了图注意力网络（Graph Attention Networks, GAT）与近端策略优化（Proximal Policy Optimization, PPO），以解决HPC调度中的根本局限性。该方法通过提供高效的图结构状态表示来补充近期不确定性感知和数字孪生（digital twin）调度器，从而捕捉复杂的作业依赖关系和资源拓扑。通过多头注意力机制和复杂的状态表示，GNN-RL同时优化了资源利用率、作业吞吐量、总完成时间（makespan）和系统公平性。对来自阿贡领导力计算设施（Argonne Leadership Computing Facility, ALCF）三个系统（Polaris、Mira和Cooley）的377,234个作业的综合评估表明，与EASY-backfilling相比，该框架取得了显著改进：资源利用率提升13.8%–20.2%，吞吐量提高15.0%–50.0%，总完成时间缩短12.1%–12.8%，且统计验证证实了显著性和大效应量。作业级分析显示，中等规模的批处理作业（16–128个节点）从基于图的调度中获益最大（利用率提高15.3个百分点），而大型作业（>128个节点）的增益较小，并存在轻微公平性权衡。该框架在50 K并发作业下保持了76%的有效性，展现出在HPC环境中实际应用的强大潜力。

《Future Generation Computer Systems》期刊上发表的论文《GNN-RL：基于图神经网络和强化学习的多目标高性能计算调度》针对当前高性能计算（High-performance computing, HPC）系统在百亿亿次（exascale）时代下面临的资源分配挑战，开展了深入的研究。研究背景源于传统调度方法（如先来先服务（First-Come First-Served, FCFS）、最短作业优先（Shortest Job First, SJF））难以应对日益异构和动态的工作负载，而现有的机器学习调度方法往往无法充分捕捉作业、资源与系统状态之间复杂的时空依赖关系。此外，当前方法在状态表示、单目标优化以及静态策略学习方面存在局限，导致调度效率低下，造成大量计算资源闲置。为此，研究人员开展了GNN-RL研究，旨在解决这些根本性问题，通过整合图注意力网络（Graph Attention Networks, GAT）与近端策略优化（Proximal Policy Optimization, PPO）算法，构建一种能够同时优化资源利用率、作业吞吐量、总完成时间（makespan）和系统公平性的多目标调度框架。该研究使用了来自阿贡领导力计算设施（Argonne Leadership Computing Facility, ALCF）三个实际系统（Polaris、Mira和Cooley）的大规模历史作业跟踪数据（共377,234个作业）进行验证。研究结果表明，GNN-RL显著优于传统的EASY-backfilling调度器，在多个关键指标上取得大幅提升，且统计验证确认了改进具有显著性和大效应量。该研究的重要意义在于为下一代HPC调度器提供了全新的图结构学习范式，能够显著提升系统资源利用率，潜在地节省数百万到数十亿美元的经济成本，并加速科学发现进程。

为开展此项研究，研究人员主要采用了以下关键技术方法：首先，构建加权有向多图（weighted directed multi-graph）来表示HPC系统状态，其中节点代表作业，边包含依赖（dependency）、资源竞争（resource competition）、时间（temporal）和用户亲和性（user affinity）四种类型，节点特征涵盖资源需求、时间属性和作业属性。其次，采用三层图注意力网络（GAT）作为状态编码器，利用多头注意力机制聚合邻居信息，生成稳定的图嵌入（embedding）。接着，将调度过程建模为多目标马尔可夫决策过程（Markov Decision Process, MDP），并设计基于近端策略优化（PPO）的强化学习算法，通过全局池化（global pooling）处理变长图输入，结合经验回放（experience replay）实现策略的连续优化。最后，引入元学习（meta-learned）的自适应奖励权重机制，动态平衡四个竞争目标（资源利用率U、吞吐量T、公平性F、总完成时间M），避免了单一目标优化的病态权衡。

研究结果部分通过多个维度展示了GNN-RL的性能与洞见，具体小标题及对应结论如下：

1. 1.
   Introduction
   研究人员在引言中指出，HPC调度因状态空间组合爆炸、工作负载非平稳性以及目标相互竞争而极具挑战。通过对比现有方法，明确了GNN-RL的创新点在于图结构状态表示、多目标自适应奖励以及PPO与经验回放的结合，为后续方法论奠定基础。
2. 2.
   Related work and positioning
   通过系统对比传统调度算法（如EASY-backfilling、SLURM）和机器学习方法（如DRAS、Decima），揭示了先前工作在有限状态表示、单一目标优化等方面的四大局限。GNN-RL通过图结构编码、混合批处理与依赖处理、自适应多目标平衡等创新，填补了这些空白，其Polaris系统资源利用率达到78.4%，超越了对比基线。
3. 3.
   Methodology
   详细阐述了GNN-RL架构。图构建部分定义了节点特征向量和四种边类型；GAT组件利用多头注意力生成作业嵌入；PPO算法将图嵌入通过全局池化后输入策略网络，输出作业到资源的分配动作；多目标奖励函数结合元学习权重，动态调整四个目标贡献。此外，还考虑了提前预留（advance reservations）对状态空间和奖励计算的影响。
4. 4.
   Experimental design
   研究人员利用ALCF的Polaris、Mira和Cooley系统的377,234个真实作业跟踪数据，在模拟环境中进行五轮独立运行。对比基线包括EASY-backfilling、DRAS和Decima。评估指标涵盖资源利用率、吞吐量、总完成时间和公平性，并采用Cohen's d效应量和Bonferroni校正后的p值进行严格统计验证。
5. 5.
   Results and analysis
   系统级评估显示，GNN-RL在所有三个系统上均显著优于EASY-backfilling，资源利用率提升13.8%–20.2%，吞吐量提升15.0%–50.0%，总完成时间缩短12.1%–12.8%，且所有改进均具有统计显著性（p < 0.001）和大效应量（Cohen's d > 0.8）。与重新实现的DRAS和Decima相比，GNN-RL在Polaris上利用率分别高出6.1%和8.6%。作业级分析表明，中等规模批处理作业（16–128节点）获益最大，利用率提升15.3个百分点；大型作业（>128节点）虽有改进但存在轻微公平性权衡。消融实验证实了图注意力、经验回放和自适应奖励权重等关键模块的有效性。扩展性测试显示，在50,000个并发作业时框架仍保持76%的有效性。
6. 6.
   Discussion
   研究人员在讨论部分指出，GNN-RL通过图结构表示和自适应多目标优化，有效解决了HPC调度的核心挑战。其图注意力机制提供了隐式鲁棒性，无需额外贝叶斯层。尽管在超大规模作业上略有公平性牺牲，但整体性能提升显著。该框架为未来结合不确定性量化（如HARMONIC）和数字孪生（如AIMS）等互补技术提供了基础，代表了向自适应、结构感知调度迈出的重要一步。
7. 7.
   Conclusion
   研究结论指出，GNN-RL成功地将图注意力网络与近端策略优化相结合，用于HPC作业调度。该框架通过多关系图表示捕捉复杂的作业依赖和资源拓扑，通过元学习自适应奖励权重实现多目标优化，并在三个ALCF系统的大规模真实跟踪数据上验证了其有效性。实验结果显示，与EASY-backfilling相比，资源利用率、吞吐量和总完成时间均有显著且具统计意义的改善。这项工作为开发下一代HPC调度器提供了可扩展且实用的解决方案，能够适应现代计算环境中复杂、异构的工作负载。