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?