Worst-Case Execution Time (WCET)

WCET analysis produces a pessimistic bound, meaning the calculated time is guaranteed to be greater than or equal to the actual worst-case time. This overestimation, or pessimism, is a deliberate safety margin. The goal is to minimize this margin while maintaining the guarantee. Key approaches include:

• Static Analysis: Analyzes the program's control flow graph and hardware model (cache, pipeline) without executing it.
• Measurement-Based Analysis: Executes the program on hardware with varied inputs to find the longest observed time, but cannot guarantee all paths are explored.

Accurate WCET requires detailed models of the microarchitecture, as features designed to improve average-case performance create timing uncertainty. Critical elements to model include:

• Caches: Predict whether an access is a hit or miss.
• Pipeline Hazards: Data and control dependencies that cause stalls.
• Branch Prediction: Mispredictions add significant penalty cycles.
• Memory Contention: Access delays from shared buses or DRAM refresh. Analysts often use abstract interpretation to safely over-approximate the effects of these hardware features on execution time.

The core challenge is identifying the worst-case execution path (WCEP) through the program's code. This is an NP-hard problem due to loops and complex conditionals. Analysis involves:

• Loop Bound Analysis: Determining the maximum number of iterations for each loop, often via manual annotation or static analysis.
• Infeasible Path Elimination: Identifying program paths that are logically impossible (e.g., if (x>10) ... else if (x>20)...) to reduce pessimism.
• Context Sensitivity: Analyzing function calls within their calling context to avoid overestimation from analyzing functions in isolation.

WCET is not an isolated metric; it is the fundamental input for real-time scheduling analysis. Schedulers like Rate-Monotonic (RM) or Earliest-Deadline-First (EDF) use the WCET of each task to verify schedulability—the guarantee that all tasks will meet their deadlines. The relationship is formalized in equations like the Liu and Layland utilization bound. A task's WCET, combined with its period and deadline, determines if the system can be certified for real-time operation.

These are distinct metrics serving different purposes. Average-Case Execution Time (ACET) is a statistical measure of expected performance, useful for throughput and battery life estimation. WCET is a hard, provable upper bound for safety assurance. In TinyML, a model might have an ACET of 15ms but a WCET of 45ms due to a rare, computationally intensive code path. System design must accommodate the WCET, while product specifications may cite the ACET.

WCET analysis relies on specialized toolchains. Prominent commercial and research tools include:

• aiT by AbsInt: Uses abstract interpretation for static analysis of binaries.
• Bound-T by Tidorum: Performs static flow analysis with hardware modeling.
• OTAWA: An open-source framework for WCET computation.
• Rapita Systems' RVS: Provides verification suites for avionics standards. These tools are essential for compliance with safety standards like DO-178C (avionics), ISO 26262 (automotive), and IEC 61508 (industrial), which mandate evidence of timing predictability.

Deterministic execution is a system property where identical inputs always produce identical outputs with identical timing behavior across repeated runs. This is a prerequisite for reliably calculating WCET. In TinyML, achieving determinism requires controlling for:

• Fixed-point arithmetic instead of floating-point.
• Static memory allocation to avoid non-deterministic heap behavior.
• Disabling interrupts or using time-triggered architectures during critical inference sections. Without deterministic execution, WCET analysis becomes probabilistic rather than absolute.

Inference latency is the total time delay from input presentation to prediction output for a single model inference. While WCET is the maximum possible latency under all conditions, average latency is the typical time. Key components measured include:

• Data preprocessing (e.g., sensor normalization).
• Model forward pass execution.
• Post-processing of results. For real-time systems, the worst-case latency (WCET) must be less than the system's deadline to guarantee timely responses.

Tail latency refers to the high-percentile latencies in a distribution, such as the 95th (P95) or 99th (P99) percentile. It represents the worst delays experienced by a small fraction of inferences. In cloud or statistical systems, optimizing P99 latency is common. However, for safety-critical real-time systems, the 100th percentile—the absolute worst-case—is the defining metric. WCET analysis aims to bound this tail to a known, safe maximum, moving beyond statistical guarantees to absolute ones.

End-to-end latency is the total time from the initial physical event (e.g., sensor trigger) to the final system action (e.g., actuator command). WCET for a model is only one component of this chain. The full pipeline includes:

• Sensor sampling and readout time.
• Data buffering and transfer (e.g., over I2C/SPI).
• Inference WCET.
• Decision logic and actuation time. System designers must perform a worst-case path analysis on the entire pipeline to ensure all deadlines are met.

Static Timing Analysis (STA) is a method from electronic design automation that analyzes a digital circuit's timing without simulation. Adapted for software, static WCET analysis uses abstract interpretation of the machine code to compute an upper bound on execution time. It considers:

• All possible program paths via control-flow graph analysis.
• Processor pipeline hazards and cache behavior (using abstract cache models).
• Loop bounds (often provided by the developer via annotations). This formal method provides a provable safe bound, essential for certification in avionics and automotive (ISO 26262).