Modeling, Simulation, And Design Of Concurrent Real-Time .

Modeling, Simulation, and Design ofConcurrent Real-Time EmbeddedSystems Using PtolemyEdward A. LeeRobert S. Pepper Distinguished ProfessorEECS DepartmentUC BerkeleyPtutorialEECS 249, Sept. 13, 2012The Ptolemy ProjectThe Ptolemy project studies modeling, simulation,and design of concurrent, real-time, embeddedsystems. The focus is on assembly of concurrentcomponents. The key underlying principle in theproject is the use of well-defined models ofcomputation that govern the interaction betweencomponents. A major problem area beingaddressed is the use of heterogeneous mixtures ofmodels of computation. A software system calledPtolemy II is being constructed in Java, and servesas the principal laboratory for experimentation.Lee, Berkeley 2l 1

History:The project wasThe Ptolemy Projectstarted in 1990, thoughDemographics, 2012its mission and focushas evolvedSponsors:considerably. An opensource, extensible Governmentsoftware frameworkl National Science Foundation(Ptolemy II) constitutesl Army Research Labthe principall DARPA (MuSyC: Multiscale Systems Center)experimentall Air Force Research Lablaboratory. IndustryStaffing:l Bosch 1 professorl National Instruments 9 graduate studentsl SRC (MuSyC: Multiscale Systems Center) 3 postdocsl Thales 2 research staffl Toyota several visitorsLee, Berkeley 3Contributors to Ptolemy IIPrincipal Authors Christopher Brooks Dai Bui Chamberlain Fong John Davis, II Patricia Derler Thomas Huining Feng Mudit Goel Rowland Johnson Bilung Lee Edward Lee Ben Lickly Jie Liu Xiaojun Liu Lukito Muliadi Stephen Neuendorffer John Reekie Neil Smyth Jeff Tsay Yuhong Xiong Haiyang Zheng Gang ZhouOther Contributors Jim Armstrong Vincent Arnould Kyungmin Bae Philip Baldwin Chad Berkley Frederic Boulanger Raymond Cardillo Jannette Cardoso Adam Cataldo Christine Cavanessians Chris Chang Albert Chen Chihong Patrick Cheng Elaine Cheong Colin Cochran Brieuc Desoutter Pedro Domecq William Douglas Johan Eker Thomas Huining Feng Tobin Fricke Teale Fristoe Shanna-Shaye Forbes Hauke Fuhrmann Geroncio Galicia Ben Horowitz Heloise HseEfrat JaegerJörn JanneckZoltan KemenczyBart KienhuisChristoph Meyer KirschSanjeev KohliVinay KrishnanRobert KroegerDaniel Lázaro CuadradoDavid LeeMan-kit (Jackie) LeungMichael LeungJohn LiIsaac LiuAndrew MihalEleftherios MatsikoudisAleksandar NecakovMike Kofi OkyereSarah PackmanShankar RaoBert RodiersRakesh ReddyAdriana RicchiutiSonia SachsIsmael M. SarmientoMichael Shilman Sean SimmonsMandeep SinghMiro SpoenemannPeter N. SteinmetzDick StevensMary StewartNed StoffelManda SutijonoStavros TripakisNeil TurnerGuillaume VibertKees VissersBrian K. VogelYuke WangXavier WarzeeScott WeberPaul WhitakerWinthrop WilliamsEd WillinkMichael WirthlinMichael WetterWilliam WuXiaowen XinPaul YangJames YehNick ZamoraCharlie ZhongLee, Berkeley 4l 2

References Ptolemy project home page:http://ptolemy.org Latest release:http://ptolemy.org/ptolemyII/ptIIlatest/ Latest version in the SVN al/Lee, Berkeley 5ForthcomingBookChapters1. Heterogeneous Modeling2. Building Graphical Models3. Dataflow4. Process Networks and Rendezvous5. Synchronous/Reactive Models6. Finite State Machines7. Discrete Event Models8. Modal Models9. Continuous Time Models10. Cyber-Physical SystemsAppendicesA. ExpressionsB. Signal DisplayC. The Type SystemD. Creating Web PagesLee, Berkeley 6l 3

