PaperlayerView exact revision on arXiv

Source-linked AI summary

Real-time Optimization of Simulation and Data Processing Pipelines for Experiments on Exascale Computing Platforms

Thomas Wester, Harikrishna Tummalapalli, Christine M. Simpson

arXiv:2610.02498v1cs.DC

TL;DR

Growing experimental data volumes and heterogeneous exascale systems make efficient workflow scheduling challenging. The paper develops theoretical and simulation tools and a two-stage dynamic strategy, then evaluates it on an SBND Monte Carlo workflow. The strategy improves makespan and worker occupancy, with an estimated node-hour reduction at the tested scale.

  • Problem

    Growing experimental data volumes and heterogeneous HPC systems challenge efficient pipeline scaling, while stochastic task durations undermine static scheduling.

    Source: §I · p. 1

  • Method

    The paper develops theoretical and simulation tools and uses early-stage runtime correlations to prioritize later pipeline stages dynamically.

    Source: §I · p. 1, §IV · p. 4, §VII · p. 7

  • Results

    The dynamic multi-stage strategy improves makespan and idle fraction versus unordered scheduling; at 2,048 nodes, estimated wasted node-hours fall from approximately 1,000 to hundreds.

    Source: §V · p. 6, §VII · p. 7

  • Takeaways & Limitations

    The validated simulator can help experimentalists explore workflow scheduling and deployment choices when task-runtime distributions can be measured.

    Source: §VII · p. 7

    The study validates and tests only CPUs; mixed CPU/GPU resource types remain for future work.

    Source: §VII · p. 7

Abstract

from arXiv · show

Current and next-generation large-scale experiments, especially in high-energy physics and cosmology, involve increasing volumes of data that require exascale computing power to analyze and model. Exascale machines present challenges for workflow scaling and efficient resource usage. We propose a multi-stage task scheduling approach for optimizing resource usage for these workflows. We demonstrate task scheduling for an example Monte Carlo simulation pipeline from the Short-Baseline Near Detector (SBND), and present theoretical and numerical tools for modeling task scheduling in these workflows that can be used to identify optimal scheduling strategies and choose resources for a given problem size.

I. INTRODUCTION

Experiments’ growing data volumes motivate exascale computing, but scaling pipelines to these systems challenges efficient resource use. The paper presents a two-stage dynamic scheduling strategy and modeling tools, applied to an HEP Monte Carlo workflow.

I. INTRODUCTION

  • Experiments will collect petabytes of raw data, while exascale systems pose challenges in porting and optimizing pipelines.Data-intensive analysis is identified as a key workload for national computing facilities.Source: §I · p. 1
  • Variable task durations from real data and Monte Carlo fluctuations make static scheduling perform poorly, a problem compounded by heterogeneous HPC systems.Particle counts can vary across detector events, changing the run time of pattern-recognition tasks.Source: §I · p. 1
  • The proposed two-stage strategy uses a short prediction stage to estimate a longer stage’s run time, aiming to improve utilization and reduce makespan.The paper also provides theoretical and numerical tools to estimate workflow performance for DAGs with random task durations.Source: §I · p. 1
  • The paper applies the approach to an HEP Monte Carlo simulation workflow and compares theory and simulation with a real neutrino-interaction workflow on HPC.The paper reports that agreement among the three approaches validates the two-stage dynamic policy’s reduction of makespan and improvement of worker occupancy.Source: §I · p. 1

II. SCHEDULING THEORY

The scheduling theory frames workflow performance through makespan and idle time, which can trade off as the number of workers changes. It considers random task durations and compares unknown, unordered runtimes with known, orderable runtimes.

II. SCHEDULING THEORY

  • A workflow has M tasks assigned to N workers through a shared queue, with makespan T and idle time I measuring job performance.Workers take the next queued task immediately when they finish, unless the queue is empty.Source: §II · pp. 1–2
  • Setting N = M minimizes T but can maximize I when task durations vary; setting N = 1 minimizes I but maximizes T.Users must choose an acceptable balance given task count and run-time variance.Source: §II · p. 2
  • The analysis models runtimes with distribution q(t), mean µ, and variance σ², comparing random assignment when runtimes are unknown with ordering when runtimes are known.It expresses makespan and idle time at the fraction p of completed work as T_p and I_p.Source: §II · p. 2

A. Unknown Run Times (Unordered)

For unknown runtimes, tasks are assigned randomly and the analysis separates execution into a fully occupied bulk phase and a draining phase. It estimates completion and idle time using the distribution of residual runtimes, under an assumption that is optimistic unless M ≫ N.

