Source-linked AI summary
Leakage-Safe and Scheduler-Aware Machine Learning for Grid Job Runtime Prediction
Ashfaq Ali Shafin, Khandaker Mamun Ahmed
TL;DR
Pre-execution runtime prediction matters to scheduling, but post-execution variables can leak information unavailable when a scheduler decides. The paper evaluates leakage-safe job-runtime prediction on AuverGrid using temporal methods and a temporally tuned CatBoost model. On the held-out temporal test set, tuned CatBoost achieves R2 = 0.239, MAE = 27,019, RMSE = 46,587, and LogMAE = 2.646.
Problem
Scheduling requires runtime estimates before execution, while post-execution trace variables can make pre-scheduling prediction invalid through target leakage.
Source: §I · p. 1Method
The paper defines a pre-execution job-runtime task on AuverGrid, excludes unavailable post-execution attributes, and evaluates models with deployment-oriented temporal settings and chronological baselines.
Source: §I · p. 1Results
R2 = 0.239, MAE = 27,019, RMSE = 46,587, and LogMAE = 2.646 for tuned CatBoost on 69,523 held-out later jobs.
Source: B. Main Temporal Result · p. 5Takeaways & Limitations
Random splitting substantially overestimates deployment performance, while long-job underestimation remains a scheduler-relevant challenge.
Source: §IX · p. 8The study uses one workload trace, so its results may not generalize to all grid, cloud, or HPC environments.
Source: §VII · p. 7
Abstract
from arXiv · showhide
Accurate job runtime prediction can improve scheduling-aware resource management in grid and distributed computing environments, but prediction models must be evaluated under realistic deployment constraints. This paper revisits CPU burst time prediction on the GWA-T-4 AuverGrid workload trace and reformulates it as leakage-safe pre-execution job runtime prediction. We define the target as job-level runtime, use only submission-time attributes, exclude post-execution variables, and evaluate models under temporal and cold-start settings rather than relying only on random cross-validation. We compare standard regressors, chronological historical baselines, categorical encoding strategies, and CatBoost with native categorical handling. We further add temporal hyperparameter tuning, runtime predictability analysis, feature ablation, error analysis by job length, and a minimal scheduling simulation. After temporal-validation tuning, CatBoost achieves the strongest deployment-oriented result with R^2=0.239, MAE=27,019, RMSE=46,587, and LogMAE=2.646 on the held-out temporal test set. A single-server simulation over all 69,523 held-out temporal test jobs shows that prediction-informed SJF reduces average waiting time by 50.92% relative to FCFS. The results show that random-split evaluation overestimates performance, categorical-native boosting improves temporal generalization, and long-job underestimation remains a scheduler-relevant challenge.
I. INTRODUCTION
The paper reframes CPU burst time prediction as pre-execution prediction of job-level runtime and argues that scheduling use requires submission-time information and deployment-aware evaluation. It evaluates leakage-safe prediction alongside chronological baselines and scheduling behavior.
I. INTRODUCTION
- The measurable target is job-level runtime in the AuverGrid trace, rather than fine-grained CPU bursts between I/O operations.The paper uses “CPU burst time prediction” in the scheduling sense while specifying the recorded job runtime as its target.Source: §I · p. 1
- Runtime estimates matter because schedulers use them for SJF, SRTF, backfilling, reservations, and adaptive Round-Robin decisions.Actual runtime is unknown before execution, so a scheduler must estimate it from information available by submission.Source: §I · p. 1
- Post-execution variables are unavailable at submission and can leak target or future-outcome information into pre-scheduling predictions.The feature policy therefore uses only pre-submit attributes and excludes post-execution outcomes.Source: §I · pp. 1–2
- The evaluation compares learning models with chronological-safe historical baselines and tests categorical encoding strategies, including CatBoost’s native handling.Its stated questions also address pre-submit feature groups and prediction errors across job-length groups.Source: §I · p. 2
- The study adds runtime predictability analysis, feature ablation, permutation importance, and job-length error analysis, then tests prediction-informed SJF in a minimal simulation.The simulation compares waiting time with FCFS in a simplified non-preemptive setting.Source: §I · p. 2
II. BACKGROUND AND RELATED WORK
The background describes exponential averaging as a simple, low-overhead runtime-estimation approach, then surveys optimization-based and fuzzy alternatives that use historical behavior but may rely on manual rules or problem-specific assumptions.
A. Classical Runtime and Burst-Time Estimation
- Exponential averaging predicts the next burst from the latest observed runtime and prior estimate, with a parameter controlling how much recent history matters.Its simplicity and low computational overhead come with limited information for heterogeneous grid workloads.Source: A. Classical Runtime and Burst-Time… · p. 2
- LPMDSA represents burst time, waiting time, and turnaround time mathematically for dual-simplex optimization, while a fuzzy system estimates CPU burst time from prior process behavior.The cited approaches show historical behavior can inform estimates, but can require manually designed rules or problem-specific assumptions.Source: A. Classical Runtime and Burst-Time… · p. 2
B. Machine Learning for Runtime Prediction
The related work spans machine-learning runtime prediction and scheduler evaluation, while this study uses the GWA-T-4 AuverGrid trace to revisit runtime prediction under stricter information and evaluation constraints.
B. Machine Learning for Runtime Prediction
- Prior work applies machine learning to application runtime prediction, CPU scheduling, CPU/GPU execution selection, and CPU burst estimation on AuverGrid; this study revisits the last direction with stricter validation.The revised evaluation adds stricter feature availability, chronological baselines, categorical-native modeling, temporal tuning, and scheduler-level validation.Source: B. Machine Learning for Runtime… · p. 2
C. Scheduling Relevance and Evaluation Realism
- HPC studies motivate evaluating runtime prediction through scheduling decisions: better estimates do not always yield better backfilling, and simulation can assess policies before deployment.DIWS integrates learned runtimes into scheduling; RLBackfilling highlights a trade-off between prediction accuracy and backfilling opportunities.Source: C. Scheduling Relevance and Evaluation… · p. 2
A. GWA-T-4 AuverGrid Workload Trace
- The GWA-T-4 AuverGrid trace records job submissions and executions, and filtering invalid runtime or submission-time records yields 347,611 jobs from 404,176 original jobs.The trace includes submission time, requested resources, user and group identifiers, executable identifiers, queue information, runtime, and post-execution outcomes.Source: A. GWA-T-4 AuverGrid Workload Trace · pp. 2–3
B. Target Definition
The paper defines its target as trace-recorded job-level runtime, not fine-grained CPU bursts, and restricts prediction inputs to fields available before submission-time decisions. It also derives temporal features that encode elapsed time and periodic patterns.
B. Target Definition
- The target is job-level runtime in the AuverGrid trace; the trace does not provide fine-grained CPU bursts between I/O operations.In the experimental sections, “CPU burst time” means the runtime a scheduler estimates before execution.Source: B. Target Definition · p. 3
C. Leakage-Safe Feature Policy
- Only pre-submit fields are eligible features, excluding post-execution variables unavailable at scheduling time; the final set has 11 numeric and 5 categorical features.The categorical fields are UserID, GroupID, ExecutableID, QueueID, and OrigSiteID.Source: C. Leakage-Safe Feature Policy · p. 3
D. SubmitTime Feature Engineering
- Submission time is represented by elapsed time from the trace’s earliest submission and cyclic hour, day, and week signals; sine/cosine encoding avoids artificial boundaries between adjacent times.The cyclical features cover hour-of-day, day-of-week, and week-of-year.Source: D. SubmitTime Feature Engineering · p. 3
IV. METHODOLOGY
The methodology frames runtime prediction as pre-execution supervised regression, compares model and categorical-encoding choices, and uses chronological-safe historical baselines to avoid future information.
A. Prediction Task
- Each job’s input contains only pre-submit attributes and its target is observed runtime, which the model predicts before execution.This defines the task as supervised regression.Source: A. Prediction Task · p. 3
B. Models and Encoding Strategies
- The study compares linear, distance-based, tree-based, and boosting regressors alongside one-hot, ordinal, target-mean, and CatBoost-native categorical handling.K-NN uses one-hot encoding because ordinal codes impose artificial distances between unordered identifiers.Source: B. Models and Encoding Strategies · p. 3
- The methodology reports runtime-distribution and predictability analysis in addition to comparing models and encoding strategies.The supplied table caption identifies the analysis as runtime distribution and predictability, with entropy estimated on log(1 + runtime).Source: Table III · p. 4
C. Chronological Historical Baselines
- Historical user, group, and executable baselines use only earlier training jobs for each test job, falling back to the global training median when no prior entity history exists.This chronological constraint is applied to median and exponential-moving-average baselines.Source: C. Chronological Historical Baselines · p. 4
D. Evaluation Protocol
The evaluation uses time-respecting splits and validation, then examines runtime uncertainty and scheduling behavior alongside prediction metrics.
D. Evaluation Protocol
- The 80/20 temporal split trains on the earliest jobs and tests on the latest, with hyperparameters selected using only inner temporal validation.The CatBoost configuration is refit on the full temporal training set and evaluated once on the held-out test set.Source: D. Evaluation Protocol · p. 4, E. CatBoost Temporal Tuning · p. 4
E. CatBoost Temporal Tuning
- CatBoost tuning uses an inner temporal validation split before refitting the selected configuration on the full temporal training set.The tuned model is evaluated once on the held-out temporal test set.Source: E. CatBoost Temporal Tuning · p. 4
F. Runtime Predictability Analysis
- Normalized entropy of log(1 + RunTime) describes runtime uncertainty but does not establish an irreducible prediction-error bound.The analysis reports entropy in bits and normalization relative to the maximum entropy of nonempty histogram bins.Source: F. Runtime Predictability Analysis · p. 4
G. Minimal Scheduling Simulation
- The single-server, non-preemptive simulation compares FCFS, prediction-informed SJF, and oracle SJF on all 69,523 held-out temporal jobs.Oracle SJF uses true runtimes as an upper bound; the simulation is not a full HPC backfilling simulator.Source: G. Minimal Scheduling Simulation · p. 4
H. Metrics
- Prediction quality is measured with R2, MAE, RMSE, and Log-MAE, while scheduling is assessed using waiting time, turnaround time, and improvement over FCFS.Log-MAE is included because grid runtimes are long-tailed.Source: H. Metrics · p. 4
V. EXPERIMENTAL RESULTS
The results characterize a highly skewed workload and frame comparisons across evaluation splits, chronological baselines, and categorical strategies.
A. Runtime Distribution and Predictability
- The runtime median is 2,658 seconds versus a 25,802-second mean, and normalized entropy of log(1 + RunTime) is 0.921.The maximum runtime is 1,575,814 seconds; the 95th and 99th percentiles are 97,796 and 173,200 seconds.Source: A. Runtime Distribution and… · p. 4
- Table V frames results across random, temporal, and cold-start settings, describing random splitting as optimistic and temporal and cold-start splits as more deployment-oriented.The supplied caption does not provide the table's cell values.Source: Table V · p. 5
- Table VI scopes chronological-safe historical baselines to entity histories submitted earlier than each test job.The caption describes the baseline timing constraint but supplies no performance values.Source: Table VI · p. 5
- Table VII compares categorical encoding strategies on the temporal 80/20 split, including CatBoost with native categorical handling and temporally selected hyperparameters.The caption does not provide comparative cell values.Source: Table VII · p. 5
B. Main Temporal Result
The tuned CatBoost model leads the reported temporal result, while split choice, chronological history, and categorical handling shape the comparisons.
B. Main Temporal Result
- R2 = 0.239, MAE = 27,019, RMSE = 46,587, and LogMAE = 2.646 for tuned CatBoost on 69,523 held-out later jobs.The hyperparameters are selected using only inner temporal validation.Source: B. Main Temporal Result · p. 5
C. Random, Temporal, and Cold-Start Summary
- Random splitting gives the strongest apparent performance, while temporal and cold-start settings are substantially more difficult; temporal tuning improves reproducibility by avoiding test-set model selection.The tuned temporal result is lower than the earlier untuned CatBoost value.Source: C. Random, Temporal, and Cold-Start… · p. 5
D. Chronological-Safe Historical Baselines
- User-level exponential moving average reaches R2 = 0.638 and MAE = 8,847 under random splitting, but user median reaches R2 = 0.064 temporally.Several other entity-level temporal baselines have negative R2 values.Source: D. Chronological-Safe Historical… · p. 5
E. Categorical Encoding and CatBoost
- Target-mean encoding improves several conventional models, with Gradient Boosting reaching R2 = 0.107, while tuned native-categorical CatBoost reaches R2 = 0.239.The passage notes that ordinal encoding imposes arbitrary numeric order on unordered identifiers.Source: E. Categorical Encoding and CatBoost · p. 6
F. Feature Ablation
Feature ablation, completed-job filtering, feature importance, error bias, and a simplified scheduling simulation provide complementary views of temporal prediction behavior.
F. Feature Ablation
- R2=0.239 for all features versus R2=0.126 for identifier-only; requested-resource-only features yield a negative R2 with tuned CatBoost.The passage contrasts this with an earlier Random Forest ablation in which all features performed worse than identifier-only.Source: F. Feature Ablation · p. 6
G. Completed-Only Label Quality Analysis
- Gradient Boosting reaches the best completed-only temporal R2 = 0.065, while results remain low despite completed jobs comprising 96.68% of the filtered dataset.The completed-only analysis indicates that label-quality filtering alone does not explain temporal generalization difficulty.Source: Table IX · p. 6, G. Completed-Only Label Quality Analysis · p. 6
H. Permutation Importance
- UserID, GroupID, and ReqTime rank among the most influential features for the temporal Random Forest model.Repeated user and group behavior remains central to prediction, with requested time contributing additional signal.Source: Table X · p. 6, H. Permutation Importance · p. 6
I. Error Analysis by Job Length
- Extreme jobs are underestimated 99.97% of the time, with mean error −105,448 seconds; short and medium jobs are overestimated.The passage identifies long-job underestimation as potentially more harmful for reservation-based and backfilling schedulers.Source: §I · p. 6, Table XI · p. 7
J. Minimal Scheduling Simulation
- In a minimal single-server scheduling simulation on all 69,523 held-out temporal test jobs, predicted SJF using tuned CatBoost runtime estimates reduced average waiting time by 50.92% versus FCFS, compared with 75.83% for oracle SJF using true runtimes.Oracle SJF serves only as an upper bound.Source: J. Minimal Scheduling Simulation · p. 6
VI. DISCUSSION
Temporal and cold-start evaluation presents a harder deployment challenge than random splitting suggests. CatBoost's native categorical handling recovers meaningful temporal performance, while runtime uncertainty remains substantial.
A. What the Revised Results Show
- Random-split scores are not deployment-valid because repeated users, groups, and applications can appear in both training and testing.Temporal and cold-start settings reveal a more difficult generalization challenge.Source: A. What the Revised Results Show · p. 7
- CatBoost reaches R2 = 0.239 on the held-out temporal period, while normalized log-runtime entropy is 0.921.The entropy analysis contextualizes the modest temporal score but does not establish an irreducible error bound.Source: A. What the Revised Results Show · p. 7
B. Why CatBoost Helps
- CatBoost handles categorical variables natively using ordered statistics, avoiding the arbitrary order imposed by ordinal encoding.One-hot encoding creates high-dimensional sparse features, while target encoding requires care to avoid leakage.Source: B. Why CatBoost Helps · p. 7
- CatBoost benefits from combining identifiers, requested resources, and temporal features, unlike the earlier Random Forest one-hot ablation.The passage attributes this contrast to the ablation results.Source: B. Why CatBoost Helps · p. 7
C. Scheduling Implications
The discussion connects prediction quality to scheduler behavior while emphasizing the limits of the simplified evaluation. Long-job underestimation and workload scope remain important constraints, motivating fuller scheduling studies.
C. Scheduling Implications
- The minimal single-server simulation supports reduced waiting time versus FCFS, but does not substitute for a full scheduler-integrated evaluation.The next step is to evaluate SJF, EASY backfilling, conservative backfilling, and hybrid policies under realistic resource constraints.Source: C. Scheduling Implications · p. 7
D. Long-Job Underestimation
- Tuned CatBoost systematically underestimates very long and extreme jobs, which can increase reservation violations and delay other jobs.The discussion motivates asymmetric loss, quantile prediction, conformal intervals, and conservative estimates for backfilling.Source: D. Long-Job Underestimation · p. 7
VII. THREATS TO VALIDITY
- The study uses one grid trace with job-level runtime, and temporal validation does not eliminate distribution shift; entropy is not a formal error bound.The simulation also omits production scheduler features including resource fragmentation, priorities, reservations, and EASY backfilling.Source: §VII · pp. 7–8
VIII. FUTURE WORK
- Future work proposes full scheduling simulation across realistic policies and resource constraints, plus cross-trace evaluation and methods targeting long-job underestimation.Proposed methods include quantile regression, conformal prediction intervals, asymmetric losses, and online learning for user and executable histories.Source: §VIII · p. 8
IX. CONCLUSION
- The study finds that random splitting overestimates deployment performance, while tuned CatBoost improves temporal prediction and long-job underestimation remains a scheduling concern.A minimal simulation shows prediction-informed SJF can reduce average waiting time relative to FCFS, but full backfilling simulation remains future work.Source: §IX · p. 8