CS 452/652 Winter 2022 - Lecture 22

Execution Time Analysis

• think of program as graph
  • computation & termination vs. control/service loop
• control/service loop: throughput vs. latency
  • timing of edges: busy vs. block
  • throughput: compare average busy cost of paths to offered load / arrival rate
  • latency: take into account busy and blocked cost

Average Latency?

• no balancing between lower and higher latencies
  • service loop: outliers change mean - potentially skews utility
    • late response is useless, regardless of how late
  • control loop: mean masks outliers - potentially hides problem
    • how often a train enters a critical track section matters more than how much it overshoots
• analysis must work with latency distribution
  • service loop: high order percentile (tail latency)
  • control loop: worst-case latency
• rare exceptions where average latency is relevant

Worst-Case Latency

• worst-case execution time (WCET)
• identify (safety-)critical paths or worst-case execution path (WCEP)
• uncertainty
  • busy: memory pipelining/caching/sharing effects?
    • cache: no miss, one miss, all misses -> reality?
  • block: contributes to latency, but not throughput
• queueing
  • standing queue - contributes to latency, but does not affect throughput
  • queueing theory: latency increases as arrivals approach capacity
    • cannot "save" capacity during low-arrival times

Automatic Analysis

• static analysis: NP-hard
• experimental measurement: no worst-case guarantee!
• hybrid: measure single feasible paths (SFP) & analyze combination
• automatic analysis: loop counts, recursion depth? needs bounds/annotations

Train Control

• preemptive scheduling: shortcut to loop start
• small tasks: shorter graph edges
• critical path: sensor event → action → effect
• preemption: keep uninterruptible kernel execution short!
• priorities: support resource management via scheduling

Task Priorities

• priorities are a mechanism to organize various components of a computer system
• critical path: sensor → uart → supervisor → engineer → track → uart → command
  • plus requisite notifiers, couriers, etc.
• critical path? everything is important! what can be bumped down?
  • computation such as routing and path planning?
• at low utilization: priorities not as critical
• priority determines worst-case latency
• low-level tasks: low priority could loose interrupts or input
  • use higher priority and/or buffer

Train Control Caveat

• track interface is half-duplex
• alternate between reading requested sensor data and sending commands
• train control commands delay sensor loop - options:
  • single-bank sensor queries - budget for train commands
  • add uncertaintly to sensor timing based on number of previous train commands
  • ignore additional error, because it is small?