Safety-critical parallel software, such as a perception pipeline in a self-driving car, is often modeled as a DAG (a directed acyclic graph). Each node is a piece of work, and each edge says one piece must finish before another starts. To certify the system, engineers need a guaranteed upper limit on how long the whole graph can take on $m$ processor cores: its worst-case response time. For fifty years the standard limit has been Graham's bound. A recent line of work tightens it considerably by looking at the graph's shape. The key observation is that work competing with the longest chain is itself made of chains, so it cannot flood every core at once. These multi-path bounds report large gains, and every one of them was measured only on randomly generated graphs with fixed, known node run times, on idealized cores that do not slow each other down. Real cores do slow each other down, sometimes badly. They share caches and a memory controller, and measured slowdowns reach 6.2x on embedded Arm chips.
This note proposes two things. The first is the missing hardware test: do multi-path bounds remain safe and tight on real chips? The second is a specific idea that the test can confirm or refute. The same shape property that multi-path analysis exploits, namely that interfering work cannot occupy all cores simultaneously, also limits how many nodes can run alongside any given node. That in turn limits how much memory contention each node can suffer. If this is right, the graph's shape should be used twice: once to limit scheduling interference, as prior work does, and once to limit how much each node's run time grows under contention, which nobody does yet. If it is wrong, because contention saturates with one or two co-runners, the experiments will show that. The fallback, a simple uniform inflation of every node's run time, is then the right answer, and we will report it as such.
Core Claim
Existing multi-path bounds take node run times as given. This leaves two ways to use them on hardware. The naive way plugs in run times measured with each node running alone, and it is likely unsafe. The conservative way inflates every run time by the worst slowdown seen with $m-1$ co-runners, and it is safe but gives back much of the tightening. We claim a middle option is both empirically safe and measurably tighter. Let $c_v$ be node $v$'s run time measured alone. Let $w(\bar v)$ be the width of the set of nodes that have no path to or from $v$, meaning the largest number of those nodes that could ever run at the same time. Let $\sigma(k)$ be the worst measured slowdown factor of any node when $k$ adversarial co-runners share the memory system. Each node then gets the inflated run time
$$\hat c_v = \sigma\big(\min(m-1,\; w(\bar v))\big)\, c_v ,$$
and the unmodified minimum-cost-flow multi-path bound is applied to the graph with the $\hat c_v$ values. Width is a maximum antichain size, computable in polynomial time by bipartite matching via Dilworth's theorem.
Soundness here is empirical, not proven. It holds only if slowdown depends mainly on the number of co-runners and grows monotonically with it, and establishing whether that is true is one of the measurements. The inflation is monotone in $c_v$ and leaves the graph structure unchanged. The bound therefore inherits the self-sustainability property proven in Multipath Bound for DAG Tasks: shortening any node's run time never raises the bound.
The idea also yields a sharp prediction about the "longer is shorter" effect. Longer Is Shorter adds artificial edges that force some independent nodes to run one after another, and it reports a 21.6% average reduction in the bound on synthetic graphs. Adding edges shrinks $w(\bar v)$, so in our model the edges should help twice. On silicon, however, each added edge becomes a real synchronization with a real cost. Whether the net effect survives has never been measured.
Relation to Prior Work
The motivating line of work consists of Bounding the Response Time of DAG Tasks Using Long Paths and The shape of a DAG. They extract a sequence of disjoint long paths by repeatedly zeroing out the longest path, and they report bounds 13.1% to 16.2% below Graham's. Multipath Bound for DAG Tasks generalizes the choice of paths through a minimum-cost flow formulation and reports acceptance-ratio gains of up to 53.2% over earlier path bounds. Optimizing Federated Scheduling via Node-Level Parallelization splits nodes into parallel sub-threads. These four papers supply the analysis we reuse unchanged. All of them evaluate only on synthetic Erdős-Rényi graphs, and the last explicitly concedes that identical sub-thread run times and a fixed overhead ratio would not hold on real caches. We change the input to their analysis, not the analysis itself.
The evidence that the inputs matter comes from Arm DynamIQ Shared Unit and Real-Time: An Empirical Evaluation. It measures slowdowns of up to 6.2x on RK3568, shows that cache way-partitioning can make things worse through reduced associativity, and shows that streaming writes on Cortex-A55 cores bypass the shared L3 cache entirely. That study used only sequential kernels and never tested a DAG-level bound, which is exactly the step we take. CITTA does model shared-cache interference analytically. It assumes independent sequential tasks and a direct-mapped cache, and it was evaluated only in simulation. We sidestep its cache-modeling assumptions by measuring $\sigma(k)$ directly, at the price of claiming empirical rather than formal safety.
Learning to Schedule DAG Tasks also adds edges to DAGs, but it minimizes average makespan on TPC-H and offers no worst-case bound. It is therefore not a competitor for certification, and it lends no support to the claim that added edges are cheap on hardware. The broader pattern of guarantees that go unchecked on real systems is documented well outside scheduling. One example is the conservative parameters that sank practical use of provably fast local clustering in A Local Clustering Algorithm for Massive Graphs. That pattern is why we treat "the bound was never tested on hardware" as a substantive gap and not a formality.
Research Program
The work has three stages.
Stage 1: contention curves. On each platform we measure the curve $\sigma(k)$ for $k = 0, \dots, m-1$. The platforms are RK3588, using its four big cores as a homogeneous cluster, RK3568, and NVIDIA Orin AGX, all taken from the DynamIQ study. For each $k$, a victim is chosen from SD-VBS vision kernels and the co-runners from the Interference-bench stress kernels. We take $\sigma(k)$ as the worst ratio of observed to isolated run time over all victim and co-runner combinations. This stage decides whether the idea has any room to help. A roughly linear curve means that knowing a node's concurrency limit is valuable. A curve that saturates at $k=1$ means it is not.
Stage 2: a real DAG runtime. We build a small work-conserving runtime. It runs a fixed pool of threads pinned to the $m$ cores of one cluster, with real-time scheduling priority on a PREEMPT_RT kernel and a shared first-in-first-out queue of ready nodes. Each graph node executes a real kernel. The runtime logs per-node start and finish times using hardware cycle counters. We run each DAG thousands of times with randomized release jitter and with adversarial memory traffic on the other cluster. The recorded maximum is the observed high-water response time. From the same logs we measure the cost $\delta$ of an artificial precedence edge, meaning the extra latency of one signal-and-wait between two threads on different cores, so that "longer is shorter" can be evaluated with its real cost included.
Stage 3: comparing bounds on identical inputs. Every bound variant receives the same graphs and the same measured run times. We record three things for each: its ratio to the observed high-water mark, whether it was ever violated, and the smallest core count it certifies against a deadline.
Baselines
The naive reference point is Graham's bound with run times measured in isolation. It is what a practitioner would compute today, and it sets the floor for tightness and the first test of safety.
The literature as published is the minimum-cost-flow multi-path bound of Multipath Bound for DAG Tasks, again fed isolated run times. Its reported advantage is up to 53.2% in acceptance ratio over earlier path bounds, and Bounding the Response Time of DAG Tasks Using Long Paths reports a 13.1% to 16.2% tighter bound than Graham. No reported result was found on Lacuna for any multi-path bound on physical hardware. Our first headline number is the violation rate of this baseline. A nonzero rate would be the empirical finding that the published bounds are unsafe as deployed.
The strongest competitor is the same multi-path bound with every run time inflated uniformly by $\sigma(m-1)$. It is simple, it is empirically safe whenever our method is, and it is what a careful engineer would do. It gets exactly the same measured curve, graphs, and runs as our method, and neither side has any tuning parameters. Our method beats it only if two conditions hold together: zero observed violations across all runs and platforms, and a bound whose ratio to the observed maximum is clearly lower, or a certified core count that is smaller on a meaningful fraction of graphs.
The key ablation replaces the per-node $w(\bar v)$ with the width of the whole graph, a single number. This isolates whether the gain comes from per-node structure or merely from the fact that narrow graphs exist.
For the edge-addition question, the baseline is Longer Is Shorter's method run on hardware in two ways. One version ignores edge cost, as the paper does. The other charges $\delta$ per added edge and compares the result with the observed response time of the edge-augmented graph.
Why not just…?
Why not just inflate every run time by the worst multi-core slowdown and keep the existing bound? This is the real threat, and the proposal is built around beating it. If Stage 1 shows that $\sigma(k)$ saturates at small $k$, which is plausible given the memory-controller bottleneck the DynamIQ study reports once working sets overflow L3, then per-node concurrency limits buy almost nothing. We would then recommend uniform inflation. Even in that outcome the project still produces the first hardware safety test of multi-path bounds.
Why not just partition the cache and use the bound unchanged? Arm DynamIQ Shared Unit and Real-Time shows that partitioning reduces slowdowns by 2x to 4x but does not remove them. It fails when working sets exceed the partition, can be bypassed by streaming writes, and leaves the unpartitioned L4 on Orin as a path for interference. We include a partitioned configuration. Our method should need less inflation there, not zero, and whether isolated run times become safe in that setting is measured directly.
Why not just certify with the measured high-water mark? An observed maximum is not a bound. It cannot be computed before deployment, it says nothing about new graphs or core counts, and it gives no guidance on how many cores to provision. We use it only as the reference against which tightness and violations are judged.
Why not stay with Graham's bound, which is simple and safe? It is only safe if its inputs are safe. With isolated run times it faces the same contention problem, and with uniform inflation it is looser than the inflated multi-path bound by construction. Both variants are reported, so the size of the gap on real hardware becomes a measured quantity.
Proposed Experiments
Workloads. We use three families. The first is Erdős-Rényi graphs with 50 to 250 nodes matching the prior papers' generators, with each node bound to a randomly chosen SD-VBS kernel so that the synthetic results can be compared directly. The second is graphs built from Autoware- and Apollo-style perception and planning pipelines, following Open-Source Autonomous Driving Software Platforms, with real kernels as stand-ins for each stage. The third is the same graphs after edge addition by the method of Longer Is Shorter.
Metrics. We report violation rate, the ratio of each bound to the observed high-water mark, the minimum certified core count, and acceptance ratio against a deadline sweep.
Decisive checks. The first check is whether the isolated-run-time multi-path bound is ever violated. The second is the shape of $\sigma(k)$ on each platform. The third is whether our bound has zero violations while beating the uniformly inflated bound in tightness, with the whole-graph-width ablation showing that the per-node structure accounts for the difference. The fourth is whether $\delta$ times the number of added edges exceeds the reduction in the bound from edge addition. That would mean the "longer is shorter" gain does not survive real hardware, and we would report it as a negative result.
References
- Multipath Bound for DAG Tasks
- Longer Is Shorter: Making Long Paths to Improve the Worst-Case Response Time of DAG Tasks
- Bounding the Response Time of DAG Tasks Using Long Paths
- The shape of a DAG: bounding the response time using long paths
- Optimizing Federated Scheduling for Real-Time DAG Tasks via Node-Level Parallelization
- Arm Dynamiq Shared Unit and Real-Time: An Empirical Evaluation
- CITTA: Cache Interference-aware Task Partitioning for Real-time Multi-core Systems
- Learning to Schedule DAG Tasks
- A Local Clustering Algorithm for Massive Graphs and Its Application to Nearly Linear Time Graph Partitioning
- Open-Source Autonomous Driving Software Platforms: Comparison of Autoware and Apollo