Scheduling Cause-Effect Chains without Timing Anomalies in End-to-End Latency

Titel: Scheduling Cause-Effect Chains zonder Timing Anomalieën in End-to-End Latentie

Auteurs: Yixuan Zhu, Bo Zhang, et al. (University of Science and Technology of China)
Publicatie: DAC '26 (Design Automation Conference), 2026.

---

1. Het Probleem: Timing Anomalieën in Real-time Systemen

In real-time systemen, zoals die gebruikt worden in autonoom rijden, moeten zowel de uitvoering van individuele taken als de dataverplaatsing tussen taken voldoen aan strikte timing-voorwaarden. Deze systemen worden vaak gemodelleerd als Oorzaak-Werkingsketens (Cause-Effect Chains of CE-chains).

Het centrale probleem dat dit paper adresseert, zijn Timing Anomalieën (TA).

• Definitie: Een timing anomalie treedt op wanneer een lokale verkorting van de uitvoeringstijd van een taak (bijvoorbeeld omdat een taak sneller is dan zijn Worst-Case Execution Time, WCET) onverwachts leidt tot een toename van de totale end-to-end latentie van het systeem.
• Oorzaak: Door variaties in uitvoeringstijden kunnen de data-propagatiepaden tussen taken veranderen. Een taak die normaal gesproken wacht op een langere taak, kan in een snellere scenario juist wachten op een andere taak die later beschikbaar komt, waardoor het totale reactietijd (Maximum Reaction Time, MRT) toeneemt.
• Huidige beperkingen:
  1. Bestaande methoden die TA's elimineren (zoals het dwingen van alle taken om hun WCET te uitvoeren) leiden tot een enorme verslechtering van de gemiddelde latentie.
  2. Andere methoden proberen TA's veilig te analyseren zonder de planning te wijzigen, maar leveren hierdoor vaak conservatieve (te hoge) bovengrenzen op, omdat de anomalieën fysiek blijven bestaan.

2. Methodologie: Deterministische Data Flow (DDF)

De auteurs stellen een nieuwe behandelingsmethode voor die TA's elimineert met een verwaarloosbaar verlies aan gemiddelde latentie. De kern van de oplossing is het afdwingen van Deterministische Data Flow (DDF).

De methode bestaat uit twee fasen: Offline Analyse en Online Uitvoering.

A. De Twee Oorzaken van TA en de Oplossing

De auteurs identificeren twee fundamentele oorzaken van TA's en bieden daarop een oplossing:

1. Structuurverandering: In niet-WCET scenario's kunnen nieuwe, langere data-paden ontstaan die niet voorkomen in het WCET-scenario.
   • Oplossing: Read-After-Write (RAW). Het afdwingen van vaste producer-consumer afhankelijkheden op taakniveau. Een consumer-taak mag pas starten nadat de specifieke producer-taak zijn schrijven heeft voltooid.
2. Variatie in Leest/Schrijftijden: Zelfs als het pad bekend is, kunnen de exacte tijdstippen waarop data wordt gelezen of geschreven variëren, wat de totale latentie beïnvloedt.
   • Oplossing: Read-From-Intended (RFI). Zorgen dat elke consumer-taak precies de data leest van de bedoelde producer-taak zoals gedefinieerd in het DDF, zelfs als er eerdere data van dezelfde producer beschikbaar is.

B. Technische Implementatie

• Offline Fase:
  • Er wordt een simulatie uitgevoerd waarbij alle taken hun WCET uitvoeren onder de originele planning (Fixed Priority, FP).
  • Uit deze simulatie wordt een DDF afgeleid: een vast patroon van communicatie-relaties tussen specifieke job-instanties.
  • Op basis van de RAW-eis worden de taakkenmerken (release-tijden en prioriteiten) aangepast om de afhankelijkheden te garanderen zonder het tijdsgebaseerde planningssysteem (TT-FP) te verlaten.
