Deterministic Execution Timing

Component: Core / Real-Time Systems Compliance: ISO 26262 · DO-178C · IEC 61508 Applicability: Real-Time Safety-Critical Systems

1. Purpose

This module defines requirements for deterministic, bounded execution timing of inference primitives. In safety-critical real-time systems, predictable timing is as important as correctness - a late result can be as dangerous as a wrong result.

Critical Requirement: Execution time of core operations must be independent of data values and exhibit minimal variance (jitter) across identical hardware.

2. The Real-Time Problem

2.1 Why Timing Matters

Medical Devices:

• Pacemaker: Must deliver signal within 10ms window
• Surgical robot: Latency > 50ms causes unsafe tremor
• Our Requirement: Predictable, bounded execution time

Automotive Systems:

• Emergency braking: Must complete within 100ms
• Lane keeping: 50ms control loop
• Our Requirement: Zero jitter for control loop stability

Aerospace:

• Flight control: 20ms hard deadline
• DO-178C Level A: Must prove WCET
• Our Requirement: Analyzable worst-case execution time

2.2 Sources of Non-Determinism (That We Avoid)

Dynamic Memory Allocation:

• malloc() latency varies with heap fragmentation
• Garbage collection introduces unpredictable pauses
• Our Solution: Zero dynamic allocation (SRS-001, SRS-003, SRS-006)

Data-Dependent Branching:

• if (value > threshold) break; creates timing variance
• Different execution paths for different data
• Our Solution: Fixed iteration counts, no early exits

Floating-Point Operations:

• IEEE-754 operations vary by value (denormals, NaN handling)
• Hardware optimization units introduce timing variance
• Our Solution: Fixed-point arithmetic only (SRS-002)

Operating System Interference:

• Context switches, interrupts, cache eviction
• ASLR (Address Space Layout Randomization)
• Our Mitigation: Documented, can be controlled by deployment

3. Requirements

3.1 Data-Independent Execution Time

SRS-007.1: Input Independence

Execution time of inference operations shall not depend on input data values.

Rationale:

• Prevents timing side-channel attacks
• Enables WCET analysis
• Required for DO-178C compliance
• Eliminates “Heisenbugs” from timing variance

Implementation: No data-dependent branches in inner loops.

Verification: Timing tests with different input patterns show identical execution time.

SRS-007.2: Fixed Iteration Counts

All loops in inference operations shall have iteration counts determined solely by matrix dimensions, not data values.

Examples:

// COMPLIANT: Loop count = rows × cols (fixed by dimensions)
for (uint16_t i = 0; i < mat->rows; i++) {
    for (uint16_t j = 0; j < mat->cols; j++) {
        // Process element
    }
}

// NON-COMPLIANT: Early exit based on data
for (uint16_t i = 0; i < mat->rows; i++) {
    if (mat->data[i] > threshold) break;  // Data-dependent!
}

Rationale:

• Loop bounds determine execution time
• Fixed bounds enable static analysis
• Simplifies WCET calculation

Verification: Code review confirms all loops have dimension-based bounds.

SRS-007.3: No Dynamic Dispatch

Function calls shall be statically resolved (no function pointers in hot paths unless demonstrably deterministic).

Exception: fx_matrix_apply() takes function pointer but still deterministic (fixed iteration, known function).

Rationale:

• Virtual dispatch can have cache effects
• Static calls enable compiler optimization
• Predictable instruction cache behavior

Verification: Static analysis confirms call graph.

3.2 Timing Predictability

SRS-007.4: Bounded Jitter

For identical hardware and identical dimensions, execution time variance (jitter) shall be minimal (<5% of mean execution time).

Definition:

Jitter = max(execution_times) - min(execution_times)
Acceptable: Jitter < 0.05 × mean

Note: This excludes OS-level interrupts (which can be controlled in real deployment).

Rationale:

• Control loops require predictable timing
• Jitter causes instability in feedback systems
• Required for hard real-time classification

Verification: Run operation 10,000 times, measure jitter.

SRS-007.5: WCET Analyzability

Code structure shall enable worst-case execution time (WCET) analysis using static analysis tools.

Requirements:

• No recursion
• All loops have statically determinable bounds
• No dynamic memory allocation
• Call graph is statically analyzable

Tools: aiT, SWEET, OTAWA, or manual analysis

Rationale:

• DO-178C Level A requires WCET proof
• ISO 26262 ASIL-D requires timing analysis
• IEC 61508 SIL 3/4 requires bounded timing

Verification: WCET analysis report available.

3.3 Performance Characteristics

SRS-007.6: Time Complexity Documentation

Each operation shall document its time complexity in Big-O notation.

Examples:

• Matrix multiplication: O(M × N × P)
• Convolution: O(OH × OW × KH × KW)
• ReLU: O(M × N)

Rationale:

• Enables system-level timing analysis
• Helps users predict performance
• Required for real-time scheduling

Verification: Documentation reviewed and tested.

4. Timing Analysis

4.1 Matrix Multiplication (fx_matrix_mul)

Time Complexity: O(M × N × P)

• M = rows of A
• N = cols of A = rows of B
• P = cols of B

Iteration Count:

Total iterations = M × N × P
For 10×10 × 10×10: 10 × 10 × 10 = 1000 iterations

Data Independence: ✅

• Loop bounds fixed by dimensions
• No early exits
• No data-dependent branches

WCET: Deterministic (M × N × P × T_MAC)

• T_MAC = time for one multiply-accumulate

4.2 Convolution (fx_conv2d)

Time Complexity: O(OH × OW × KH × KW)

• OH, OW = output height, width
• KH, KW = kernel height, width

Iteration Count:

