CS 452/652 Winter 2023 - Lecture 16

Train Modelling (cont'd)

Stop Distance

• special case of deceleration
• manual experiment
  • send stop command when sensor is triggered
  • manually measure stop distance

Stop Time

• 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

Start

• 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?

Short Moves

• stop before reaching target velocity
• manual experiments with different (short) times between start and stop

Earlier Documents

Stopping (2016)
The Kinematics of Train Calibration (2017)
The Kinematics of Train Calibration (2015)
Reverse Engineering Acceleration/Deceleration(2011)

Latency 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 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 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
  • internal loops - bounds?
• 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 for later high-arrival
• alternative model: Critical Instant
  • assume all events happen at the same time; all tasks ready
  • trace priority execution

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

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?