CS 452/652 Spring 2022 - Lecture 16
Jun 23, 2022
Train Modelling (cont'd)
- special case of deceleration
- manual experiment
- send stop command when sensor is triggered
- manually measure stop distance
- compute using acceleration model
- experiment with two sensors close to each other?
- experiment by trying to stop right after sensor
- use search algorithm to find right time: could be automated
- stop time + velocity → compute stop distance?
- search algorithm (e.g., binary search) might be brittle and need many experiments
- special case of acceleration
- measure based on known estimate for stop time/distance
- stop at known location, then start
- measure time to sensor
- can compute acceleration
- similar caveat as acceleration measurement: did train reach target velocity?
- stop before reaching target velocity
- manual experiments with different (short) times between start and stop
The material covered in class should be sufficient for train modelling.
However, during the past years, various documents have described train
modelling and calibration in the context of CS 452/652. The various
versions are made available here with the caveat that they might or might
not be helpful:
The Kinematics of Train Calibration (2017)
The Kinematics of Train Calibration (2015)
Reverse Engineering Acceleration/Deceleration(2011)
- 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 catastrophic 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
- internal loops - bounds?
- 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
Reminder: 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?