ShawnSchaffertAndBru noSinopoli

Comparing Models of Computation for Real-time, Distributed Control Systems: 

Comparing Models of Computation for Real-time, Distributed Control Systems Shawn Schaffert Bruno Sinopoli

Outline: 

Outline The real-time, distributed control problem The two car example Analysis of different models Implementation Conclusion

The real-time, distributed control problem: 

The real-time, distributed control problem

The Real-time, Distributed Control Dream: 

The Real-time, Distributed Control Dream Model for classical control Model for discrete world High level: networking, synchronization Low level: task scheduling Verification tools Code-generation -> implementation

Key Ideas: 

Key Ideas Applications Environmental monitoring (distributed sensing) Rocket vibration damping (distributed actuation) Two car example (distributed sensing and actuation) Algorithms Routing Localization Synchronization Control Scheduling Mechanisms Communication network Local & global clocks Distributed dynamical environment Local shared resources Dynamic node creation/destruction Properties Controller stability Fault tolerance Task deadlines Network reliability Synchronization error

The two car example: 

The two car example

System Structure: 

System Structure Distributed wireless sensor nodes detect the coming cars and their directions, communicate with neighbor nodes, and control the cars to avoid collision

Analysis of different models: 

Analysis of different models

Models: 

Models Continuous Time Timed Multitasking Continuous Time with Discrete Event Globally Asynchronous Locally Synchronous (GALS) Other models Giotto SDF SR

Continuous Time (CT): 

Continuous Time (CT) This model captures: Control stability This model doesn’t capture: Synchronization Scheduling Network

Timed Multitasking (TM): 

Timed Multitasking (TM) One purpose: analysis of scheduling of shared resources Isn’t interesting for the two car example Could be useful for general problems Higher level provides bounds on event inter-arrival time This level guarantees task deadlines are met

Continuous Time with Discrete Event (CT-DE): 

Continuous Time with Discrete Event (CT-DE) Our models captures Radio communication Broadcast channel Radio delay Radio collision Distributed environment Nodes are separate entities Communication only via radio channel Distributed sensor readings

Continuous Time with Discrete Event (CT-DE): 

Continuous Time with Discrete Event (CT-DE) Our model could be extended to capture: Improved radio model Radio noise Low radio bandwidth – collision window based on packet size Local and global clocks Nodes query environment individually Hardware-in-the-loop Problems with the CT-DE model: Dynamic node creation/destruction seems cumbersome Does not model task level Scale to 100 or 1000 nodes

Esterel: 

Esterel Synchronous language Control-dominated software or hardware reactive system High-level programming using functional models C code is automatically generated

Design Flow: 

Design Flow Implement functional specification using high-level language (Esterel) Directly generate function modules(C code) through compiling Build interfaces and wrappers needed by the execution platform

High-Level Description: 

High-Level Description module extnode: Loop await CAR; emit TO_N end loop module Cluster: loop await FROM_NC; await E; emit CAR_TURN each L || loop await E; emit TO_NC each L || loop await T; emit CAR_TURN; emit TO_NC each L module intnode: loop await [CAR or FROM_N]; present CAR then present FROM_N then emit T else [await FROM_N; emit L] end present else present FROM_N then [await CAR; emit E] end present end present end loop

The real World: 

The real World Esterel –A <modulename>.strl

Synch vs Asynch: 

Synch vs Asynch In Synchronous models “Reaction based” Absence () can be sensed and used in the specification of behaviors A global tick exists In Asynchronous models “Signal based” No global tick Reaction cannot be observed anymore  cannot be sensed

Endochronicity: 

Endochronicity define desynchronization of P This map is unique but not invertible “If P satisfies a special condition called endochrony, then there exists a unique such that holds”

Endochronicity: Meaning: 

Endochronicity: Meaning STS Set of variables W’ clock inference of W ( ) if knowing presence/absence of allows deriving the presence absence of If then the process is endochronous

Isochronicity: 

Isochronicity In general WE want the equality to hold (no spurious behavior due to asynchronous communication) “If (P,Q) satisfies a special condition called isochrony then the equality indeed holds”

Isochronicity: Meaning: 

Isochronicity: Meaning

Our Case: 

Our Case module extnode: Loop await CAR; emit TO_N end loop This is endochronous: module intnode: loop await [CAR or FROM_N]; present CAR then present FROM_N then emit T else [await FROM_N; emit L] end present else present FROM_N then [await CAR; emit E] end present end present end loop This is not endochronous since CAR and FROM_N are not related: if (messagePayload_ptr->sourceNodeID == DUMB_NODE) { internal_I_FROM_N()} else if (messagePayload_ptr->sourceNodeID == OTHER_SMART_NODE) { internal_I_FROM_NC()} internal()

Make it Endochronous: 

Make it Endochronous Simple solution: add signaling For each signal add a boolean flag which indicates presence/absence During the execution the functions will wait for all the flags and then will react Very expensive in general: If (flag==T) { set_input;set_arrived} If (all_flag) {react;reset_arrived}

Some discussion: 

Some discussion External node: Code size overhead 7% Internal node Code size overhead 18% The external node is already endochronous Internal node needs some extra signaling

Implementation: 

Implementation

Conclusion: 

Conclusion Ptolemy Allows accurate model for entire system Network, dynamics, scheduling User friendly (intuitive) Scalability issues Code generation for sensor networks? Esterel Limited modeling (only behavioral level) Verifiability Code generation

Proposed Design Methodology: 

Proposed Design Methodology Hardware

END: 

END Acknowledgements: Professor Lee for stimulating discussion Alessandro Pinto, Yanmei Li for their contribution in the Esterel implementation