Source-linked AI summary
Hard and Soft Real-Time DNN Inference Scheduling on Heterogeneous Multi-Accelerator Systems via Reinforcement Learning
Francesco Giulio Blanco, Enrico Russo, Giuseppe Ascia, Davide Patti, Maurizio Palesi
TL;DR
Mixed real-time DNN inference scheduling must accommodate dynamic soft-real-time requests while meeting hard deadlines on heterogeneous accelerators. The paper combines an online RL scheduler with deterministic runtime certification and a schedulability-preserving prefix-replacement criterion. Experiments report preserved HRT schedulability alongside improved QoS-aware outcomes and accelerator utilization versus state-of-the-art approaches.
Problem
Heterogeneous DNN systems must schedule precedence-constrained mixed workloads with dynamic SRT requests while ensuring HRT deadlines, but adaptive online schedulers generally lack strict HRT guarantees.
Source: §1 · pp. 1–2Method
An online RL scheduler jointly chooses accelerator assignments and execution priorities, while deterministic runtime certification validates candidate prefixes using a schedulability-preserving replacement criterion.
Source: §1 · p. 2Results
The framework preserves HRT schedulability while improving SRT deadline satisfaction, client-level QoS, and accelerator utilization compared with state-of-the-art approaches.
Source: §1 · p. 2, §8 · p. 26Takeaways & Limitations
The framework's reported evaluation supports combining QoS-aware online optimization with a deterministic layer that enforces HRT correctness independently of the learned policy.
Source: §1 · p. 2, §8 · p. 26The reference schedule and runtime certification do not rely on locality-based reuse, while HRT execution bounds conservatively account for activation write-back and read costs.
Source: §2.1 · p. 4
Abstract
from arXiv · showhide
We present a scheduling framework for heterogeneous multi-accelerator systems executing both hard real-time and soft real-time QoS-aware DNN inference workloads. The framework combines an online reinforcement learning (RL) scheduler with a deterministic runtime safety layer. The RL scheduler dynamically generates candidate schedules by jointly selecting sub-job priorities and accelerator assignments, while runtime certification guarantees that all HRT deadlines remain satisfied independently of the learned policy. To enable runtime certification in heterogeneous precedence-constrained systems, we introduce a schedulability-preserving prefix replacement criterion based on machine-wise cuts. The proposed criterion guarantees that runtime-generated schedule prefixes preserve the existence of a feasible continuation without requiring complete finish-time dominance with respect to a feasible reference schedule. Experimental results on heterogeneous DNN accelerator platforms show that the proposed framework preserves HRT schedulability while improving QoS-aware deadline satisfaction, client-level service quality, and accelerator utilization compared to state-of-the-art scheduling approaches.
1 Introduction
Mixed hard- and soft-real-time DNN inference on heterogeneous multi-accelerator systems requires adaptive scheduling alongside reliable hard-deadline guarantees. This framework pairs an online RL scheduler with deterministic runtime certification and evaluates it against state-of-the-art approaches.
1 Introduction
- Mixed HRT and SRT DNN inference is challenging because precedence-constrained execution, heterogeneous accelerators, dynamic SRT arrivals, and worst-case HRT deadlines interact.The paper motivates the setting with safety-critical applications including autonomous vehicles, robotics, and industrial automation.Source: §1 · pp. 1–2
- An RL scheduler jointly selects accelerator assignments and execution priorities, while a deterministic safety layer validates candidate schedule prefixes before execution.HRT correctness is guaranteed independently of the learned policy.Source: §1 · p. 2
- A machine-wise-cut prefix-replacement criterion preserves the existence of a feasible continuation without requiring complete finish-time dominance over a feasible reference schedule.The criterion supports runtime certification for heterogeneous precedence-constrained schedules.Source: §1 · p. 2
- The framework preserves HRT schedulability while improving SRT deadline satisfaction, client-level QoS, and accelerator utilization compared with state-of-the-art approaches.The evaluation uses heterogeneous DNN accelerator platforms.Source: §1 · pp. 2–3
2 System and Scheduling Model
The model schedules periodic hard real-time (HRT) DAG tasks alongside online soft real-time (SRT) DAG requests on heterogeneous processors. It prioritizes HRT deadlines, then seeks better SRT responsiveness, client-level service, and accelerator utilization.
2.1 Platform and DAG Job Model
- Processors are heterogeneous, and DAG jobs comprise sequential sub-jobs linked by precedence constraints, with execution WCET depending on the assigned eligible processor.HRT execution-time bounds include conservative activation write-back and read costs; runtime scheduling may exploit locality, but the HRT reference schedule and certification do not rely on reuse.Source: §2.1 · pp. 3–4
2.2 Hard and Soft Real-Time Workloads
- HRT workloads are periodic constrained-deadline DAG tasks whose generated jobs must all meet their deadlines, whereas SRT DAG jobs arrive aperiodically and may miss soft deadlines without compromising correctness.SRT jobs can be delayed, canceled, or rejected to preserve HRT guarantees.Source: §2.2 · p. 4
2.3 Client-Level QoS and Fairness
- An average system-level SRT hit ratio can conceal severe client-level QoS degradation, motivating client-specific SLO achievement rates and targets.The paper notes that averages offer no guarantees.Source: §2.3 · p. 5
2.4 Scheduling Model and Objective
- Scheduling couples processor allocation with execution priority, with dynamic sub-job priorities and nonpreemptive HRT execution; interrupted SRT work is canceled rather than resumed.Valid schedules must respect eligibility, processor exclusivity, nonparallel execution, and precedence.Source: §2.4 · pp. 5–6
- The objective is lexicographic: meet every admitted HRT deadline under admissible runtime executions, then improve SRT responsiveness, deadline-hit ratios, client SLO satisfaction, and accelerator utilization.Source: §2.4 · p. 6
3 Framework Overview
The framework separates online performance optimization from HRT safety: an adaptive scheduler proposes joint HRT/SRT schedules, while deterministic runtime certification governs whether they execute. A feasible HRT reference schedule supports admission control and fallback.
3 Framework Overview
- The framework combines adaptive online scheduling with strict HRT guarantees by enforcing correctness independently of the policy optimizing runtime performance.Although the described scheduler uses reinforcement learning, the safety envelope can enclose any online policy that generates candidate schedules.Source: §3 · p. 6
3.1 Reference Schedule and Admission Control
- Admission control accepts a new HRT task only when a feasible HRT-only WCET reference schedule can be constructed with the admitted tasks.The reference schedule is built offline and can be constructed using any method.Source: §3.1 · pp. 6–7
3.2 Runtime Scheduling
- At each activation, the runtime scheduler observes system state and generates a bounded-interval schedule prefix, jointly choosing sub-job priorities and accelerator assignments.Allocation and priority decisions are coupled because execution time depends on the selected accelerator.Source: §3.2 · p. 7
3.3 Runtime Safety Certification
- Every runtime candidate must pass a bounded-time certification test; otherwise, execution falls back to the corresponding HRT reference portion, preserving the deterministic safety envelope.Unsafe online decisions may reduce performance but cannot compromise HRT correctness.Source: §3.3 · p. 8
4 Runtime Safety Certification
The certification method adapts transfer schedulability to heterogeneous, precedence-constrained scheduling using machine-wise cuts rather than a scalar slack test. Its safe-prefix criterion preserves a feasible continuation when four conditions hold.
4.1 From Transfer Schedulability to Prefix Certification
- Classical scalar slack tests do not suffice for heterogeneous DAG scheduling because feasibility jointly depends on machine assignment, nonpreemptive execution, precedence, and contention across unrelated accelerators.Even total remaining work within aggregate processor capacity does not ensure jobs can be packed feasibly; the paper therefore uses a bounded-time sufficient test.Source: §4.1 · p. 9
4.2 Schedulability-Preserving Prefix Replacement
- A machine-wise cut is a vector of local machine times, and its induced prefix contains HRT sub-jobs completed by each assigned machine's local cut time.A clean cut has no HRT sub-job crossing it; the criterion uses these cuts to compare candidate and reference schedule prefixes.Source: §4.2 · pp. 9–10
- A safe candidate prefix can replace the corresponding reference prefix without losing HRT schedulability, provided the cut is clean and the four Definition 6 conditions hold.The conditions cover prefix validity, completed terminal jobs meeting deadlines, coverage of completed reference-prefix work, and no delay to reference-suffix releases.Source: §4.2 · pp. 10–11
5 Online Scheduler
The online scheduler periodically proposes candidate prefixes, but a deterministic runtime layer certifies them before execution to protect HRT schedulability. Its DDPG policy jointly selects sub-job priorities and accelerator assignments to optimize SRT service and accelerator use.
5 Online Scheduler
- The periodic scheduler proposes prefixes for available HRT and SRT sub-jobs, but every proposal is validated before execution; rejected proposals fall back to the certified HRT reference schedule.The scheduler is not trusted for HRT correctness; the framework uses RL to improve SRT QoS and accelerator utilization within the deterministic safety envelope.Source: §5 · p. 12
5.1 Runtime HRT Certification
- Certification accepts a candidate only when it meets the machine-wise cut conditions; otherwise, execution falls back to the certified reference prefix, preserving a feasible HRT continuation.On fallback, SRT work in the rejected prefix is discarded, and reserved HRT slots are not shortened when jobs finish early.Source: §5.1 · pp. 13–14
5.2 Background on Reinforcement Learning
- DDPG uses actor–critic networks during training, but after training the actor alone serves as the scheduling policy.The critic estimates action utility, while DDPG supports continuous action spaces for jointly encoding scheduling priorities and accelerator selection.Source: §5.2 · p. 14
5.3 RL-based Scheduler Policy
- The policy observes ready sub-jobs and accelerator occupancy, while its reward prioritizes deadline satisfaction and then balances client QoS and accelerator utilization.HRT deadline misses receive a strong penalty during training, but HRT correctness at deployment is enforced by runtime certification rather than the learned policy.Source: §5.3 · pp. 15–17
- DDPG encodes each ready sub-job with temporal and accelerator priorities, then decodes these continuous outputs into dispatch decisions.Continuous priorities avoid the rapidly growing combinatorial action space of directly representing joint sub-job ordering and accelerator assignment as discrete actions.Source: §5.3 · pp. 15–16
6 Experimental Results
The evaluation compares online schedulers on a heterogeneous six-accelerator DNN platform under moderate- and high-pressure SRT workloads, with HRT schedulability preserved through a common safety envelope. The proposed scheduler maintains stronger SRT and client-level service under high pressure, while the experiments also examine fallback, ablations, and scheduling-period effects.
6.1 Experimental Setup
- The evaluation uses six accelerators spanning row-stationary and weight-stationary dataflows and small and large sizes, with AlexNet, InceptionV3, ResNet50, and YOLO-v2 workloads.SRT arrivals are generated from a heavy-tailed Pareto process at mean inter-arrival times of 40 ms and 10 ms.Source: §6.1 · pp. 17–18
6.2 Baselines
- The baselines include online DNN schedulers, slack-based real-time methods, and dispatch heuristics; methods lacking native HRT guarantees are evaluated with the same safety envelope.This common envelope is also used to evaluate certified variants of the baselines.Source: §6.2 · p. 19, §6.3 · p. 19
6.3 Experimental Results
- At 10 ms inter-arrival, the proposed scheduler reaches HS = 81.41%, versus 59.50% for the client-aware baseline and 50.74% for FF+TC/FF+TCSD; throughput follows the same trend.The comparison is under preserved HRT schedulability.Source: Figure 5 · p. 20, §6.3 · p. 21
- At 10 ms, the proposed scheduler keeps the worst client at 62.05%, a 31.86-percentage-point gain over the best baseline.At 40 ms, its worst-client SLO achievement rate is 90.32%, compared with 82.93% for SSML.Source: Figure 7 · p. 21, §6.3 · p. 21
- At 10 ms, the proposed scheduler combines HS = 81.41% with a 12.16% standard deviation in client-level rates, while FF+TC and FF+TCSD have a 49.99% standard deviation and a 0.00% worst-client rate.FCFS has a 10.03% standard deviation but only HS = 15.27%.Source: §6.3 · p. 21, Figure 8 · p. 22
- The scheduler has a very low fallback rate, which the authors attribute to HRT-aware policy inputs and a large negative reward for HRT deadline violations.Fallback occurs when the runtime test rejects a candidate prefix and execution returns to the certified reference schedule.Source: §6.3 · p. 22, Figure 9 · p. 23
- Without the safety envelope, the policy reaches 99.8% HRT and 81.4% SRT deadline satisfaction, but HRT correctness is no longer guaranteed.The authors use this diagnostic to distinguish empirical performance from the guarantee supplied by deterministic fallback.Source: §6.3 · pp. 22–23, Figure 10 · p. 23
- A policy trained with a 5 ms scheduling period achieves HS values from 69.45% to 81.40% across the tested periods, while separately trained policies achieve 25.69% to 62.81%.The authors report that the 5 ms-trained policy retains effectiveness across scheduling frequencies.Source: §6.3 · p. 24
7 Related Work
Related work covers heterogeneous hard-periodic and soft-aperiodic scheduling, DNN inference scheduling on accelerators, and slack-stealing approaches. The paper distinguishes its setting by considering heterogeneous precedence-constrained DNN workloads and client-level QoS alongside HRT guarantees.
Hard-periodic/soft-aperiodic scheduling on heterogeneous resources
- Tang et al. schedule hard periodic tasks offline and use per-resource slack windows to admit soft aperiodic work online on heterogeneous resources.Their original model assumes independent, non-preemptive tasks that can execute on any resource with resource-dependent execution times.Source: §7 · p. 24
DNN inference on domain-specific accelerators
- DNN accelerator schedulers address runtime allocation, utilization, and co-location, while the cited systems do not focus on single-client QoS or deterministic HRT guarantees; CD-MSA targets homogeneous accelerators.Static approaches such as LayerWeaver and AI-MT cannot adapt to runtime variability.Source: §7 · p. 25
Slack stealing and modified look-ahead EDF
- Slack stealing uses unused processing time from a guaranteed periodic schedule for aperiodic work, and SSML adapts look-ahead EDF principles to uniprocessor systems.The cited SSML setting assumes independent tasks.Source: §7 · p. 25
8 Conclusion
The conclusion presents a framework that pairs online RL scheduling with deterministic runtime certification for heterogeneous multi-accelerator DNN workloads. It reports preserved HRT schedulability alongside improved QoS-related outcomes and identifies extensions to runtime uncertainties, workload prediction, and alternative QoS objectives.
8 Conclusion
- The framework combines an online RL scheduler with deterministic runtime certification that guarantees HRT correctness independently of the learned policy.The certification supports runtime adaptation through a schedulability-preserving prefix replacement criterion for heterogeneous precedence-constrained schedules.Source: §8 · pp. 25–26
- Experiments report preserved HRT schedulability and improvements in QoS-aware deadline satisfaction, client-level service quality, and accelerator utilization over state-of-the-art approaches.Source: §8 · p. 26
- Future work includes support for additional runtime uncertainties, workload prediction mechanisms, and alternative QoS optimization objectives.Source: §8 · p. 26