conference RTSS 25 noanim

Enforcing Safety of Real-Time Schedules on Contemporary Processors using a Virtual Simple Architecture (VISA): 

Enforcing Safety of Real-Time Schedules on Contemporary Processors using a Virtual Simple Architecture (VISA) Aravindh Anantaraman*, Kiran Seth†, Eric Rotenberg*, Frank Mueller‡ Center for Embedded Systems Research (CESR) *Electrical & Computer Eng./ ‡ Computer Science North Carolina State University † Qualcomm. Inc

Complexity in Hard-Real-Time Systems: 

Complexity in Hard-Real-Time Systems Worst-case execution time (WCET) crucial for schedulability analysis Contemporary processors are extremely complex Branch prediction, pipelining, out-of-order execution Improve average case performance WCET unknown Complex processors not used in real-time systems

Virtual Simple Architecture (VISA): 

Virtual Simple Architecture (VISA)

Virtual Simple Architecture (VISA): 

Virtual Simple Architecture (VISA) Task X WCET = 10 ms

Virtual Simple Architecture (VISA): 

Virtual Simple Architecture (VISA) Task X WCET = 10 ms

Virtual Simple Architecture (VISA): 

Virtual Simple Architecture (VISA) Task X WCET = 10 ms Task X WCET = ?? (unreliable)

Virtual Simple Architecture (VISA): 

Virtual Simple Architecture (VISA) Task X WCET = 10 ms

Virtual Simple Architecture (VISA): 

Virtual Simple Architecture (VISA) Task X WCET = 10 ms Virtual Simple Architecture: give illusion of simple processor

Virtual Simple Architecture (VISA): 

Virtual Simple Architecture (VISA) Task X WCET = 10 ms Virtual Simple Architecture: give illusion of simple processor Task X WCET = 10 ms

Virtual Simple Architecture (VISA): 

Virtual Simple Architecture (VISA) Task X WCET = 10 ms Virtual Simple Architecture: give illusion of simple processor Task X WCET = 10 ms Novel non-literal approach to static timing analysis Use simple processor as proxy for complex processor Dynamically guarantee WCET

Virtual Simple Architecture (VISA): 

Virtual Simple Architecture (VISA) Task X WCET = 10 ms Virtual Simple Architecture: give illusion of simple processor Task X WCET = 10 ms

Virtual Simple Architecture (VISA): 

Virtual Simple Architecture (VISA) Task X WCET = 10 ms Virtual Simple Architecture: give illusion of simple processor Task X WCET = 10 ms

Virtual Simple Architecture (VISA): 

Virtual Simple Architecture (VISA) Task X WCET = 10 ms Virtual Simple Architecture: give illusion of simple processor Task X WCET = 10 ms

Virtual Simple Architecture (VISA): 

Virtual Simple Architecture (VISA) Task X WCET = 10 ms Virtual Simple Architecture: give illusion of simple processor Task X WCET = 10 ms

Virtual Simple Architecture (VISA): 

Virtual Simple Architecture (VISA) Task X WCET = 10 ms Virtual Simple Architecture: give illusion of simple processor Task X WCET = 10 ms

Virtual Simple Architecture (VISA): 

Virtual Simple Architecture (VISA) Task X WCET = 10 ms Virtual Simple Architecture: give illusion of simple processor Task X WCET = 10 ms

Virtual Simple Architecture (VISA): 

Virtual Simple Architecture (VISA) Task X WCET = 10 ms Virtual Simple Architecture: give illusion of simple processor Task X WCET = 10 ms

Virtual Simple Architecture (VISA): 

Virtual Simple Architecture (VISA) Task X WCET = 10 ms Virtual Simple Architecture: give illusion of simple processor Task X WCET = 10 ms Exploit dynamic slack for power/energy savings, other functionality

Previous Approaches: 

Previous Approaches Avoid complexity VISA allows complex processors to be used Disable complexity during hard-real-time tasks VISA disables complexity only when problematic Continue research in timing analysis WCET of simple proxy improved

VISA Overview: 

VISA Overview Provides real-time guarantees for contemporary processors Approach Execute tasks optimistically on complex mode Gauge interim progress Safe back-up mode for anomalous scenarios

Dual-Mode VISA Processor: 

Dual-Mode VISA Processor Static prediction

Dual-Mode VISA Processor: 

Dual-Mode VISA Processor Static prediction

