CacheFlow: Using Maximum Flow to Bound Cache-Based Preemption Delays

In this work, we present a new framework that we call CacheFlow that enables these types of insights to be more easily composed to compute tighter CRPD bounds. We address the pessimism inherent in summing independent worst-case bounds by formulating the total CRPD as a max-flow problem over an analysis interval. CRPDs can be viewed as flow from preempting jobs and their corresponding ECBs, to preempted jobs, and their corresponding UCBs. We describe this new technique as a framework: the flow network can be constructed in a number of ways to exploit specific insights about the task system, such as adding or removing nodes from the flow network, or adjusting edge capacities.

A key advantage of this approach is that it shifts the focus from bounding CRPD on a per-job or per-task basis to bounding the total CRPD incurred across an entire analysis interval for all jobs in that interval. By considering the aggregate behavior of all jobs within a window of time, CacheFlow can account for constraints that are difficult to capture in traditional set-based analyses. This interval-based perspective allows for a more holistic accounting of cache usage and preemption patterns, further reducing the pessimism inherent in summing independent worst-case bounds.

Previous CRPD analysis methods have leveraged information from cache and timing analysis that determined which cache blocks are useful, i.e., will be reused, and which cache blocks are evicting, or simply accessed during the job’s execution, possibly evicting cache lines of preempted jobs. In this work, we define the utility of a cache block, which generalizes these previous approaches. Specifically, the utility of a cache block bounds the total number of times that a cache block may be reused during a job’s execution, assuming it executes in isolation. Thus, if the utility of a cache block is zero (resp., non-zero), that cache block is an evicting (resp., useful) cache block. Cache utility allows us to further reduce pessimism in CRPD analysis, as the total CRPD accounted for due to a given cache block should not exceed its utility. This information can also be incorporated into our CacheFlow framework by adjusting the capacity of some edges in the flow network.

• $\mathrm{■}$

  We introduce CacheFlow, a framework that formulates CRPD analysis as a max-flow problem over a network of job-level cache interactions. By bounding the total CRPD across a set of jobs – rather than summing per-job bounds – CacheFlow captures cross-job constraints that existing analyses cannot express.

• $\mathrm{■}$

  We define cache-block utility, a generalization of the binary useful/evicting classification. Utility bounds the number of cache hits a block provides within a single job execution, allowing CacheFlow to tighten CRPD bounds by limiting flow through individual cache-block edges.

• $\mathrm{■}$

  We present two network refinements – frequency constraints and aggregate task constraints – that embed the insights of prior analyses (UCB-Union-Multiset and ECB-Union-Multiset) as bottleneck nodes in the flow network.

• $\mathrm{■}$

  We present an incremental algorithm that integrates CacheFlow into fixed-priority response-time analysis (RTA). The algorithm exploits the monotonic growth of the flow network across RTA iterations by reusing the residual graph, and includes an early-exit optimization that avoids computing the full max-flow when the CRPD budget is already exceeded.

• $\mathrm{■}$

  We evaluate CacheFlow experimentally against prior uniprocessor CRPD analysis techniques, demonstrating significant improvements in schedulability across a range of system configurations.

Consistent with prior work on CRPD analysis, we assume a single-level direct-mapped cache. When a job $J_{i,k}$ preempts a lower-priority job, $J_{i,k}$ may evict cache lines that the preempted job would have reused, causing additional cache misses upon resumption. The resulting delay is called cache-related preemption delay (CRPD). CRPD analysis relies on two sets derived from cache analysis: the evicting cache blocks ${\mathrm{𝐸𝐶𝐵}}_i$ of task ${\tau }_i$, which are the cache blocks that ${\tau }_i$ may access (and thus potentially evict from the cache); and the useful cache blocks ${\mathrm{𝑈𝐶𝐵}}_i$, which are the cache blocks that ${\tau }_i$ may have cached and would reuse absent a preemption. The block reload time, denoted $\mathrm{𝐵𝑅𝑇}$, is the worst-case time to reload a single cache block from main memory.

A flow network is a directed graph $G=(V,E)$ with a designated source $S$, a sink $T$, and a capacity $c(u,v)\ge 0$ on each directed edge $(u,v)$. A flow assigns a non-negative value $f(u,v)\le c(u,v)$ to each edge such that flow is conserved at every internal vertex. The maximum-flow problem seeks the assignment that maximises the total flow from $S$ to $T$; by the max-flow/min-cut theorem this equals the minimum capacity cut separating $S$ from $T$. Maximum flow is solvable in polynomial time (e.g., Dinic’s algorithm runs in $O(V^{2}E)$).

