面向网格作业运行时间预测的防泄漏与调度器感知机器学习

# 防泄漏且调度器感知的网格作业运行时长预测机器学习方法
来源：https://arxiv.org/html/2609.13701
Ashfaq Ali Shafin所属机构：美国奥古斯塔纳学院，美国佛罗里达国际大学，邮箱：[email protected]；Khandaker Mamun Ahmed

###### 摘要

准确的作业运行时长预测可改善网格与分布式计算环境中的调度感知资源管理，但预测模型必须在现实部署约束条件下进行评估。本文在GWA-T-4 AuverGrid工作负载追踪数据上重新审视CPU突发时间预测问题，并将其重新定义为防泄漏的执行前作业运行时长预测。我们将预测目标定义为作业级运行时长，仅使用提交时属性，排除执行后变量，并在时间序列和冷启动条件下评估模型，而非仅依赖随机交叉验证。我们比较了标准回归器、时序历史基线、分类变量编码策略以及具有原生分类变量处理能力的CatBoost算法。进一步增加时间超参数调优、运行时长可预测性分析、特征消融、按作业长度的误差分析及最小化调度模拟。经过时序验证调优后，CatBoost在时序测试集上取得最佳部署导向结果：R²=0.239，MAE=27,019，RMSE=46,587，LogMAE=2.646。对全部69,523个时序测试作业的单服务器模拟表明，预测驱动的SJF（最短作业优先）调度相比FCFS（先来先服务）平均等待时间降低50.92%。结果表明：随机划分评估会高估性能；分类变量原生提升算法能改善时序泛化能力；长作业预测低估仍是与调度器相关的重要挑战。

###### 关键词：

网格工作负载预测、运行时预测、CPU突发时间、防泄漏评估、部署感知评估、CatBoost、调度模拟、机器学习、分布式系统

## Ⅰ 引言

进程和作业调度是操作系统、网格平台和分布式计算环境的基本功能。在多任务操作系统中，进程调度器决定哪个进程应被分配到CPU。常见调度算法包括先来先服务（FCFS）、时间片轮转（RR）、优先级调度、最短作业优先（SJF）和最短剩余时间优先（SRTF）[1]。在网格和高性能计算环境中，调度决策影响等待时间、周转时间、减速比、公平性、资源利用率和吞吐量。

CPU突发指进程在CPU上执行直至阻塞、终止或离开运行状态的时间间隔[2]。然而在生产网格工作负载追踪中，可用的目标通常是作业级运行时长，而非I/O操作之间的细粒度CPU突发。因此，本文在调度语境下使用“CPU突发时间预测”这一术语，但将可测量的预测目标精确定义为GWA-T-4 AuverGrid追踪记录的作业级运行时长。该定义避免了操作系统级CPU突发与网格工作负载作业时长之间的概念混淆。

可靠的运行时长估计对多种调度策略具有价值。SJF和SRTF优先调度预期执行时间较短的作业。回填和基于预留的调度器使用运行时长估计来判断作业能否在不延迟预留高优先级作业的前提下执行。时间片轮转调度的自适应变体也可能利用运行时长分布来确定时间片。但在实际应用中，新提交作业的实际运行时长在执行前是未知的。调度器必须仅使用作业提交时或之前可用的信息来估计运行时长。

这一需求带来了方法论挑战。工作负载追踪包含执行前变量和执行后结果。如果使用观测运行时长、等待时间、作业状态、内存使用量、CPU时间、分区分配或上次运行站点等执行后变量作为输入特征，预测任务将对执行前调度部署无效。这些变量在调度器决策时不可用，可能导致目标泄漏。模型可能因间接观测到目标或未来执行结果而显得精度极高。