Dual-Mode VISA Processor: 

Dual-Mode VISA Processor Static prediction

Dual-Mode VISA Processor: 

Dual-Mode VISA Processor Static prediction

Dual-Mode VISA Processor: 

Dual-Mode VISA Processor Static prediction

VISA in Action: 

VISA in Action simple mode

VISA in Action: 

VISA in Action simple mode complex mode

VISA in Action: 

VISA in Action WCEC Non-speculative simple mode simple mode complex mode

VISA in Action: 

VISA in Action WCEC 1 Non-speculative simple mode simple mode complex mode

VISA in Action: 

VISA in Action WCEC 1 2 Non-speculative simple mode simple mode complex mode

VISA in Action: 

VISA in Action WCEC 1 2 3 Non-speculative simple mode simple mode complex mode

VISA in Action: 

VISA in Action WCEC 1 2 3 4 Non-speculative simple mode simple mode complex mode

VISA in Action: 

VISA in Action WCEC 1 2 3 4 WCEC’ Non-speculative simple mode Successful speculation in complex mode simple mode complex mode

VISA in Action: 

VISA in Action WCEC 1 2 3 4 chk1 chk2 chk3 chk4 WCEC’ Non-speculative simple mode Successful speculation in complex mode simple mode complex mode

VISA in Action: 

VISA in Action WCEC 1 2 3 4 chk1 chk2 chk3 chk4 WCEC’ Non-speculative simple mode Successful speculation in complex mode headstart simple mode complex mode

VISA in Action: 

VISA in Action WCEC 1 2 3 4 chk1 chk2 chk3 chk4 WCEC’ 1 Non-speculative simple mode Successful speculation in complex mode 1 simple mode complex mode

VISA in Action: 

VISA in Action WCEC 1 2 3 4 chk1 chk2 chk3 chk4 WCEC’ 1 2 Non-speculative simple mode Successful speculation in complex mode 1 simple mode complex mode

VISA in Action: 

VISA in Action WCEC 1 2 3 4 chk1 chk2 chk3 chk4 WCEC’ 1 2 3 Non-speculative simple mode Successful speculation in complex mode 1 simple mode complex mode

VISA in Action: 

VISA in Action WCEC 1 2 3 4 chk1 chk2 chk3 chk4 WCEC’ 1 2 3 4 Non-speculative simple mode Successful speculation in complex mode 1 simple mode complex mode

VISA in Action: 

VISA in Action WCEC 1 2 3 4 chk1 chk2 chk3 chk4 WCEC’ 1 2 3 4 dynamic slack Non-speculative simple mode Successful speculation in complex mode 1 $$$ cash back! simple mode complex mode

VISA in Action: 

VISA in Action WCEC 1 2 3 4 WCEC’ Non-speculative simple mode Misspeculation in complex mode simple mode complex mode

VISA in Action: 

VISA in Action WCEC 1 2 3 4 chk1 WCEC’ 1 Non-speculative simple mode 1 Misspeculation in complex mode simple mode complex mode

VISA in Action: 

VISA in Action WCEC 1 2 3 4 chk1 chk2 WCEC’ 1 Non-speculative simple mode 1 Misspeculation in complex mode (2) simple mode complex mode

VISA in Action: 

VISA in Action WCEC 1 2 3 4 chk1 chk2 WCEC’ 1 Non-speculative simple mode 1 Misspeculation in complex mode 2 (2) simple mode complex mode

VISA in Action: 

VISA in Action WCEC 1 2 3 4 chk1 chk2 WCEC’ 1 Non-speculative simple mode 1 Misspeculation in complex mode 2 3 (2) simple mode complex mode

VISA in Action: 

VISA in Action WCEC 1 2 3 4 chk1 chk2 WCEC’ 1 Non-speculative simple mode 1 Misspeculation in complex mode 2 3 4 (2) simple mode complex mode

VISA in Action: 

VISA in Action WCEC 1 2 3 4 chk1 chk2 WCEC’ 1 Non-speculative simple mode 1 Misspeculation in complex mode 2 3 4 (2) simple mode complex mode

Contributions: 

Contributions Minimize headstart overhead Novel zero-overhead VISA approach – dynamic headstart accrual Extend VISA to multi-tasking systems Energy evaluation in multi-tasking systems

Headstart Assessment: 

Headstart Assessment simple mode complex mode