We bound the CRPD that $J_{i,k}$ causes to its victims in $\mathrm{𝑙𝑝}(J_{i,k},t)$, not the CRPD $J_{i,k}$ itself experiences. The cache set $b$ maps to holds at most one occupant; when $J_{i,k}$ first accesses $b$, if that occupant is a victim $J_{x,y}\in \mathrm{𝑙𝑝}(J_{i,k},t)$ the access evicts $J_{x,y}$’s $b$-data and the victim will pay $\mathrm{𝐵𝑅𝑇}$ to reload $b$ once it resumes; otherwise no victim CRPD is caused. Under fixed-priority preemptive scheduling, $J_{x,y}$ cannot run again until $J_{i,k}$ completes, so $J_{x,y}$ reloads $b$ at most once regardless of any further evictions of the slot during $J_{i,k}$’s execution. Hence $J_{i,k}$ causes at most $\mathrm{𝐵𝑅𝑇}$ of CRPD per ECB across all victims it preempts. $◀$

From this lemma, we construct the following edge subset.

This edge subset encodes the fact that each evicting cache block can cause at most $\mathrm{𝐵𝑅𝑇}$ CRPD.

An evicting cache block can only evict data that maps to the same cache set, so $b$ can only evict cache blocks that map to the same set as $b$. Furthermore, $J_{i,k}$ can only preempt lower-priority jobs, i.e., jobs $J_{x,y}\in \mathrm{𝑙𝑝}(J_{i,k},t)$. Finally, the eviction of $b$ causes a CRPD for $J_{x,y}$ only if $b$ would have been reused by $J_{x,y}$ absent the preemption, i.e., only if $b\in {\mathrm{𝑈𝐶𝐵}}_x$. $◀$

We can apply this result to construct the following edge set.

This edge subset encodes the fact that an evicting cache block of a higher-priority job can only cause CRPD to a lower-priority job if the same memory block $b$ belongs to both ${\mathrm{𝐸𝐶𝐵}}_i$ and ${\mathrm{𝑈𝐶𝐵}}_x$. In a direct-mapped cache, each memory block maps to a unique cache set, so the intersection $b\in {\mathrm{𝐸𝐶𝐵}}_i\cap {\mathrm{𝑈𝐶𝐵}}_x$ is on memory-block identity and simultaneously implies the same cache-set mapping.

The previous edge sets are derived from similar observations as have been used to derive previous CRPD analysis techniques. The remaining edge sets are derived from new observations. Importantly, these new observations codify an interesting and important intersection between cache analysis and CRPD and schedulability analysis.

Compared to closed-form CRPD bounds, CacheFlow incurs additional computational cost because each step of the fixed-point response-time iteration requires solving a max-flow instance on the network $G(t)$. While this is more expensive than several prior approaches, the max-flow problem is solvable in polynomial time in the size of the constructed graph. To quantify this overhead in practice, we include in our evaluation the wall-clock analysis time per generated task system, reporting the total time spent across the RTA fixed-point loop and all max-flow invocations.

From a worst-case perspective, the overall test is pseudo-polynomial. The size of $G(t)$ depends on the number of jobs in $𝒥(t)$ and the number of cache-block vertices (ECB/UCB, and frequency vertices in refined variants), which in turn depend on numeric parameters such as task periods and the candidate response time $t$. As $t$ grows, additional jobs enter $𝒥(t)$ and the graph expands, increasing the cost of each max-flow solve. Since fixed-priority RTA is itself pseudo-polynomial in the same parameters, composing RTA with a polynomial-time max-flow solver yields an overall pseudo-polynomial schedulability test.

The graph $G=(V,E)$ defined above is parameterized by the interval length $t$: the job set $𝒥(t)$ determines which culprit and victim nodes exist, and therefore which ECB and UCB nodes and edges are present. In fixed-priority response-time analysis (RTA), $t$ is the candidate response time that is iteratively refined in a fixed-point computation. As $t$ increases, $|𝒥(t)|$ can only grow – new jobs are released, but no previously released job leaves the analysis window. Consequently, $G$ expands monotonically with $t$.

The maximum flow through $G(t)$ provides a safe upper bound on the total CRPD that can occur during an interval of length $t$. Because all edge capacities are expressed in time units (multiples of $\mathrm{𝐵𝑅𝑇}$), the max-flow value directly gives the CRPD bound. The edge capacities encode exactly the constraints derived in Edge subsets 1–5: the per-block reload cost (Lem. 2), the cache-set matching requirement, and the per-block utility bound. Since every feasible CRPD scenario corresponds to a feasible flow through $G(t)$, the maximum flow is an upper bound on total CRPD. Standard RTA convergence arguments apply [12]: if the right-hand side of (14) is monotonically non-decreasing in $t$ and bounded, the iteration converges to a least fixed point. $◀$

