DROPS

Document

DOI: 10.4230/LIPIcs.ECRTS.2026.13

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

Authors: Tiancheng He and Bryan C. Ward

Published in: LIPIcs, Volume 375, 38th European Conference on Real-Time Systems (ECRTS 2026)

Abstract

Cache-related preemption delay (CRPD) analysis bounds the additional execution time caused by cache evictions during preemptions. Tightly bounding CRPDs is challenging as there are many possible preemption patterns that can occur at runtime, and thus there has been continuous work over three decades to refine these bounds. This paper presents CacheFlow, a framework that formulates total CRPD as a maximum-flow problem. In the flow network, nodes and edge capacities can be constructed to model certain eviction patterns that can occur. Therefore, by (safely) removing nodes or edges, or reducing edge capacities, tighter CRPD bounds can be derived. This is demonstrated with different CacheFlow refinements, some of which include insights from prior analyses, as well as a refinement for simply periodic systems. An iterative max-flow formulation is also described to more efficiently integrate the max-flow solving in the context of standard fixed-priority response-time analysis. Experiments on synthetic task systems demonstrate significant schedulability improvements across a range of system configurations, while also having reasonable solving times.

Cite as

Tiancheng He and Bryan C. Ward. CacheFlow: Using Maximum Flow to Bound Cache-Based Preemption Delays. In 38th European Conference on Real-Time Systems (ECRTS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 375, pp. 13:1-13:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{he_et_al:LIPIcs.ECRTS.2026.13,
  author =	{He, Tiancheng and Ward, Bryan C.},
  title =	{{CacheFlow: Using Maximum Flow to Bound Cache-Based Preemption Delays}},
  booktitle =	{38th European Conference on Real-Time Systems (ECRTS 2026)},
  pages =	{13:1--13:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-429-1},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{375},
  editor =	{Kritikakou, Angeliki},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2026.13},
  URN =		{urn:nbn:de:0030-drops-266058},
  doi =		{10.4230/LIPIcs.ECRTS.2026.13},
  annote =	{Keywords: Cache-related Preemption Delay, Real-Time Systems, Maximum Flow}
}

Document

Artifact

DOI: 10.4230/DARTS.12.2.7

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

Authors: Tiancheng He and Bryan C. Ward

Published in: DARTS, Volume 12, Issue 2, Special Issue of the 38th European Conference on Real-Time Systems (ECRTS 2026)

Abstract

This artifact accompanies the ECRTS 2026 paper CacheFlow: Using Maximum Flow to Bound Cache-Based Preemption Delays [Tiancheng He and Bryan C. Ward, 2026]. It provides the Rust plus Python implementation of every cache-related preemption delay (CRPD) analysis evaluated in the paper, the experiment harness used to compare them, the configurations that drive each figure in the paper, and a Docker-based build that fully reproduces the experimental claims of Sections 7.2-7.4. We claim all four ECRTS artifact-evaluation badges: Available, Functional, Reusable, and Results Reproduced.

Cite as

Tiancheng He and Bryan C. Ward. CacheFlow: Using Maximum Flow to Bound Cache-Based Preemption Delays (Artifact). In Special Issue of the 38th European Conference on Real-Time Systems (ECRTS 2026). Dagstuhl Artifacts Series (DARTS), Volume 12, Issue 2, pp. 7:1-7:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@Article{he_et_al:DARTS.12.2.7,
  author =	{He, Tiancheng and Ward, Bryan C.},
  title =	{{CacheFlow: Using Maximum Flow to Bound Cache-Based Preemption Delays (Artifact)}},
  pages =	{7:1--7:5},
  journal =	{Dagstuhl Artifacts Series},
  ISSN =	{2509-8195},
  year =	{2026},
  volume =	{12},
  number =	{2},
  editor =	{He, Tiancheng and Ward, Bryan C.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DARTS.12.2.7},
  URN =		{urn:nbn:de:0030-drops-266240},
  doi =		{10.4230/DARTS.12.2.7},
  annote =	{Keywords: Cache-related preemption delay; CRPD; max-flow; schedulability analysis; real-time systems; artifact}
}

Search Results

Documents authored by He, Tiancheng

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

Abstract

Cite as

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

Abstract

Cite as

Thanks for your feedback!

Could not send message