Headstart Assessment: 

Headstart Assessment simple mode complex mode

Headstart Assessment: 

Headstart Assessment simple mode complex mode

Headstart Assessment: 

Headstart Assessment simple mode complex mode

Headstart Assessment: 

Headstart Assessment simple mode complex mode

Headstart Assessment: 

Headstart Assessment simple mode complex mode

Headstart Assessment: 

Headstart Assessment simple mode complex mode

Headstart Assessment: 

Headstart Assessment simple mode complex mode

Explicit Padding Approach: 

Explicit Padding Approach Pad task WCEC with max headstart amount Give padded WCEC to schedulability analysis

Dynamic Headstart Accrual: 

Dynamic Headstart Accrual Harness naturally occurring dynamic slack in simple mode as headstart  switch to complex mode

Dynamic Headstart Accrual: 

Dynamic Headstart Accrual simple mode complex mode

Dynamic Headstart Accrual: 

Dynamic Headstart Accrual 1 2 3 4 Non-speculative simple mode WCEC simple mode complex mode

Dynamic Headstart Accrual: 

Dynamic Headstart Accrual 1 2 3 4 Non-speculative simple mode WCEC WCEC Successful speculation in complex mode simple mode complex mode

Dynamic Headstart Accrual: 

Dynamic Headstart Accrual 1 2 3 4 Non-speculative simple mode WCEC 1 WCEC Successful speculation in complex mode simple mode complex mode

Dynamic Headstart Accrual: 

Dynamic Headstart Accrual 1 2 3 4 Non-speculative simple mode WCEC 1 WCEC Successful speculation in complex mode simple mode complex mode

Dynamic Headstart Accrual: 

Dynamic Headstart Accrual 1 2 3 4 Non-speculative simple mode WCEC 1 2 WCEC Successful speculation in complex mode simple mode complex mode

Dynamic Headstart Accrual: 

Dynamic Headstart Accrual 1 2 3 4 Non-speculative simple mode WCEC 1 2 WCEC Successful speculation in complex mode simple mode complex mode

Dynamic Headstart Accrual: 

Dynamic Headstart Accrual 1 2 3 4 Non-speculative simple mode WCEC 1 2 3 WCEC Successful speculation in complex mode chk3 simple mode complex mode

Dynamic Headstart Accrual: 

Dynamic Headstart Accrual 1 2 3 4 Non-speculative simple mode WCEC 1 2 3 4 WCEC Successful speculation in complex mode chk3 chk4 simple mode complex mode

Dynamic Headstart Accrual: 

Dynamic Headstart Accrual 1 2 3 4 Non-speculative simple mode WCEC 1 2 3 4 WCEC Successful speculation in complex mode chk3 chk4 dynamic slack simple mode complex mode

Dynamic Headstart Accrual: 

Dynamic Headstart Accrual 1 2 3 4 Non-speculative simple mode WCEC 1 2 3 4 WCEC Successful speculation in complex mode chk3 chk4 simple mode complex mode First simple mode, then complex mode No explicit headstart padding

Dynamic Headstart Accrual: 

Dynamic Headstart Accrual 1 2 3 4 Non-speculative simple mode WCEC WCEC Misspeculation in complex mode simple mode complex mode

Dynamic Headstart Accrual: 

Dynamic Headstart Accrual 1 2 3 4 Non-speculative simple mode WCEC 1 WCEC Misspeculation in complex mode simple mode complex mode

Dynamic Headstart Accrual: 

Dynamic Headstart Accrual 1 2 3 4 Non-speculative simple mode WCEC 1 2 WCEC Misspeculation in complex mode simple mode complex mode

Dynamic Headstart Accrual: 

Dynamic Headstart Accrual 1 2 3 4 Non-speculative simple mode WCEC 1 2 WCEC chk3 Misspeculation in complex mode (3) simple mode complex mode

Dynamic Headstart Accrual: 

Dynamic Headstart Accrual 1 2 3 4 Non-speculative simple mode WCEC 1 2 WCEC chk3 Misspeculation in complex mode (3) 3 simple mode complex mode

Dynamic Headstart Accrual: 

Dynamic Headstart Accrual 1 2 3 4 Non-speculative simple mode WCEC 1 2 WCEC chk3 Misspeculation in complex mode (3) 3 4 simple mode complex mode

Dynamic Headstart Accrual: 