As $t$ increases, jobs may be added to $𝒥(t)$ but never removed. Each new job $J_{j,k}$ adds a culprit vertex, a victim vertex, and corresponding ECB and UCB vertices, together with their incident edges. No existing vertices or edges are removed. Since the feasible region of the max-flow problem can only grow, the optimal flow value cannot decrease. $◀$

This monotonicity property is essential: it ensures that the demand function on the right-hand side of (14) is non-decreasing, which guarantees that the fixed-point iteration either converges or exceeds $d_i$. Intuitively, because new jobs only add nodes and edges to $G(t)$ and no existing vertex or edge is ever removed, the set of feasible flows can only expand as $t$ grows – so the maximum flow is monotone in $t$, underpinning the convergence of Algorithm 1.

Each refinement from the previous section preserves monotonicity. For the periodic refinement, edge set $E_3^{\prime }$ can only gain edges as $t$ grows, since new jobs may enter $𝒥(t)$ and create new feasible preemption pairs, but no existing pair is invalidated. For frequency constraints, the frequency factor $\lceil \frac{R_x}{p_j}\rceil$ depends on $R_x$, which is non-decreasing across RTA iterations; hence the capacity of every $E_{3b}$ edge can only grow. For aggregate task constraints, the ECB-Union-Multiset bound ${\gamma }_j^{\text{ecb}}(t)$ and the UCB-Union-Multiset bound ${\gamma }_x^{\text{ucb}}(t)$ are both non-decreasing in $t$, so the $E_{1a}$ and $E_{5b}$ capacities can only grow. When the candidate response time increases during the RTA iteration, the edge capacities are updated by adding the difference between the new and old bounds to the residual capacity. In all cases, no existing vertices or edges are removed, so Lem. 17 and the incremental algorithm apply without modification.

The monotonic growth of $G$ suggests an efficient incremental strategy. Rather than rebuilding the graph and solving from scratch at each iteration, we extend the residual graph from the previous iteration and compute only the additional flow contributed by newly added nodes and edges. Algorithm 1 presents this approach.

The key insight is that the max-flow solver operates on the residual graph $G_R$ from the previous iteration. Because existing edges and their residual capacities are preserved, the solver need only search for augmenting paths through the newly added portion of the graph. The accumulated flow $F_{\text{total}}$ gives the total CRPD bound at each step.

At each iteration, the algorithm computes a budget: the maximum additional CRPD that the system can tolerate at the current candidate response time $t$. When $F_{\text{total}}$ is below the budget, the remaining slack $\mathrm{𝑏𝑢𝑑𝑔𝑒𝑡}-F_{\text{total}}$ is passed as a flow limit to the solver (line 12), which stops as soon as the limit is reached. When $F_{\text{total}}$ already meets or exceeds the budget, the solver is still invoked without a restrictive limit (line 13) to ensure that the total flow reflects any new augmenting paths introduced by newly added nodes and edges. This is necessary for correctness: without it, $F_{\text{total}}$ could remain stale, causing the iteration to converge prematurely to an unsafe value.

The size of the flow network $G(t)$ is pseudo-polynomial in the task parameters: the number of vertices and edges depends on the number of jobs $|𝒥(t)|={\sum }_{{\tau }_j\in \mathrm{ℎ𝑝}({\tau }_i)}\lceil t/p_j\rceil$, which grows with the numeric parameter $t$. Since max-flow is solvable in polynomial time in the size of the network, and fixed-priority RTA is itself pseudo-polynomial, the overall schedulability test is pseudo-polynomial. In practice, warm-starting the solver from the previous iteration’s residual graph and the early-exit optimization described above keep runtimes well within practical bounds, as shown in the evaluation.

CRPD analysis dates back to Lee et al. [14], who defined useful cache blocks (UCBs) and evicting cache blocks (ECBs) and showed how to incorporate CRPD into fixed-priority response-time analysis. Busquets-Mataix et al. [9] proposed an ECB-Only approach that bounds CRPD using only the evicting cache blocks of the preempting task. Altmeyer and Burguière [1] refined the UCB definition by restricting it to definitely-cached blocks (DC-UCBs), significantly reducing the number of blocks classified as useful and thereby tightening CRPD bounds.

Building on these foundations, Altmeyer, Davis, and Maiza [2, 3] systematically formalized four approaches to CRPD analysis: ECB-Only, UCB-Only, ECB-Union, and UCB-Union. They established dominance relationships among these approaches and showed that the ECB-based and UCB-based families are incomparable – neither strictly dominates the other in all cases. Their journal paper [3] further introduced multiset variants (ECB-Union-Multiset and UCB-Union-Multiset) that compute a sorted multiset of per-preemption CRPD costs and sum the largest $k$ entries, yielding tighter bounds than multiplying the worst-case per-preemption cost by the number of preemptions.

