conference RTSS 25 noanim

Information about conference RTSS 25 noanim

Published on January 14, 2008

Author: Davide

Source: authorstream.com

Content

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?

Related presentations


Other presentations created by Davide

presentation ramsar
09. 01. 2008
0 views

presentation ramsar

law school presentation
13. 01. 2008
0 views

law school presentation

myths of creation gods
16. 04. 2008
0 views

myths of creation gods

dyson 1L
08. 01. 2008
0 views

dyson 1L

rivers2
08. 01. 2008
0 views

rivers2

Methadone Ibogaine
12. 01. 2008
0 views

Methadone Ibogaine

10 11 07Parrish Presentation
15. 01. 2008
0 views

10 11 07Parrish Presentation

Facet5 Professional presentation
17. 01. 2008
0 views

Facet5 Professional presentation

Winter Safety Briefing
18. 01. 2008
0 views

Winter Safety Briefing

The Most Dangerous Job
19. 01. 2008
0 views

The Most Dangerous Job

APUSH Chapter2 2007
20. 01. 2008
0 views

APUSH Chapter2 2007

Weiss presentation
24. 01. 2008
0 views

Weiss presentation

Holocaust Notes
24. 01. 2008
0 views

Holocaust Notes

bigpic
15. 01. 2008
0 views

bigpic

IEDBrief
04. 02. 2008
0 views

IEDBrief

EttiquettePPT
04. 02. 2008
0 views

EttiquettePPT

hybrid toyota stremler
05. 02. 2008
0 views

hybrid toyota stremler

BK12e Ch05 basic
11. 02. 2008
0 views

BK12e Ch05 basic

Flint
10. 01. 2008
0 views

Flint

SFEI Talk 3 01 whitehead
16. 01. 2008
0 views

SFEI Talk 3 01 whitehead

KATHARINE E HAMNETT Presentation
28. 01. 2008
0 views

KATHARINE E HAMNETT Presentation

simplicity and complexity
23. 01. 2008
0 views

simplicity and complexity

MK Comp Test
07. 02. 2008
0 views

MK Comp Test

upload c kutzke 3n1
18. 02. 2008
0 views

upload c kutzke 3n1

VS2008
20. 02. 2008
0 views

VS2008

1ST YEAR LECTURE NOTES
22. 02. 2008
0 views

1ST YEAR LECTURE NOTES

TB020
12. 03. 2008
0 views

TB020

Kiev Business 5 19 06
16. 03. 2008
0 views

Kiev Business 5 19 06

d102
19. 03. 2008
0 views

d102

DelGrosso An Advertisers Guide
19. 03. 2008
0 views

DelGrosso An Advertisers Guide

Fall 2004 PDO
25. 03. 2008
0 views

Fall 2004 PDO

Starting a Business Pres UJCjr
20. 03. 2008
0 views

Starting a Business Pres UJCjr

Appliance Dealer Presentation
10. 04. 2008
0 views

Appliance Dealer Presentation

imm myths PP October
17. 04. 2008
0 views

imm myths PP October

Presentazione BP v 0 42
18. 04. 2008
0 views

Presentazione BP v 0 42

welcomeparty
21. 04. 2008
0 views

welcomeparty

af pres
24. 04. 2008
0 views

af pres

Meeting 3 SFE
12. 02. 2008
0 views

Meeting 3 SFE

OptionsTRIPS
07. 05. 2008
0 views

OptionsTRIPS

global relevance en
08. 05. 2008
0 views

global relevance en

4Triads
17. 01. 2008
0 views

4Triads

W6 closed loop innovations
30. 04. 2008
0 views

W6 closed loop innovations

USA JUDO OCTOBER 06 PRESENTATION
02. 05. 2008
0 views

USA JUDO OCTOBER 06 PRESENTATION

ss 1 013
02. 05. 2008
0 views

ss 1 013

AHeFTSlideDeck
11. 01. 2008
0 views

AHeFTSlideDeck

SBS CCproviders
15. 01. 2008
0 views

SBS CCproviders

LarsV071212
07. 02. 2008
0 views

LarsV071212

Bestpractices062707J ojitAlcazar
04. 02. 2008
0 views

Bestpractices062707J ojitAlcazar

cd wrkshp slide v8
16. 04. 2008
0 views

cd wrkshp slide v8

thermal
16. 01. 2008
0 views

thermal

TVAIC CBA Presentation1
25. 01. 2008
0 views

TVAIC CBA Presentation1

wk2
15. 02. 2008
0 views

wk2

La teoria dell'Agenda Setting
19. 04. 2009
0 views

La teoria dell'Agenda Setting

Mercati Predittivi
25. 11. 2008
0 views

Mercati Predittivi

Book3 Unit2
31. 03. 2008
0 views

Book3 Unit2

Insulated
06. 02. 2008
0 views

Insulated

La creatività nel web 2.0
17. 02. 2007
0 views

La creatività nel web 2.0

Barry
28. 01. 2008
0 views

Barry

Le forme della scienza online
01. 10. 2009
0 views

Le forme della scienza online

Economia Media Sociali
23. 05. 2009
0 views

Economia Media Sociali

oct workshop3
16. 01. 2008
0 views

oct workshop3

Drill Ethics Final
24. 03. 2008
0 views

Drill Ethics Final

Big data for a new sociability
27. 06. 2014
0 views

Big data for a new sociability

CLC History Part II
23. 01. 2008
0 views

CLC History Part II

Me Map
11. 02. 2008
0 views

Me Map

MyVacation
21. 03. 2008
0 views

MyVacation

Aust 090604 Steel
16. 01. 2008
0 views

Aust 090604 Steel