A. Unknown Run Times (Unordered)

  • The unordered schedule divides execution into a bulk phase, when the queue keeps all workers busy, and a draining phase after the final task leaves the queue.The draining phase begins at approximately (M − N)µ/N.Source: A. Unknown Run Times (Unordered) · p. 2
  • At queue drain, longer tasks are more likely to remain active, so the residual-runtime distribution weights task runtimes by their duration.The derivation assumes remaining runtimes are uniformly distributed with respect to the drain time; this is optimistic and holds only when M ≫ N.Source: A. Unknown Run Times (Unordered) · p. 2
  • The model derives T_p by counting completions across the bulk and draining phases, then expresses I_p using T_p and completed work.The number of draining-phase completions needed for fraction p is m_drain = pM − m_bulk.Source: A. Unknown Run Times (Unordered) · p. 2

B. Known Run Times (Ordered)

When runtimes are known, longest-first ordering places shorter tasks at the end of the queue, limiting the final task’s contribution to makespan. The analysis gives a bound and finds idle time decreases with larger task counts under the stated conditions, while emphasizing that its estimates are optimistic.

B. Known Run Times (Ordered)

  • For known runtimes, longest-first ordering is preferred because residual block duration is proportional to task durations near the end of the queue.The final task is assigned to the first available worker after the others and is the shortest task.Source: B. Known Run Times (Ordered) · p. 2
  • When M ≫ N, the worst-case makespan bound assumes the final task starts after all other tasks finish and extends completion by its runtime.If the longest-running task remains active when the final task is assigned, it could extend makespan instead, though this is atypical when M ≫ N.Source: B. Known Run Times (Ordered) · p. 2
  • For randomly distributed known runtimes under longest-first scheduling, idle time decreases as M increases, opposite to the unknown-runtime case.The idle-time expression scales only with the number of workers allocated during the block.Source: B. Known Run Times (Ordered) · p. 3
  • The scheduling expressions rely on idealized assumptions and are optimistic estimates, while runtime information allows more favorable reductions in makespan and idle time.Source: B. Known Run Times (Ordered) · p. 3

III. SCHEDULING SIMULATOR

The scheduling simulator estimates makespan and worker idle time when theoretical models rely on simplifying assumptions. It extends pipeline scheduling to general DAGs through task ordering, resource mapping, and discrete-event simulation.

III. SCHEDULING SIMULATOR

  • The simulator extends pipeline scheduling to general DAGs and numerically estimates makespan and worker idle time under simplifying assumptions.Its architecture is illustrated in Fig. 1.Source: §III · p. 3, Figure 1 · p. 3
  • WorkflowModel represents workflows as DAGs, while TaskOrderer prioritizes ready tasks and Mapper assigns them to the compute system.Built-in ordering policies include FIFO, shortest-first, and longest-first.Source: §III · p. 3
  • Compute nodes contain slots with compute-power parameters, and a network graph represents inter-node links with bandwidth parameters.The system model comprises ComputeNode and ComputeSlot components.Source: §III · p. 3
  • A discrete-event loop schedules ready tasks, advances time to the earliest completion, releases resources, and schedules newly ready successors until no events remain.Task completion times are calculated from task compute cost and allocated-slot power.Source: §III · p. 3
  • The simulator is used to validate against a production HPC workflow and study scheduling performance across node counts and task-duration variance.Source: §III · p. 3

IV. HIGH-ENERGY PHYSICS WORKFLOW

The study applies scheduling strategies to SBND's LARSOFT neutrino-simulation workflow, whose stages have variable runtimes. It uses correlations between early and later stage runtimes to reprioritize downstream work; the dynamic multi-stage timeline shows later-starting stages with shorter median runtimes.

IV. HIGH-ENERGY PHYSICS WORKFLOW

  • The compared strategies either run each pipeline sequentially on one worker or split it into generator and downstream task groups, potentially on different workers.The dynamic strategy prioritizes generators first and updates downstream priority according to generator run length.Source: Figure 2 · p. 4, §IV · p. 5
  • The SBND LARSOFT workflow chains GENIE event generation, GEANT4 particle propagation, WIRECELL detector-readout simulation, and PANDORA reconstruction.The study tests the workflow on Aurora using CPUs; GPUs were not used.Source: §IV · pp. 4–5
  • Early and later stage runtimes are strongly correlated, allowing downstream tasks to be reprioritized as generator stages finish and longer estimated tasks to be favored.The paper illustrates task-time distributions and correlation for 100,000 independent pipelines.Source: §IV · p. 4, Figure 3 · p. 4
  • Later-starting dynamic multi-stage tasks have shorter median stage runtimes, characteristic of longest-first scheduling.Fig. 4 compares worker occupancy and task runtimes for unordered single-stage and dynamic multi-stage scheduling on Aurora.Source: Figure 4 · p. 5, §IV · p. 5