Total iterations = OH × OW × KH × KW
For 14×14 output, 3×3 kernel: 14 × 14 × 3 × 3 = 1764 iterations

Data Independence: ✅

• Loop bounds fixed by dimensions
• No early exits
• No data-dependent branches

WCET: Deterministic (OH × OW × KH × KW × T_MAC)

4.3 ReLU (fx_relu)

Time Complexity: O(M × N)

Iteration Count:

Total iterations = M × N
For 10×10 matrix: 100 iterations

Note: Contains if (data[i] < 0) branch

• Branch predictor may cause small variance
• Modern CPUs: <1% timing difference
• Acceptable for most real-time systems
• Critical systems: Use branchless version

WCET: Nearly deterministic (M × N × T_CMP)

5. Benchmark Methodology

5.1 Test Setup

Hardware: Document CPU, cache configuration, frequency

Software: Document OS, kernel version, compiler flags

Isolation:

• Disable frequency scaling
• Pin process to single core
• Disable interrupts if possible
• Warm up caches before measurement

5.2 Measurement Procedure

1. Warm-up: Run operation 1000 times (load caches)
2. Measurement: Run operation 10,000 times
3. Record: Each individual execution time
4. Analysis: Calculate min, max, mean, jitter

5.3 Acceptance Criteria

Pass Criteria:

• Mean execution time documented
• Jitter < 5% of mean (excluding OS interrupts)
• Min/Max ratio < 1.05
• No outliers > 2× median

Fail Criteria:

• Jitter > 10% of mean
• Bimodal distribution (indicates hidden states)
• Increasing trend (memory leak)

6. Commercial Value

6.1 The Triple Threat

1. Bit-Perfect Results (Correctness)

• Same input → same output, always
• Proven by SRS-001 through SRS-006

2. Traceable Requirements (Compliance)

• Complete audit trail
• Requirements → Code → Tests
• Ready for regulatory submission

3. Zero-Jitter Execution (Predictability)

• Deterministic timing
• No “Heisenbugs”
• WCET analyzable

Value: Companies pay $500K+ for this combination.

6.2 Certification Advantages

DO-178C (Aerospace):

• Level A requires WCET proof ✅
• Structural coverage easily achieved ✅
• No dynamic behavior to analyze ✅

ISO 26262 (Automotive):

• ASIL-D requires timing predictability ✅
• Deterministic behavior proven ✅
• No timing side-channels ✅

IEC 62304 (Medical):

• Class C requires risk analysis ✅
• Predictable timing reduces risk ✅
• Formal verification possible ✅

6.3 Competitive Advantage

vs. TensorFlow Lite:

• TensorFlow: Data-dependent optimization (non-deterministic)
• Us: Fixed execution path (deterministic) ✅

vs. ONNX Runtime:

• ONNX: Dynamic memory allocation (timing variance)
• Us: Pre-allocated buffers (predictable) ✅

vs. PyTorch Mobile:

• PyTorch: Python runtime overhead (jitter)
• Us: Pure C, zero overhead (zero jitter) ✅

7. Timing Side-Channel Resistance

7.1 Security Benefit

Constant-Time Operations:

• Prevents timing attacks on sensitive data
• Important for medical privacy (HIPAA)
• Required for defense applications

Example Attack Prevented:

// VULNERABLE: Timing reveals if tumor detected
if (tumor_probability > threshold) {
    allocate_large_buffer();  // Takes longer!
    detailed_analysis();
}

// SECURE: Constant time regardless of detection
result = classify_region();  // Always same time

7.2 Privacy Implications

In medical AI:

• Processing time should not reveal diagnosis
• Constant-time prevents information leakage
• Our architecture naturally constant-time

8. Implementation Guidelines

8.1 Writing Deterministic Code

DO:

• Use dimension-based loop bounds
• Avoid break in inner loops
• Use fixed-point arithmetic
• Pre-allocate all buffers

DON’T:

• Use malloc in hot paths
• Have data-dependent branches in loops
• Use floating-point operations
• Call functions with unknown timing

8.2 Testing Determinism

// Test pattern
uint64_t times[ITERATIONS];
for (int i = 0; i < ITERATIONS; i++) {
    start = get_time();
    operation();
    end = get_time();
    times[i] = end - start;
}

// Analyze
uint64_t min = times[0];
uint64_t max = times[0];
uint64_t sum = 0;
for (int i = 0; i < ITERATIONS; i++) {
    if (times[i] < min) min = times[i];
    if (times[i] > max) max = times[i];
    sum += times[i];
}
uint64_t mean = sum / ITERATIONS;
uint64_t jitter = max - min;

// Verify
assert(jitter < mean * 0.05);  // Jitter < 5%

9. Future Work

SRS-007.7: (Planned) Branchless ReLU Implementation

For ultra-critical systems, implement ReLU without branches:

// Branchless ReLU
fixed_t relu_branchless(fixed_t x) {
    fixed_t mask = x >> 31;  // Sign bit
    return x & ~mask;        // Zero if negative
}

SRS-007.8: (Planned) WCET Analysis Reports

Generate formal WCET analysis using static analysis tools.

SRS-007.9: (Planned) Timing Guarantees

Provide documented timing guarantees per operation:

• Matrix mul: X ns per MAC
• Conv2D: Y ns per MAC
• Platform-specific characterization

10. References

• DO-178C - Software Considerations in Airborne Systems
• ISO 26262-6:2018 - Road vehicles functional safety (software)
• IEC 61508 - Functional safety of electrical/electronic systems
• MISRA-C:2012 - Guidelines for embedded C
• Liu & Layland (1973) - “Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment”

11. Revision History

Document Classification: Technical Specification
Approval Status: Approved for Implementation
Next Review: 2026-04-15