PaperlayerView exact revision on arXiv

Source-linked AI summary

BOOSTEDSOSA: Accelerated Inferencing for Low Variance Stochastic Online Scheduling

Adam H. Ross, Riccardo Revalor, Aryan Singh, Ayush Jain, Debjit Pal

arXiv:2608.25346v1cs.AR

TL;DR

Heterogeneous stochastic HPC scheduling is limited by variable user runtime estimates, which weaken scheduling guarantees as prediction variance increases. BOOSTEDSOSA combines submission-time XGBoost prediction, temporal-aware additive training, and dual-FPGA inference and scheduling. It reports lower prediction error and faster end-to-end scheduling, with memory use and workload-model scope remaining limitations.

  • Problem

    User-provided runtime estimates introduce substantial variance into stochastic scheduling, weakening competitive-ratio guarantees as prediction variability increases.

  • Method

    BOOSTEDSOSA uses submission-time XGBoost predictions with an additive temporal training policy and separate inference and scheduling FPGAs.

  • Results

    BOOSTEDSOSA achieves an average 17× speedup over the AVX baseline, while XGBoost outperforms Random Forest across all ten MIT SuperCloud shifts and nine Blue Waters shifts.

  • Takeaways & Limitations

    The architecture replaces human runtime estimates with real-time hardware-accelerated predictions while adapting to temporal workload shifts.

  • Takeaways & Limitations

    The method uses six submission-time features, increases peak host memory by about 7×, and has not been evaluated with additional ML predictors.

Abstract

from arXiv · show

Heterogeneous scheduling in stochastic, online envi- ronments, such as high-performance computing (HPC) systems, presents a significant challenge. Stochastic Online Scheduling Accelerators (SOSAs) offer a promising solution, but their effectiveness is compromised by a reliance on runtime estimates provided by users. These estimates introduce substantial vari- ance into the scheduling process (mean MAE in hundreds of Core-Days), thereby weakening the competitiveness of Stochastic Online Scheduling algorithms as their competitive-ratio bound increases with runtime variability. To address this limitation, we introduce BOOSTEDSOSA, a dual-FPGA ML-assisted Scheduling architecture that integrates a Machine Learning predictor for expected processing times, with a novel temporal-aware training policy. The predictor estimates job runtimes using only scheduler parameters available at submission time, enabling its use in existing HPC systems. Using historical real-world HPC job data (from the Argonne Leadership Comput- ing Facility, MIT Supercloud and UIUC Blue Waters workload datasets), we show that the predictor reduces MAE by up to 63.85% compared to user runtime estimates, and the additive training policy reduces MAE by up to 71.88% compared to a static model. End-to-end, BOOSTEDSOSA achieves an average 17x speedup over an AVX-optimized software baseline and processes up to 1,711 jobs/seconds

I. INTRODUCTION

HPC scheduling must handle unpredictable arrivals, variable execution times, and resource contention, while SOSAs depend critically on accurate expected processing times. BOOSTEDSOSA addresses runtime-estimate variability with submission-time ML prediction, temporal adaptation, and separate inference and scheduling FPGAs.

  • HPC scheduling is challenging because job arrivals, execution times, and resource availability are unpredictable, creating a multidimensional decision space.
  • Accurate expected processing times are essential because SOSAs use them to calculate assignment costs and determine execution priority.
  • User-provided estimates and historical averages introduce substantial variance between expected and real processing times, leading to suboptimal scheduling.
  • BOOSTEDSOSA predicts each incoming job’s expected processing time on an Inference FPGA before scheduling it on a separate Scheduling FPGA.
  • The architecture keeps prediction and scheduling independent, allowing either component to be replaced without redesigning the other.
  • BOOSTEDSOSA adapts predictions to workload changes over time through an additive training policy.

A. Stochastic Scheduling Abstractions

Stochastic online scheduling maps streaming jobs to heterogeneous machines without knowing future workloads or exact execution times. It uses expected processing times to prioritize jobs, while prediction variance directly affects scheduling guarantees.

  • SOS dynamically maps streaming jobs to heterogeneous resources while minimizing weighted expected processing time under uncertainty.
  • A job is represented by weight, machine-specific expected processing times, program type, and a unique identifier.
  • EPT is a predictive estimate available before execution, whereas RPT is the realized processing time observed after execution.
  • Virtual schedules continuously order uncommitted jobs by their relative weighted-shortest-processing-time ratios and can be adjusted online.
  • SOS competitive-ratio bounds depend on the squared coefficient of variation between real and expected processing times.
  • Temporal-aware training is motivated because prediction error that grows as workloads drift produces larger variability and weaker guarantees.