Getting More Information: DocumentationVolume 1:User-OrientedVolume 2:Developer-OrientedVolume 3:Researcher-OrientedTutorial information: http://ptolemy/conferences/07/tutorial.htmLee, Berkeley 7Outline Building modelsModels of computation (MoCs)Creating actorsCreating directorsSoftware architectureMiscellaneous topicsLee, Berkeley 9l 4

Building Models – Hello WorldLee, Berkeley 10Building more interesting modelsDE Director specifies that thiswill be a discrete-event modelLee, Berkeley 11l 5

Building more interesting modelsModel of regularly spacedevents (e.g., a clock signal).Lee, Berkeley 12Building more interesting modelsModel of irregularly spacedevents (e.g., a failure event).Lee, Berkeley 13l 6

Building more interesting modelsModel of a subsystem thatchanges modes at random(event-triggered) timesLee, Berkeley 14Building more interesting modelsModel of an observersubsystemLee, Berkeley 15l 7

Building more interesting modelsEvents on the two inputstreams must be seen intime stamp order.Lee, Berkeley 16Ptolemy uses Superdense TimeDiscrete event signalscan have a sequence ofdistinct events at a timeinstant.Lee, Berkeley 17l 8

This is a Component TechnologyModel of a subsystem givenas an imperative program.Lee, Berkeley 18This is a Component TechnologyModel of a subsystem givenas a state machine.Lee, Berkeley 19l 9

This is a Component TechnologyModel of a subsystem givenas a modal model.More types of components: Modal models Functional expressions. Submodels in DE Submodels in other MoCsLee, Berkeley 20ContinuousTimeExampleHybrid systems are particularlyclean with superdense time. Theabove signal has multiple values atthe times of the transitions.Lee, Berkeley 21l 10

Superdense Time forContinuous-Time SignalsAt each tag, the signal has exactly one value. At each time point, thesignal has an infinite number of values. The red arrows indicate valuechanges between tags, which correspond to discontinuities. Signals arepiecewise continuous, in a well-defined technical sense.22Lee, Berkeley 22Contrast with Simulink/StateflowIn Simulink, a signal can only have one value at a giventime. Hence Simulink introduces solver-dependent behavior.The simulator engine of Simulink introducesa non-zero delay to consecutive transitions.Transient StatesLee, Berkeley 23l 11

Outline Building modelsModels of computation (MoCs)Creating actorsCreating directorsSoftware architectureMiscellaneous topicsLee, Berkeley 24MoC Example 1:Discrete Events (DE)DE Director implementstimed semantics using anevent queueIn DE, actors send timestamped events to oneanother, and events areprocessed in chronologicalorder.Event sourceSignalput() method inserts a tokeninto the event queue.Time lineLee, Berkeley 25l 12

MoC Example 2:Kahn Process Networks (PN)actor threadsignal streamIn PN, everyactor runs ina thread,with blockingreads ofinput portsand nonblockingwrites tooutputs.reads blockwrites don’tKahn, MacQueen, 1977Lee, Berkeley 26MoC Example 3:Synchronous Dataflow (SDF)In SDF, actors “fire,” and in each firing, consume afixed number of tokens from the input streams, andproduce a fixed number of tokens on the outputstreams.SDF is a special case of PNwhere deadlock andboundedness are decidable. It iswell suited to static schedulingand code generation. It can alsobe automatically parallelized.Lee, Berkeley 27l 13

MoC Example 4:Synchronous/Reactive (SR)At each tick of a global “clock,” everysignal has a value or is absent.Like SDF, SR is decidable and suitable forcode generation. It is harder to parallelizethan SDF, however.SR languages: Esterel, SyncCharts, Lustre,SCADE, Signal.Lee, Berkeley 28MoC Example 5:RendezvousIn Rendezvous, everyactor runs in a thread,with blocking reads ofinput ports and blockingwrites to outputs. Everycommunication is a(possibly multi-way)rendezvous.writes blockCSP (Hoare), SCCS (Milner),Reo (Arbab)actor threadreads blockLee, Berkeley 29l 14