• Online Fase:
  • RAW: De aangepaste taakkenmerken zorgen ervoor dat een consumer-taak niet kan pre-empten (onderbreken) zijn producer-taak, waardoor de uitvoeringsvolgorde deterministisch blijft.
  • RFI: Er wordt een multi-buffer communicatiemechanisme gebruikt. In plaats van één register (waarbij de nieuwste data altijd wordt gelezen), worden meerdere buffers gebruikt. Een consumer-taak leest specifiek uit de buffer die hoort bij de bedoelde producer-job uit het DDF. Dit voorkomt dat een taak per ongeluk data van een eerdere, snellere job leest.

3. Belangrijkste Bijdragen

1. Insight: Identificatie van de twee specifieke oorzaken van TA's in end-to-end latentie: variaties in de structuur van job-afhankelijkheidsketens en variaties in leest/schrijftijden.
2. Eerste TA-vrije behandeling: Voor het eerst wordt een methode gepresenteerd die TA's volledig elimineert voor CE-ketens onder Fixed Priority planning, met slechts een verwaarloosbaar verlies aan gemiddelde latentie (in tegenstelling tot eerdere methoden die WCET-uitvoering afdwingen).
3. Algemene Modellering: Definieert een meer algemene definitie van "immediate forward job chains" die zowel register- als multi-buffer communicatie ondersteunt.
4. Formeel Bewijs: Het paper bevat een formeel bewijs dat de voorgestelde behandeling TA-vrij is. Dit wordt gedaan door te bewijzen dat de immediate forward ketens invariant blijven en dat de grenzen van leest/schrijftijden veilig zijn.
5. Precieze Analyse: Omdat TA's zijn geëlimineerd, kan de exacte maximale latentie (MRT) worden bepaald door simpelweg een simulatie met alle WCET's uit te voeren, zonder complexe en pessimistische benaderingen.

4. Experimentele Resultaten

De methode is getest op synthetische taaksets en ketens afgeleid van automotive benchmarks, vergeleken met de state-of-the-art (SOTA) methoden:

• M21: Elimineert TA's door online WCET-uitvoering af te dwingen (hoge gemiddelde latentie).
• M23: Gebruikt veilige analyse zonder TA-eliminatie (hoge bovengrens, TA's bestaan nog).

Resultaten:

• Maximum Reaction Time (MRT): De voorgestelde methode verlaagt de MRT met 9% tot 12% in vergelijking met de veilige analyse-methode (M23), en tot 61% in de beste gevallen.
• Gemiddelde Reactietijd (ART): In vergelijking met de WCET-afdwingende methode (M21) presteert de nieuwe methode aanzienlijk beter, met een verhoging van slechts 2% tot 5% ten opzichte van de originele planning (M23).
• Jitter (Schommeling): De latentie-jitter wordt met 53% tot 68% gereduceerd, wat leidt tot een veel stabielere systeemrespons.
• Geheugenoverhead: De multi-buffer communicatie introduceert slechts een minimale toename in het geheugengebruik.
• Schedulability: Als een taakset oorspronkelijk planbaar was, blijft het dat ook na toepassing van de methode.

5. Significantie

Dit onderzoek is van groot belang voor de ontwikkeling van veiligheidskritieke real-time systemen (zoals in de auto-industrie). Het biedt een praktische oplossing voor het dilemma tussen veiligheid (garanderen van de ergste-case scenario's) en prestatie (gemiddelde responsiviteit).

Door TA's te elimineren zonder de gemiddelde prestaties te offeren, kunnen ingenieurs:

1. Precieze en minder pessimistische bovengrenzen voor latentie berekenen.
2. Betere garanties geven voor de tijdige reactie van het systeem.
3. Systemen ontwerpen die robuuster zijn tegen variaties in uitvoeringstijd, zonder de complexiteit van exhaustive scenario-analyse.

De methode maakt het mogelijk om de theoretische voordelen van TA-vrije systemen te realiseren in de praktijk, zelfs in systemen met variabele uitvoeringstijden.