B. STANNIC FPGA-Assisted Scheduler

STANNIC uses systolic hardware to maintain virtual schedules and perform low-latency scheduling on heterogeneous machines. BOOSTEDSOSA pairs this scheduler with gradient-boosted inference whose additive structure supports FPGA acceleration and temporal warm starts.

  • STANNIC maintains a WSPT-ordered virtual schedule for each machine using a one-dimensional systolic array of processing elements.
  • Processing elements compare stored jobs with an incoming job to identify the boundary between high- and low-priority sets.
  • Boundary processing elements return scheduling costs through a parallel O(1) lookup instead of O(N).
  • XGBoost predicts runtime by summing outputs from sequentially trained decision trees over each job’s feature vector.
  • The summed leaf weights support spatial FPGA acceleration through adder-tree cascades.
  • XGBoost’s iterative training supports warm-start partial training for adapting predictors to temporal HPC workload conditions.

III. ML TECHNIQUE FOR EPT PREDICTION

The ML technique prepares HPC data and features for submission-time EPT prediction under FPGA numerical constraints. It sanitizes historical traces, prevents temporal leakage, and translates mixed feature types into fixed-width representations.

  • The ML strategy covers EPT prediction, software-to-hardware data translation, and the hardware components needed for scheduling.
  • Historical HPC data is sanitized to exclude faulty records that could skew predicted runtimes.
  • Zero-runtime records associated with failures, crashes, or cancellations are filtered to avoid biasing predictions toward artificially short runtimes.
  • EPT prediction must use information available at job submission time without temporal data leakage from post-submission system state.
  • XGBoost supports numerical and categorical scheduler features, but FPGA inference requires fixed-width numerical types.
  • Fixed-point representation requires balancing integer range against fractional precision to avoid overflow, quantization, and truncation errors.

C. Data Normalization and Target Formulation

BOOSTEDSOSA combines runtime-target formulation with XGBoost and a temporal-aware Core + Additive training policy. The policy preserves a frozen baseline while adding capacity to track workload changes under FPGA constraints.

  • C. Data Normalization and Target Formulation: XGBoost predictions are converted from core-hours to wall-clock days by dividing consumed core-hours by 24 × requested cores.Wall-clock days are numerically smaller and safer for fixed-point hardware than raw core-hours.
  • 1) Additive Training: Recently completed jobs provide feedback for updating predictions because HPC workloads are non-stationary and static models can degrade under changing runtime distributions.The update process uses newly observed ground-truth execution values.
  • 1) Additive Training: Additive training appends new decision trees to an existing XGBoost ensemble, correcting errors without discarding previously learned patterns or fully retraining.The policy is also evaluated with Random Forest to test whether adaptation extends beyond XGBoost.
  • 1) Additive Training: Figure 1 depicts how training data are allocated to trees across the additive-training process.The figure summarizes the data-to-tree allocation design.
  • 2) Bifurcated Core + Additive Policy: The bifurcated policy splits a bounded tree budget between a pre-deployment CORE model and an additive phase constrained by inference-hardware capacity.Historical workload data are divided into two halves for the initial model and subsequent updates.
  • 2) Bifurcated Core + Additive Policy: Sensitivity analysis sweeps six CORE/additive tree-budget allocations, including CORE-only and Additive-only configurations, under increasing synthetic temporal drift.The evaluation uses the datasets described for the experimental setup.
  • 2) Bifurcated Core + Additive Policy: The adopted 50/50 split preserves a substantial frozen baseline while reserving sufficient capacity to track distributional shifts.It is presented as a balance between under- and over-committing to either component.

3) XGBoost Rationale:

The evaluation tests XGBoost and additive training under temporal drift, then places the predictor within a dual-FPGA architecture. Results support workload-calibrated additive updates rather than a universal bucket setting.

  • 3) XGBoost Rationale: 45,000 jobs is the optimal ALCF additive bucket size, with ADD consistently outperforming CORE across all tested drift severities.Figure 3 reports mean MAE with shaded ±1 standard-deviation bands.
  • 3) XGBoost Rationale: Under σ = 0.25 drift, CORE reaches approximately 285 MAE while the 45K additive model reaches approximately 255.The comparison is reported for the ALCF workload.
  • 3) XGBoost Rationale: Additive accuracy converges toward the baseline for bucket sizes above 60,000 because bucket-specific distributions can be overcorrected.The additive model remains stable under severe drift.
  • 3) XGBoost Rationale: A 45K bucket is an ALCF-specific calibration, and new deployments can initialize CORE and bucket estimates from target-system or representative historical traces.Completed-job wall-clock observations can refine the configuration after deployment.
  • 3) XGBoost Rationale: BOOSTEDSOSA separates inference and scheduling across two FPGAs, while the host handles preprocessing and model training.The architecture uses a Conifer FPU-based Inference FPGA and a systolic-array Scheduling FPGA.
  • 3) XGBoost Rationale: Asynchronous host threads parallelize communication, scheduling control, and model maintenance to hide PCIe latency and reduce host-side bottlenecks.Five threads are identified for orchestration and maintenance.
  • 3) XGBoost Rationale: Figure 5 traces conversion of the trained XGBoost model into an FPGA kernel bitstream and model-weight payload through Conifer.The diagram distinguishes movement between the Python model, translator, host code, and FPU kernel.

1) Host Side Job Orchestration:

The host orchestrates job identifiers, feature preparation, model maintenance, and communication with the FPGA modules. Model compilation separates reusable inference architecture from runtime-loaded tree data.

  • 1) Host Side Job Orchestration: The Writer assigns each submitted job a unique quantized ID supplied by the Job ID Manager.The Job ID Manager translates between software-cluster identifiers and accelerator identifiers.
  • 1) Host Side Job Orchestration: The Trainer updates the XGBoost model, after which Conifer generates an inference kernel bitstream and a Model Nodes Binary.The compilation uses FPU configuration parameters including tree engines, nodes per engine, feature width, and fixed-point precision.
  • 1) Host Side Job Orchestration: The synthesized HLS kernel encodes tree traversal, fixed-point arithmetic, and pipeline structure, while the Model Nodes Binary stores tree feature indices, thresholds, and leaf scores.Vitis compiles the kernel for the Inference FPGA, and the binary is loaded at runtime.
  • 1) Host Side Job Orchestration: For each incoming job, the host creates a feature batch excluding Machine ID and sends it to the Inference FPGA.This forms the host-to-inference stage of the prediction pipeline.
  • 1) Host Side Job Orchestration: The Inference FPGA’s FPU uses a synthesized Conifer architecture, while individual tree weights are loaded separately into on-chip memory.The FPU populates 128 independent tree-engine units, one per ensemble tree.
  • 1) Host Side Job Orchestration: The Scheduling FPGA hosts STANNIC with Reader and Writer modules for receiving prediction packets and returning scheduling decisions.STANNIC is integrated as a largely unmodified black-box scheduling engine.
  • 1) Host Side Job Orchestration: STANNIC receives packets from Host RAM through PCIe, computes assignments, and streams results back to the host for checkout and dispatch.The host Reader thread handles the returned scheduling result.

2) Scheduling FPGA Data Flow:

The scheduling data path bridges high-precision inference output to lightweight integer scheduling input and supports continuous streaming. Evaluation spans diverse HPC workloads using MAE and multiple baselines.

  • 2) Scheduling FPGA Data Flow: BOOSTEDSOSA addresses the precision mismatch between the FPU output and STANNIC input by maximizing precision within STANNIC’s lightweight integer constraints.The design treats precision preservation and hardware-resource limits as a joint interface problem.
  • 2) Scheduling FPGA Data Flow: The Zipper multiplies predicted EPT days by 96 and casts the result to uint16_t, producing EPT blocks of floor(EPT days × 96).The factor 96 represents 24 hours × 4 fifteen-minute blocks per hour.
  • 2) Scheduling FPGA Data Flow: The architecture replaces batch loading with continuous streaming through PCIe shared memory, FIFO-connected Reader and Writer modules, and non-blocking reads.This decouples scheduler operation from job arrivals and supports asynchronous dispatch.
  • 2) Scheduling FPGA Data Flow: Evaluation uses ALCF data for primary training and testing, with MIT Supercloud and UIUC Blue Waters datasets testing generalization across independent HPC environments.The environments differ in schedulers, hardware configurations, and workload distributions.
  • 2) Scheduling FPGA Data Flow: NODE_TYPE identifies machines for ALCF, processor types for MIT Supercloud, and compute-node types for UIUC Blue Waters.The field’s operational meaning differs across datasets.
  • 2) Scheduling FPGA Data Flow: The implementation uses one host CPU and two PCIe-connected Alveo U55C FPGAs, assigned to inference and scheduling.The host system has 16 CPU cores, 32 threads, and 512 GB RAM.
  • 2) Scheduling FPGA Data Flow: The software-only baseline runs XGBoost inference and SOS scheduling on the host CPU with Intel AVX for SIMD parallelism.This isolates the performance contribution of BOOSTEDSOSA’s hardware acceleration.
  • 2) Scheduling FPGA Data Flow: Table I reports additive bucket sizes, raw and retained job counts, and wall-time mean, median, 75th-percentile, and 95th-percentile distributions.Bucket Size denotes jobs used for additive updates; Raw Jobs precedes preprocessing and Retained Jobs follows it.

VI. EXPERIMENTAL RESULTS

Experiments across three HPC workload datasets show that tree-based ML predictors provide more accurate, lower-variance runtime estimates than human estimates, historical averages, and linear regression. ADD is evaluated under workload shifts using MAE and MAE p95.

  • 1,295 Core-Days and 2,376.36 Core-Days are the mean MAE of human estimates on ALCF and MIT Supercloud, respectively.Human estimates also show extreme variance, reaching 1,368 on ALCF.
  • 2.02×, 1.71×, and 2.27× higher MAE than the best ML predictor occur for historical averages on ALCF, MIT Supercloud, and UIUC Blue Waters.
  • 2.82×, 2.01×, and 2.17× higher MAE than the best ML predictor occur for linear regression on ALCF, MIT Supercloud, and UIUC Blue Waters.
  • 1.77 Core-Days is XGBoost’s MAE on MIT Supercloud, while Random Forest achieves the lowest MAE on ALCF and UIUC Blue Waters.Tree-based models reduce both absolute prediction error and variance across cross-validation folds.
  • ADD and CORE are compared using mean MAE and MAE p95 under Gaussian temporal shifts in used Core-Days across all three datasets.Lower MAE and MAE p95 indicate better performance.

B. Effectiveness of Additive Scheduling Policy

ADD is assessed against CORE under synthetic distribution shifts, chronological workload drift, and realistic scheduling arrival rates. It generally improves prediction accuracy, especially under substantial shifts, while streaming I/O avoids the latency imposed by batch filling.

  • Effectiveness of Additive Scheduling Policy: 12.0% mean and 2.7% median MAE reductions occur for ADD on MIT Supercloud in 5 of 10 settings.In the two central settings, CORE is 4.4% more accurate on average; the MIT result has p = 0.275.
  • Real Chronological Workload-Drift Validation: 222 Core-Days versus roughly 460 for CORE and 539 for RECENT-ONLY is ADD’s approximate ALCF MAE by chronological Window 9.ADD consistently matches or outperforms CORE from Window 5 onward, with p = 0.05 for the CORE/ADD gap.
  • Real Chronological Workload-Drift Validation: 10.4× and 9.2× increases in median Blue Waters job wall-time accompany Windows 7–8 distribution shifts, while MIT Supercloud median wall-time decreases 40.3%.Under abrupt shifts, ADD can temporarily overcorrect because recent trees retain residual corrections from the preceding workload distribution.
  • Cost of Batch I/O Under Realistic Arrival Rates: 245.0 ms at 10^2 jobs/s versus 2.4 ms at 10^4 jobs/s is the batch-path latency change, while streaming remains below 4 µs.Batch waiting constitutes 99.8% of total latency at the lowest rate; the paths are statistically indistinguishable only when all jobs are available at t = 0.

E. Comparison of End-to-End Performance