V. RESULTS

In the SBND workflow, dynamic multi-stage scheduling outperformed unordered single-stage scheduling on makespan and idle fraction. The empirical and simulator results followed the theoretical trends, with the theoretical makespan estimates optimistic under the study’s assumptions.

V. RESULTS

  • Theory, simulator, and empirical cases were compared using expected makespans Tp and idle fractions ϕp.The theoretical values use the empirical task run-time distribution and are expected to underestimate Tp.Source: §V · pp. 5–6, Table I · p. 6
  • Dynamic multi-stage scheduling produced smaller makespan Tp and idle fraction ϕp than unordered single-stage scheduling.The comparison is shown in Fig. 5 and was attributed to using predicted run-time distributions to order second-stage tasks.Source: §V · p. 6, Figure 5 · p. 6
  • The measurements of ϕ99.99 and T99.99 cover approximately 10 tasks and therefore have large statistical variance.Source: §V · p. 6
  • Empirical and simulator occupancies had slopes similar to theoretical predictions, while their makespan lag reflected optimistic simplifying assumptions.The queue-empty task-uniformity assumption holds only for M/N ≫ 1; the empirical case used M/N = 4.Source: §V · p. 6

VI. PIPELINE SIMULATIONS: PROPERTIES AND SCALING

The scheduling simulator was used to explore SBND workflow scaling and task-duration variance using generated task times. Dynamic multi-stage scheduling showed less sensitivity to run-time variance than unordered single-stage scheduling, while strong scaling indicated a node-count trade-off between makespan and occupancy.

VI. PIPELINE SIMULATIONS: PROPERTIES AND SCALING

  • The simulator tested workflow variations in node count and run-time variance using generated task times based on the SBND case study.Task times were generated from measured means and variances; for the dynamic multi-stage case, independently generated stage times were sorted and paired to match empirical telemetry.Source: §VI · pp. 6–7
  • As node count increased, worker occupancy dropped while makespan flattened, indicating an optimal node count for minimizing makespan with minimal occupancy loss.The strong-scaling simulations held the pipeline count fixed at 104,448 and assumed 102 workers per node.Source: §VI · p. 7, Figure 6 · p. 7
  • The study used three dynamic multi-stage variance variants: both stages varied, only stage 2 varied, or only stage 1 varied.The unordered single-stage comparison held its task mean at twice the mean run time of a single stage and steadily increased σ.Source: §VI · p. 7
  • Dynamic multi-stage scheduling was far less sensitive to task run-time variance than unordered single-stage scheduling.Increasing both stage variances together gave the worst results and eventually converged to the unordered case; varying only one stage retained better performance, although downstream-stage variance was less favorable.Source: §VI · p. 7

VII. CONCLUSIONS

High task-time variance can increase idle worker time and makespan, while dynamic multi-stage scheduling can reduce wasted node-hours. The study validates its scheduling policy with theoretical and simulator-based tools and a production SBND workflow.

VII. CONCLUSIONS

  • Fig. 7 explores three two-stage cases with 10-minute mean tasks per stage and an unordered single-stage case with 20-minute mean tasks as task-time variability changes.The caption describes the tested distributions but does not state which case performs best.Source: Figure 7 · p. 7
  • Approximately 15% idle node compute time would waste approximately 1,000 node-hours at 2,048 nodes, whereas dynamic multi-stage scheduling could reduce that waste to hundreds of node-hours.The estimate is for the tested HEP pipeline if workload grows relative to node count to keep makespan fixed.Source: §VII · p. 7
  • The scheduling policy uses correlations between pipeline stages to inform task priority, and was validated with theory, simulation, and a production SBND Monte Carlo workflow.The conclusion describes this policy as optimizing task submission.Source: §VII · p. 7
  • The extensible simulator models workflow DAGs with deterministic or stochastic task durations and can guide deployment when task run-time distributions are measurable.It was validated against real Aurora runs at ALCF.Source: §VII · p. 7
  • The study did not evaluate PARSL launcher efficiency and tested only CPUs; mixed CPU/GPU resource types are left for future work.The conclusion notes that faster per-task GPU performance does not necessarily improve workflow makespan in some circumstances, in part because GPUs are less numerous on compute nodes.Source: §VII · pp. 7–8
Loading 2610.02498v1…