DRAFTS Distributed Real time Applications Fault Tolerant Scheduling Claudio Pinello pinello eecs berkeley edu 1 DRAFTS Motivation Drive by Wire applications 2 DRAFTS Motivation No rods increased passive safety Interior design freedom BMW Daimler Cytroen Chrysler Bertone SKF etc 3 DRAFTS Problem Overview Safety system failure must be as unlikely as in traditional systems Fault tolerance redundancy is key 4 DRAFTS Faults SW faults bugs can be reduced by disciplined coding even better by code generation HW faults harsh environment many units 50 uProcessors in a car subsystems with 10 15 uP s 5 DRAFTS Fault Model Silent Faults faults result in omission errors Detectable Faults faults result in detectably corrupted data e g CRC protected channels Non silent Faults faults result in value errors Byzantine Faults malicious attacks non silent faults unbounded delays etc 6 DRAFTS Software Redundancy Space redundancy execute replicas on different HW send results on different multiple channels 7 DRAFTS N copies Solution Pros Plant Plant design once Abstractinput ArbiterBest AbstractOut CoarseCTRL Plant FineCTRL Abstractinput ArbiterBest AbstractOut CoarseCTRL FineCTRL Abstractinput ArbiterBest AbstractOut CoarseCTRL Iterator Cons FineCTRL Iterator Iterator N x costs 1x speed Pros Plant reduced cost Abstractinput ArbiterBest AbstractOut CoarseCTRL FineCTRL Cons Iterator degradation 1x speed multiple designs Plant Plant Abstractinput Abstractinput AbstractOut AbstractOut Iterator Iterator 8 DRAFTS Redundancy Management Managing a distributed system with multiple results requires careful programming keep N copies synchronized exchange and apply results detect and isolate faults recover 9 DRAFTS Possible solutions Off The Shelf solutions TTP based architectures FT CORBA middleware Synthesis Debugged and portable libraries Development tools 10 DRAFTS Automotive Domain Production costs dominate NRE costs multi vendor supply chain interest in full utilization of architectures Validation and certification are critical validate process validate product 11 DRAFTS Shortcomings of OTS solutions TTP proprietary communication network network redundancy default is 2 way active replication potential underutilization of resources FT CORBA fairly large overhead middleware 12 DRAFTS Synthesis based Solution Synthesize only needed glue code at the extreme get rid of OS Customizable replication mechanisms use passive replicas Treat architecture as a distributed execution machine exploit parallelism to speed up execution 13 DRAFTS Schedule Synthesis Plant Abstractinput ArbiterBest CoarseCTRL CPU CPU CPU CPU CPU CPU AbstractOut FineCTRL Mapping Iterator Sens Input Sens Input Sens Sens Input CoarseCTRL CPU ArbiterBest SensFineCTRL CPU Plant Sens Input CoarseCTRL CPU CoarseCTRL ArbiterBest Output Act ArbiterBest Output Act CoarseCTRL FineCTRL Iterator Iterator CPU Output Iterator Act 14 CPU ArbiterBest Output CPU Act DRAFTS Synthesis based Solution Enables fast architecture exploration 15 DRAFTS Contributions Programming Model Metropolis platform Schedule synthesis tool and optimization strategy Verification Tools 16 DRAFTS Programming Model Definition of a programming model that Is amenable to specifying feedback controllers Is convenient for analysis simulation and synthesis Supports degraded functionality accuracy Supports redundancy Deterministic 17 DRAFTS Static Data flow Model A Pros Deterministic behavior Actors perform deterministic computation no internal states Requires all inputs to fire an actor B C Shortcomings Requires all inputs to fire an actor but source actors may fail Explicit parallelism Good for periodic algorithms 18 DRAFTS Pendulum Example Plant BangBang Abstractinput ArbiterBest CoarseCTRL AbstractOut FineCTRL Linear Iterator 19 DRAFTS Model Extensions Node Criticality Node Typing sensor input arbiter etc Some types input and arbiter can fire with missing inputs Tokens have Epoch and Valid fields Specialized single place buffer links manage redundant sources and destinations 20 DRAFTS Data Tokens Epoch Data Epoch Valid iteration index of the periodic algorithm Actors ask for current inputs Using we can account for missing results self synchronization 21 DRAFTS Data Tokens Valid Data Epoch Valid Valid models the effect of fault detection True data was received produced correctly False data was not received on time or was corrupted Firing rules and actors may use it to change their behavior 22 DRAFTS FTDataFlow modeling Metropolis used as framework to develop the set of tools FTDF is a platform library in Metropolis modeling simulation fault injection supports semi automatic replication results visualization 23 DRAFTS Actor Classes DF SENactor sensor actor DF INactor input actor DF AINactor abstract input actor DF FUNactor data flow actor DF ARBactor arbiter actor DF AOUTactor abstract output actor DF OUTactor output actor DF ACTactor actuator actor DF MEM state memory DF Injector fault injection 24 DRAFTS Pendulum Example Plant Abstractinput ArbiterBest CoarseCTRL AbstractOut FineCTRL Inject Iterator 25 DRAFTS Simulation output Fault 26 DRAFTS Summary on FTDF Extended SDF to deal with missing redundant inputs different criticality functionality types Developed Metropolis platform modeling simulation fault injection visualization of results support for adding redundancy 27 DRAFTS Architecture Model Architecture Connectivity bipartite graph Computation and communication times actor cpu data channel matrices of execution and transmission times 28 CPU CPU CPU CPU CPU CPU Same as SynDEx model DRAFTS Fault Behavior Failure patterns Subsets of Arch Graph that may fail simultaneously For each failure pattern specify criticality level i e which functionalities must be guaranteed typically for empty failure pattern all functionality must be guaranteed 29 DRAFTS Synthesis Problem Given Application Architecture Fault Behavior Derive Plant Abstractinput CoarseCTRL ArbiterBest CPU CPU CPU CPU CPU CPU AbstractOut FineCTRL Mapping Iterator SensInput CPU CoarseCTRL SensInput CPU CPU CoarseCTRL Plant Sens Input Sens Input Sens CoarseCTRL CoarseCTRL ArbiterBest Output Act ArbiterBest Output Act FineCTRL Iterator Redundancy Schedule ArbiterBest Iterator Iterator CPU Output Act 30 SensFineCTRL CPU ArbiterBest Output CPU Act DRAFTS Pendulum Example Sens Act Actuator Sensor location Tolerate any single fault CPU Sens CPU Sens Act CPU empty all functionality one CPU may drop FineController and sensor actuator on
View Full Document
Unlocking...