BOOSTEDSOSA substantially reduces end-to-end scheduling time and increases throughput compared with an AVX-optimized software baseline, while using more host memory. Its split FPGA design also preserves modularity and supports scalability toward larger machine counts.

  • End-to-End Performance: 17× average speedup: BOOSTEDSOSA processes 45K-job workloads in about 26.3 seconds versus 445.63–451.91 seconds for the AVX baseline.The comparison uses a random 45K-job sample from the ALCF dataset across job depths of 10–40.
  • End-to-End Performance: 1,701.54–1,711.74 jobs/sec: BOOSTEDSOSA consistently exceeds the AVX baseline’s 99.65–100.98 jobs/sec throughput.The PCIe streaming integration adds small communication overhead rather than explaining the speedup.
  • End-to-End Performance: 0.28%–0.49% CV: BOOSTEDSOSA is more stable across job depths than the AVX baseline, whose CV ranges from 0.39% to 2.79%.Mean total time varies by 0.6% for BOOSTEDSOSA and 1.4% for AVX across evaluated depths.
  • Resource Trade-offs: 7× higher peak host memory: BOOSTEDSOSA reaches about 253 MB RSS compared with approximately 35 MB for the AVX baseline.The increase is attributed to asynchronous PCIe streams, FPGA management, and multithreaded host orchestration.
  • Resource Trade-offs: At most 4% of LUTs on inference and 2% on scheduling: the FPGA modules occupy a modest fraction of available resources.Both boards operate at 371.47 MHz, and DSP slices are unused across the reported modules.
  • Architecture and Scalability: A single FPGA could in principle host a condensed design, but the split organization preserves scheduling resources and modularity for scaling.Separating scheduling from inference avoids resource contention as STANNIC scales toward larger machine counts.

G. ML Predictor Ablation with Random Forest

Random Forest preserves the temporal adaptation benefits of ADD, although XGBoost is generally more robust under pronounced workload shifts. The ablation therefore supports predictor flexibility while identifying differences in adaptation behavior.

  • Predictor Comparison: All 12 pronounced-shift dataset pairs favor XGBoost over Random Forest on ADD MAE.Random Forest performs better only under six milder ALCF shifts, while XGBoost wins all ten MIT SuperCloud and nine Blue Waters shifts.
  • Chronological Validation: Replacing XGBoost with Random Forest preserves ADD’s chronological improvement over CORE and removes temporary losses on MIT SuperCloud and Blue Waters.On ALCF, ADD remains below CORE from Window 5 and reaches 150 Core-Days at Window 9.
  • Chronological Validation: Random Forest makes RECENT-ONLY achieve the lowest MAE in some later windows, including Window 9 on ALCF and Blue Waters.This is attributed to all RECENT-ONLY trees reflecting the current workload under sufficiently large changes.
  • Predictor Comparison: XGBoost is more robust to pronounced temporal shifts, while ADD adapts to both XGBoost and Random Forest predictors.Table VI defines positive relative MAE differences as favoring XGBoost.
  • Chronological Validation: ADD generally preserves or improves upon CORE across ten sequential workload windows on all three datasets with Random Forest.The chronological validation indicates that ADD is not specific to XGBoost.

VIII. LIMITATIONS

The paper identifies limitations involving host-memory overhead, restricted submission-time features, limited predictor coverage, and incomplete representation of HPC workloads and prediction errors. It also notes that quantization assumptions may change over a system’s lifetime.

  • Limitations: About 7× higher peak host memory: asynchronous PCIe streams and multithreaded orchestration increase BOOSTEDSOSA’s memory use relative to AVX.The reported peak RSS is approximately 253 MB versus 35 MB for the baseline.
  • Limitations: Six submission-time features may miss deeper application-specific runtime patterns because post-submission telemetry is excluded to prevent temporal leakage.The limitation concerns the feature scope of the XGBoost predictor.
  • Limitations: Temporal adaptation is evaluated with XGBoost and Random Forest, while additional ML predictors remain future work.The paper does not claim coverage of all possible predictor families.
  • External Threats: The evaluation cannot cover all HPC architectures and workloads, so additional dataset evaluations would strengthen the claims.The study mitigates this boundary with varied historical datasets and chronological and synthetic distribution shifts.
  • Internal Threats: Historical 99.9th-percentile quantization values are not guaranteed to remain constant throughout a real system’s lifecycle.The modular design permits recalculating quantization values when needed.
  • Construct Threats: Gaussian perturbations and chronological windows represent only subsets of possible HPC workload shifts, while MAE and MAE p95 may omit other scheduling-relevant errors.These limitations constrain the workload-shift and prediction-error constructs used in evaluation.
Loading 2608.25346v1…