All of the above approaches bound CRPD on a per-job or per-preemption basis and then aggregate over multiple preemptions. In contrast, CacheFlow bounds the total CRPD across a set of jobs holistically by encoding cross-job constraints in a flow network. This allows CacheFlow to exploit structural constraints – such as the fact that a single ECB can cause at most $\mathrm{𝐵𝑅𝑇}$ total CRPD across all victims – that per-job analyses cannot capture.

Several works have sought to tighten CRPD bounds beyond the four classic approaches. Altmeyer, Maiza, and Reineke [4] introduced resilience analysis, a quantitative cache property that measures how many accesses a cache block can survive before being evicted in a set-associative cache. Resilience refines CRPD analysis for LRU caches by accounting for associativity. Our notion of cache-block utility is related in spirit but captures a different property: whereas resilience measures robustness against eviction, utility quantifies the total reuse benefit of a cache block, i.e., the maximum number of accesses to a block that are definitely cache hits.

Kleinsorge, Falk, and Marwedel [13] proposed a synergetic approach that jointly considers the cache states of the preempting and preempted tasks, achieving tighter bounds than analyzing each in isolation. Rashid et al. [24, 23] observed that not all UCBs are evicted on every preemption when cache persistence is considered and integrated cache persistence analysis with CRPD analysis. Stock, Hahn, and Reineke [26] later showed how to make cache persistence analysis exact. Marković et al. [21] proposed preemption partitioning, which assigns each preemption point to a specific higher-priority task and computes a tighter per-task CRPD bound accordingly.

These refinements are complementary to CacheFlow: the per-job or per-block CRPD information they produce can be incorporated as edge capacities in our flow network. Specifically, persistence-aware analysis refines the inputs to CRPD analysis – the useful-block sets and their per-block reload counts – rather than the algorithm that aggregates them. CacheFlow consumes such refinements directly: tighter UCB sets reduce the number of $E_3$ edges, and a per-block utility $U_b$ derived from persistence analysis tightens $E_4$ capacities. We therefore view persistence- and resilience-aware analyses as complementary to, and composable with, our framework. However, none of them formulates CRPD as an optimization problem or considers cross-job interactions the way a flow network does.

Lunniss et al. [18] extended CRPD analysis to EDF scheduling by bounding per-task CRPD over an interval. Our work builds directly on this interval-based formulation but bounds the total CRPD across all tasks in the interval, further reducing pessimism. The same group also compared FP and EDF scheduling accounting for CRPD [16], considered hierarchical scheduling [17], and, with Davis and Dobrin, analyzed preemption thresholds [8].

On the architecture side, Zhang and Koutsoukos [27] addressed CRPD in multi-level inclusive cache hierarchies, Fischer and Falk [11] tackled non-inclusive hierarchies, and Ballabriga et al. [5] considered FIFO replacement policies using ILP. Shah et al. [25] provided an experimental evaluation of existing CRPD-aware analysis techniques. The ECB and UCB sets used as inputs to all compared analyses are standard outputs of cache analysis: binary cache analyses such as those in [14, 1] and commercial tools (e.g., AbsInt’s aiT) derive these sets from control-flow graphs and binary executables. Benchmark suites such as TACLeBench and Mälardalen have been used in this manner (e.g., Shah et al. [25]), providing a clear path to applying CacheFlow to real workloads. Altmeyer et al. [10] proposed a compositional framework for multicore response-time analysis incorporating CRPD. Nguyen et al. [22] used cache-awareness to improve offline scheduling decisions. For a comprehensive survey, we refer the reader to Lv et al. [19] for static cache analysis and Maiza et al. [20] for multicore timing verification.

The use of network flow and mathematical programming in real-time systems analysis has methodological precedent, though not in CRPD analysis. Bonifaci, Marchetti-Spaccamela, and Stiller [6] used network flow to construct a constant-factor feasibility test for multiprocessor scheduling, where flow represents the allocation of computational work to processors. Brandenburg [7] used linear programming to derive tight blocking bounds for semaphore protocols under partitioned fixed-priority scheduling. Li and Malik [15] pioneered the implicit path enumeration technique (IPET), using integer linear programming to compute WCET bounds.

CacheFlow shares the philosophy of formulating a timing-analysis problem as a combinatorial optimization problem, but differs in what the optimization captures. In [6], flow represents work allocation; in [7], LP variables represent blocking scenarios. In CacheFlow, flow through the network represents CRPD. The max-flow/min-cut formulation naturally encodes constraints that span multiple jobs – for instance, the constraint that a single ECB can cause at most $\mathrm{𝐵𝑅𝑇}$ total CRPD across all jobs it preempts – which cannot be expressed in per-job analyses.