机器学习为运行时长预测提供了有前景的方法，因为监督模型可以学习作业提交属性、请求资源、用户行为、组成员关系、队列分配、站点信息和可执行标识之间的关联。先前研究已将基于学习的方法应用于运行时长预测和调度相关决策[3,4,5,6]。然而，要使机器学习在调度感知系统中发挥作用，评估必须是防泄漏、时间感知且与调度行为相关，而不仅仅报告孤立的回归精度。

本文使用GWA-T-4 AuverGrid工作负载追踪[7]修订并强化CPU突发时间预测。核心贡献并非新回归算法，而是在现实信息约束下对网格运行时长预测进行严格的部署感知再评估。我们定义了严格的执行前预测任务，排除所有提交时未知属性，仅在训练分区上拟合预处理，评估随机划分和部署导向划分，增加时序安全历史基线，比较分类变量编码策略，使用时序验证划分调优CatBoost，分析运行时长可预测性，解释特征消融结果，并增加最小化调度模拟。

本研究回答以下问题：
- •RQ1：仅使用作业提交时可用属性，机器学习模型能多准确地预测网格作业运行时长？
- •RQ2：基于学习的模型与仅使用每个测试作业历史数据的时序历史基线相比如何？
- •RQ3：分类变量编码和原生分类建模如何影响时序泛化能力？
- •RQ4：哪些提交前特征组对时序预测性能贡献最大？
- •RQ5：短、中、长、超长及极端时长作业的预测误差有何差异？
- •RQ6：预测驱动的调度能否在最小化调度模拟中改善等待时间？

主要贡献包括：
- •明确预测目标，将AuverGrid追踪上的CPU突发时间预测定义为作业级运行时长预测。
- •引入防泄漏特征策略，仅使用提交前属性并排除执行后结果。
- •评估时序安全历史基线，防止未来信息影响基线预测。
- •比较独热编码、序数编码、目标均值编码和原生分类建模策略，包括时序验证调优的CatBoost。
- •增加运行时长可预测性分析、特征消融、排列重要性、已完成作业过滤及按作业长度组的误差偏差分析。
- •提供最小化调度模拟，证明预测驱动的SJF在简化非抢占设置中能相对FCFS减少等待时间。

## Ⅱ 背景与相关工作

### Ⅱ-A 经典运行时长与突发时间估计

多种调度算法需要预测未来的突发时间或作业时长。经典方法是指数平均法，其中下一个预测突发时间由最近观测突发时间和前次预测计算得出：

τ_{n+1}=αT_n+(1−α)τ_n  (1)

其中T_n是最近观测运行时长，τ_n是前次估计值，α控制近期历史的影响权重。该公式常见于操作系统调度讨论[1,8]。其优势是简单且计算开销低，但使用信息有限，可能不足以应对异构网格工作负载。

基于优化和基于规则的方法也被探索。Maheshwari等人提出使用线性规划模型对偶单纯形算法（LPMDSA）的调度方法，将突发时间、等待时间和周转时间数学化表示并通过对偶单纯形法优化[9]。Pourali等人提出智能模糊系统从历史进程行为估计CPU突发时间[10]。这些研究证明历史执行行为具有价值，但通常需要人工设计规则或问题特定假设。

### Ⅱ-B 机器学习用于运行时长预测

机器学习已被广泛探索用于运行时长预测和调度相关决策。Smith等人提出通过识别相似历史应用并使用搜索方法确定应用特征相似性的并行应用运行时长预测方法[5]。Negi等人将机器学习应用于Linux CPU调度，旨在通过学习CPU时间片利用行为减少进程周转时间[3]。Shulga等人研究了异构环境中的学习型CPU/GPU执行选择[4]。Helmy等人使用机器学习在GWA-T-4 AuverGrid数据集上研究CPU突发时间估计[6]。本工作在该方向上以更严格的特征可用性、时序基线、分类变量原生建模、时序调优和调度器级验证进行再审视。

### Ⅱ-C 调度相关性与评估现实性