MoC Example 6:Continuous Time (CT)In CT, actors operate oncontinuous-time and/ordiscrete-event signals. AnODE solver governs theexecution.Signal is acontinuous-timefunction.Director includes an ODE solver.Lee, Berkeley 30Ptolemy II Hierarchy Supports HeterogeneityConcurrent actors governed by one model ofcomputation (e.g., Discrete Events).Modal behavior given in another MoC.Detailed dynamics givenin a third MoC (e.g.Continuous Time)This requires a composable abstract semantics.Lee, Berkeley 31l 15

Outline Building modelsModels of computation (MoCs)Creating actorsCreating directorsSoftware architectureMiscellaneous topicsLee, Berkeley 34ActorsLee, Berkeley 35l 16

Ptolemy Components are Actors and ObjectsThe established: Object-oriented:class nameWhat flows throughan object issequential controldatamethodscallreturnThings happen to objectsThe alternative: Actor oriented:actor namedata (state)parametersportsInput dataActors make things happenWhat flows throughan object isevolving dataOutput dataLee, Berkeley 36Actors Ptolemy has a library of predefined actorsJava classes that implement the “executable” interfaceLee, Berkeley 37l 17

Actors can be defined in Java, C, Python, Cal,and MATLABCal, developed by Joern Janneck (nowat Lund) is a language for definingactors that are analyzable for keybehavioral properties.Lee, Berkeley 38Most Actors are Written in JavaLee, Berkeley 39l 18

Simple String Manipulation Actor in Javapublic class Ptolemnizer extends TypedAtomicActor {public Ptolemnizer(CompositeEntity container, String name)throws IllegalActionException, NameDuplicationException {super(container, name);input new TypedIOPort(this, t.setInput(true);output new TypedIOPort(this, tput.setOutput(true);}public TypedIOPort input;public TypedIOPort output;public void fire() throws IllegalActionException {if (input.hasToken(0)) {Token token input.get(0);String result ((StringToken)token).stringValue();result result.replaceAll("t", "pt");output.send(0, new StringToken(result));}}}Lee, Berkeley 40Object Model forExecutable r fire() initialize() postfire() : boolean prefire() : boolean preinitialize() stopFire() terminate() wrapup() getDirector() : Director getExecutiveDirector() : Director getManager() : Manager inputPortList() : List newReceiver() : Receiver outputPortList() : ctorDirectorAtomicActorLee, Berkeley 41l 19

Definition of the Register Actor (Sketch)class Register extends TypedAtomicActor {private Object state;boolean prefire() {Can theif (trigger is known) { return true; }actor fire?}void fire() {if (trigger is present) {send state to output;React to}else {triggerdata input portassert output is absent;input.}}void postfire() {Read theif (trigger is present) {data inputstate value read from data input;and update}the state.}triggerinputportLee, Berkeley 42Outline Building modelsModels of computation (MoCs)Creating actorsCreating directorsSoftware architectureMiscellaneous topicsLee, Berkeley 43l 20

DirectorsLee, Berkeley 44Object Model (Simplified) forCommunication oomExceptionthrowsthrowsNoTokenException get() : Token getContainer() : IOPort hasRoom() : boolean hasToken() : boolean put(t : Token) setContainer(port : ceiverPNReceiver1.1FIFOQueueArrayFIFOQueueLee, Berkeley 45l 21

Object-Oriented Approach to AchievingBehavioral Polymorphism«Interface»Receiver get() : Token getContainer() : IOPort hasRoom() : boolean hasToken() : boolean put(t : Token) setContainer(port : IOPort)These polymorphic methodsimplement the communicationsemantics of a domain in PtolemyII. The receiver instance used incommunication is supplied by thedirector, not by the component.DirectorIOPortRecall: Behavioral polymorphismis the idea that components can bedefined to operate with multiplemodels of computation and multiplemiddleware frameworks.consumeractorproduceractorReceiverLee, Berkeley 46Extension ExerciseBuild a director that subclasses PNDirector to allow portsto alter the “blocking read” behavior. In particular, if a porthas a parameter named “tellTheTruth” then the receiversthat your director creates should “tell the truth” whenhasToken() is called. That is, instead of always returningtrue, they should return true only if there is a token in thereceiver.Parameterizing the behavior of a receiver is a simple formof communication refinement, a key principle in, forexample, Metropolis.Lee, Berkeley 47l 22