CS 452/652 Winter 2022 - Lecture 22
March 4, 2022
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
- 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 execution time (WCET)
- identify (safety-)critical paths or worst-case execution path (WCEP)
- busy: memory pipelining/caching/sharing effects?
- cache: no miss, one miss, all misses -> reality?
- block: contributes to latency, but not throughput
- 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
- 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
- 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
- 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?