近期HPC运行时长预测工作强调预测应与调度决策关联，而非仅作为孤立回归问题评估。时长感知工作负载调度器（DIWS）将机器学习运行时长估计集成到HPC调度策略中，并通过模拟评估调度效果[11]。RLBackfilling表明仅更好的运行时长预测不一定能改善回填决策，因为预测精度与回填机会之间存在权衡[12]。HPC运行时长预测的最佳实践研究强调仔细的方法论设计和有意义的运营评估[13]。基于数字孪生的调度框架进一步表明预测和模拟可结合评估部署前的自适应调度策略[14,15]。这些工作促进了我们的部署感知预测基准和最小化调度器级验证。

## Ⅲ 数据集与特征策略

表Ⅰ：过滤前后数据集统计。表Ⅱ：运行时长预测防泄漏特征策略。

### Ⅲ-A GWA-T-4 AuverGrid工作负载追踪

本研究使用GWA-T-4 AuverGrid工作负载数据集[7,16]（见表Ⅰ）。AuverGrid是由位于法国奥弗涅地区多个集群构成的生产网格平台。该追踪包含作业提交和执行记录，包括提交时间、请求资源、用户和组标识、可执行标识、队列信息、运行时长及执行后结果。

原始数据集包含404,176个作业和29列。过滤无效运行时长和提交时间记录并应用防泄漏特征策略后，主要实验数据集包含347,611个作业。

### Ⅲ-B 目标定义

预测目标是AuverGrid追踪中记录的作业级运行时长。我们将其记为作业i的y_i。该追踪不提供I/O操作间的细粒度CPU突发。因此，在整个实验部分中，CPU突发时间指调度器在作业执行前希望估计的运行时长。

### Ⅲ-C 防泄漏特征策略

表Ⅱ列出了修订后的特征策略。仅提交前字段可作为特征候选。执行后变量被排除，因为它们在调度器决策时不可用。

最终特征集包含11个数值特征和5个分类特征。数值特征包括：SubmitTime、SubmitTimeSinceStart、循环小时/日/周特征、ReqNProcs、ReqTime和ReqMemory。分类特征包括：UserID、GroupID、ExecutableID、QueueID和OrigSiteID。

### Ⅲ-D 提交时间特征工程

原始提交时间可能难以直接供模型使用。因此我们导出时间特征以捕获单调趋势和周期性工作负载结构。设s_i为作业i的提交时间，s_0为保留追踪中的最早提交时间。定义：

Δs_i = s_i - s_0  (2)

使用正弦和余弦变换表示小时、日和周信号：

sin(2πz/P), cos(2πz/P)  (3)

其中z是对应小时、日或周索引，P是周期长度。该表示避免了相邻时间（如23时与0时）之间的人为不连续性。

## Ⅳ 方法论

### Ⅳ-A 预测任务

我们将网格作业运行时长预测公式化为监督回归。对于每个作业i，输入向量x_i仅包含提交前属性，目标y_i是观测运行时长。目标是学习f(x_i)在作业执行前预测ŷ_i。

### Ⅳ-B 模型与编码策略

我们评估线性、基于距离、基于树和提升模型。模型集包括线性回归、线性SVR、K近邻、决策树、随机森林、梯度提升、XGBoost和CatBoost。由于分类标识符对工作负载预测至关重要，我们比较独热编码、序数编码、目标均值编码和CatBoost的原生分类处理。K近邻使用独热编码评估，因为序数编码会在无序标识符间引入人为距离。

包含CatBoost是因为它使用有序目标统计量原生处理分类变量，能减少对高维独热编码的需求。这对于用户和可执行标识符携带历史行为信息的工作负载追踪尤为重要。

表Ⅲ：运行时长分布与可预测性分析。熵在log(1+RunTime)上估计。

### Ⅳ-C 时序历史基线

如果历史基线在随机划分下汇总所有训练记录而不尊重每个测试作业的提交时间，可能意外使用未来信息。为避免此问题，我们实现时序安全基线...