Dynamic Headstart Accrual 1 2 3 4 Non-speculative simple mode WCEC WCEC Flexible: fluidly switch between simple and complex simple mode complex mode

Dynamic Headstart Accrual: 

Dynamic Headstart Accrual 1 2 3 4 Non-speculative simple mode WCEC 1 WCEC Flexible: fluidly switch between simple and complex simple mode complex mode

Dynamic Headstart Accrual: 

Dynamic Headstart Accrual 1 2 3 4 Non-speculative simple mode WCEC 1 2 WCEC Flexible: fluidly switch between simple and complex simple mode complex mode

Dynamic Headstart Accrual: 

Dynamic Headstart Accrual 1 2 3 4 Non-speculative simple mode WCEC 1 2 WCEC Flexible: fluidly switch between simple and complex simple mode complex mode

Dynamic Headstart Accrual: 

Dynamic Headstart Accrual 1 2 3 4 Non-speculative simple mode WCEC 1 2 WCEC chk3 Flexible: fluidly switch between simple and complex (3) simple mode complex mode

Dynamic Headstart Accrual: 

Dynamic Headstart Accrual 1 2 3 4 Non-speculative simple mode WCEC 1 2 WCEC chk3 Flexible: fluidly switch between simple and complex (3) 3 simple mode complex mode

Dynamic Headstart Accrual: 

Dynamic Headstart Accrual 1 2 3 4 Non-speculative simple mode WCEC 1 2 WCEC chk3 Flexible: fluidly switch between simple and complex (3) 3 simple mode complex mode

Dynamic Headstart Accrual: 

Dynamic Headstart Accrual 1 2 3 4 Non-speculative simple mode WCEC 1 2 WCEC chk3 chk4 Flexible: fluidly switch between simple and complex (3) 3 4 simple mode complex mode

Dynamic Headstart Accrual: 

Dynamic Headstart Accrual 1 2 3 4 Non-speculative simple mode WCEC 1 2 WCEC chk3 chk4 Flexible: fluidly switch between simple and complex (3) 3 4 simple mode complex mode Re-enable speculation after missed checkpoint

Explicit Padding vs. Dynamic Headstart Accrual: 

Explicit Padding vs. Dynamic Headstart Accrual Explicit padding +Guaranteed speculation Inflated WCETs  Unschedulable task-sets Dynamic headstart accrual +Schedulability unaffected +Flexible switching Dependent on dynamic slack in simple mode

VISA in Multi-Tasking Systems: 

VISA in Multi-Tasking Systems Gauging mechanism (watchdog counter) disrupted Adapt for multi-tasking Interruption  save watchdog counter Resumption  restore watchdog counter

Easy Integration in Multi-Tasking Systems : 

Easy Integration in Multi-Tasking Systems System software components depend on WCET EDF scheduler, DVS scheduler, etc. VISA preserves WCET abstraction We demonstrate VISA in a hard-real-time system with Look-Ahead EDF-DVS [Pillai&Shin’01]

Look-Ahead EDF-DVS in VISA: 

Look-Ahead EDF-DVS in VISA Simple processor VISA (Explicit padding) VISA (Dynamic headstart accrual)

Experimental Methodology: 

Experimental Methodology Cycle-accurate microarchitecture simulator Wattch power models to measure power/energy [Brooks00] 6 C-lab real-time benchmarks

Energy Savings: 

Energy Savings

Average Frequencies: 

Average Frequencies

High Utilization Task-sets: 

High Utilization Task-sets Worst-case utilization (unpadded WCETs) = 1.0 Cannot use explicit padding  task-set unschedulable Dynamic headstart accrual works!

Energy Savings (U = 1): 

Energy Savings (U = 1)

Coarse-grained vs. fine-grained sub-tasks: 

Coarse-grained vs. fine-grained sub-tasks Coarse-grained sub-tasks 1 1 2 3 4 5 6 7 8 2 3 4 Fine-grained sub-tasks

Fine-grained vs. coarse-grained sub-tasks: 

Fine-grained vs. coarse-grained sub-tasks

Summary: 

Summary VISA enables use of complex processors in safe real-time systems Headstart calculation Novel zero-overhead VISA speculation technique dynamic headstart accrual VISA extended to multi-tasking systems 19% – 58% energy savings with respect to explicitly-safe simple processor

Questions?: 

Questions?