WIXLIB

technische universitätdortmundfakultät für informatikinformatik 12Peter MarwedelTU Dortmund,Informatik 122010/09/20These slides use Microsoft clip arts.Microsoft copyright restrictions apply.Graphics: Alexandra Nolte, Gesine Marwedel, 2003Challenges in ESDesign

Quite a number of challenges, e.g. dependabilityDependability? Non-real time protocols used for real-time applications(e.g. Berlin fire department) Over-simplification of models(e.g. aircraft anti-collision system) Using unsafe systems for safety-critical missions(e.g. voice control system in Los Angeles; 800planes without voice connection to tower for 3 hrstechnische universitätdortmundfakultät fürinformatik p. marwedel,informatik 12, 2010- 35 -

Importanceof EnergyEfficiencyEfficient softwaredesign needed,otherwise, theprice for softwareflexibility cannotbe paid. Hugo De Man,IMEC, Philips, 2007technische universitätdortmundfakultät fürinformatik p. marwedel,informatik 12, 2010- 36 -

It is not sufficient to consider ESjust as a special case of software engineeringEE knowledge must be available,Walls between EE and CS must be torn downCSEEThe same for walls to other disciplines and more challenges .technische universitätdortmundfakultät fürinformatik p. marwedel,informatik 12, 2010- 37 -

technische universitätdortmundfakultät für informatikinformatik 121.3 Design flowsGraphics: Alexandra Nolte, Gesine Marwedel, 2003Design flows

Application KnowledgeHypothetical design Test *ApplicationmappingSystem software(RTOS,middleware, )OptimizationEvaluation & Validation(energy, cost,performance, )* Could beintegratedinto loopGeneric loop: tool chains differ in the number and type of iterationstechnische universitätdortmundfakultät fürinformatik p. marwedel,informatik 12, 2010- 39 -

technische universitätdortmundfakultät fürinformatik p. marwedel,informatik 12, 2010- 40 -

technische universitätdortmundfakultät fürinformatik p. marwedel,informatik 12, 2010- 41 -

technische universitätdortmundfakultät fürinformatik p. marwedel,informatik 12, 2010- 42 -

technische universitätdortmundfakultät fürinformatik p. marwedel,informatik 12, 2010- 43 -

Iterative design (1)- After unrolling loop Example:SpecCtoolstechnische universitätdortmundfakultät fürinformatik p. marwedel,informatik 12, 2010- 44 -

technische universitätdortmundfakultät fürinformatik p. marwedel,informatik 12, 2010- 45 -

Motivation for considering specs Why considering specs? If something is wrong with the specs, then itwill be difficult to get the design right,potentially wasting a lot of time. Typically, we work with models of thesystem under design (SUD) What is a model anyway?technische universitätdortmundfakultät fürinformatik p. marwedel,informatik 12, 2010- 46 -

Requirements for specification techniques (5) Presence of programming elementsExecutability (no algebraic specification)Support for the design of large systems ( OO)Domain-specific supportReadabilityPortability and flexibilityTerminationSupport for non-standard I/O devicesNon-functional propertiesSupport for the design of dependable systemsNo obstacles for efficient implementationAdequate model of computationWhat does it mean “to compute”?technische universitätdortmundfakultät fürinformatik p. marwedel,informatik 12, 2010- 47 -

ModelsDefinition: A model is a simplification of another entity,which can be a physical thing or another model. The modelcontains exactly those characteristics and properties of themodeled entity that are relevant for a given task. A modelis minimal with respect to a task if it does not contain anyother characteristics than those relevant for the task.[Jantsch, 2004]:Which requirements do we have for our models?technische universitätdortmundfakultät fürinformatik p. marwedel,informatik 12, 2010- 48 -

Models and Architectures The system collection of simpler subsystems or pieces There are different methods of decomposing functionality A particular method a modeltechnische universitätdortmundfakultät fürinformatik p. marwedel,informatik 12, 2010- 49 -

Model Taxonomy1. State Oriented (state diagram)for control systems temporal behavior2. Activity Oriented (dataflow graph)for transformational systems like digital signalprocessing3. Structure Oriented (block diagram)4. Data Oriented (entity relationship diagram)for information systems lik databases3. Heterogeneoustechnische universitätdortmundfakultät fürinformatik p. marwedel,informatik 12, 2010- 50 -

technische universitätdortmundfakultät fürinformatik p. marwedel,informatik 12, 2010- 51 -

technische universitätdortmundfakultät fürinformatik p. marwedel,informatik 12, 2010- 52 -

Views of an Elevator Controller If the elevator is stationary and the floor requestedis equal to the current floor, then the elevatorremains idle.If the elevator is stationary and the floor requestedis less than the current floor, then lower theelevator to the requested floor.If the elevator is stationary and the floor requestedis greater than the current floor, then raise theelevator to the requested floor.req floor curr floordirection : downreq floor curr floordirection : idlereq floor curr floordirection : downDownreq floor curr floordirection : idletechnische universitätdortmundloopif (req floor curr floor) thendirection : idle;elsif (req floor curr floor) thendirection : down;elsif (req floor curr floor) thendirection : up;end if;end loop;fakultät fürinformatikreq floor curr floordirection : upreq floor curr floordirection : idleIdlereq floor curr floordirection : up p. marwedel,informatik 12, 2010Up- 53 -

Finite State 2/d1f3r3/ntechnische universitätdortmundfakultät fürinformatik p. marwedel,informatik 12, 2010- 54 -

Finite State MachineStatesA set of transitionsA set of actions S, I, O, f : S I S, h : S I O Set of states : S {s1,s2, ,sn}Set of inputs : I {i1,i2, ,im}Set of outputs : O {o1,o2, ,ok}Next state function : fOutput function : htechnische universitätdortmundfakultät fürinformatik p. marwedel,informatik 12, 2010- 55 -

Meally and Moore MachinesTransition based (Mealy) : h : S I OState based (Moore) : h : S Otechnische universitätdortmundfakultät fürinformatik p. marwedel,informatik 12, 2010- 56 -

FSM with Data PathCurr floor! req floor/output: req floor-curr floor;curr floor: req floorstartS1Curr floor req floor/output: 0 S, I STAT, O A, f, h A set of storage variables : VAR A set of expressions : EXP { f(x, y, z, ) x, y, z, VAR } A set of storage assignments : A { X e X VAR, e EXP } A set of status expressions : STAT { Rel(a, b) a, b EXP} f : S (I STAT) S h : S (I STAT) (O A)technische universitätdortmundfakultät fürinformatik p. marwedel,informatik 12, 2010- 57 -

Problems with FSM and FSMD models Neither the FSM nor the FSMD model is suitable forcomplex systems Neither one supports concurrency and hierarchytechnische universitätdortmundfakultät fürinformatik p. marwedel,informatik 12, 2010- 58 -

Requirements for specification techniques:HierarchyHierarchyHumans not capable to understand systemscontaining more than 5 objects.Most actual systems require more objects Hierarchy Behavioral hierarchyExamples: states, processes, procedures.procprocproc Structural hierarchyExamples: processors, racks,printed circuit boardstechnische universitätdortmundfakultät fürinformatik p. marwedel,informatik 12, 2010- 59 -

Hierarchical Concurrent Finite State Machine(HCFSM) Each set can be decomposed into a set ofsubstates : hierarchy Each set can be decomposed into a set ofconcurrent substates : execute in parallel Language for HCFSM : Statechartstechnische universitätdortmundfakultät fürinformatik p. marwedel,informatik 12, 2010- 60 -

Statechart NotationTransitions If event E occurs in state S and condition C holds thenmake the transition to state T. Actions to be carried out when event E occurs in state S arenormally put into an event-action table rather than part ofthe diagram. The actions could be lengthy and detailed.technische universitätdortmundfakultät fürinformatik p. marwedel,informatik 12, 2010- 61 -

Hierarchical statecharts FSMs are flat. They provide no facility torepresent hierarchies. Details sometimes can to be hidden to portrayhigher level abstraction. Because the arrows go inside node S, events Aand B indicate that there is more detail in stateS. When in state S it is also in either state P orQ. When in state S, move from P to Q on eventC When in state T move to state S and within Sto P on event B. Regardless of states P or Q, on event E,move to T Move to T from Q and S on event Atechnische universitätdortmundfakultät fürinformatik p. marwedel,informatik 12, 2010- 62 -

Clustering Clustering is another form of hierarchy. The advantage is the reduction in the number of arrows. Likely states P and Q are abstractly different from T.technische universitätdortmundfakultät fürinformatik p. marwedel,informatik 12, 2010- 63 -

Three modes of a digital watchtechnische universitätdortmundfakultät fürinformatik p. marwedel,informatik 12, 2010- 64 -

Start and Stop StatesStart states are the simple large dots.Stop states are the encircled dots.A nested statechart should have a start point indicated anda stop state if it's not obvious.technische universitätdortmundfakultät fürinformatik p. marwedel,informatik 12, 2010- 65 -

History mechanism When entering a state that has anested statechart, you may want toresume where you left off when you leftthe enclosing state. The encircled H asthe entry point as below means to startin the state within that was exited. Each level can have its own historymechanism. Each history variablewould be initialized to the start state ofthe level. The encircled H can have an asteriskattached to indicate that the historymechanism is to be used at all levels ofthe hierarchy.technische universitätdortmundfakultät fürinformatik p. marwedel,informatik 12, 2010- 66 -

Concurrency Concurrency refers to the ability to manage more than one statesimultaneously. If a simple FSM is used, the number of states needed is the product ofthe number of states that can be represented in each group separately. Example: Consider the 3 style types -- bold, italics andunderline. These styles can be used in any combination. Bold is on oroff, italics is on or off, underline is on or off. The total number of states is2*2*2 8 and the number of transitions is nearly as bad. Instead, keep each style type as a separate statechart (bold on or off),(italics on or off) and (underline on or off). Each statechart is a simplepair of states. Example: Consider the 4 paragraph positions -- left, center, right andjustified. These types are mutually exclusive but the number of transitionarcs is 10 ( 4*5/2).technische universitätdortmundfakultät fürinformatik p. marwedel,informatik 12, 2010- 67 -

Concurrencytechnische universitätdortmundfakultät fürinformatik p. marwedel,informatik 12, 2010- 68 -

Requirements for specification techniques (2):Component-based design Systems must be designed fromcomponents Must be “easy” to derive behavior frombehavior of subsystems Work of Sifakis, Thiele, Ernst, Concurrency Synchronization and communicationtechnische universitätdortmundfakultät fürinformatik p. marwedel,informatik 12, 2010- 69 -

Structure oriented models : Componentconnectivity diagram Models systems structural view Often used in the later phases of the design processcomponentsProgrammemoryDatamemorySystem busProcessorI/OcoprocessorApplication specifichardwareConnections :buses, wiresSystem block diagramtechnische universitätdortmundfakultät fürinformatik p. marwedel,informatik 12, 2010- 70 -

CCDLeftBusRightBusBARegister fileLIRRIRALURT-level schematictechnische universitätdortmundfakultät fürinformatikGate-level schematic p. marwedel,informatik 12, 2010- 71 -

Data-Oriented Models: Entityrelationship diagramGenerally used in the design of information ncerequestOrderProductRelationship : factrelevant to itsentitiesMight be the nameand addresstechnische universitätdortmundfakultät fürinformatik p. marwedel,informatik 12, 2010- 72 -

Requirements for specification techniques (3):Timing Timing behaviorEssential for embedded systems! Additional information (periods, dependences,scenarios, use cases) welcome Also, the speed of the underlying platform must beknown Far-reaching consequences for design processes!“The lack of timing in the core abstraction (of computerscience) is a flaw, from the perspective of embeddedsoftware” [Lee, 2005]technische universitätdortmundfakultät fürinformatik p. marwedel,informatik 12, 2010- 73 -

Requirements for specification techniques (3):Timing (2)4 types of timing specs required, according to Burns, 1990:1. Measure elapsed timeCheck, how much time has elapsed since last call?executet2. Means for delaying processesttechnische universitätdortmundfakultät fürinformatik p. marwedel,informatik 12, 2010- 74 -

Requirements for specification techniques (3)Timing (3)3. Possibility to specify timeoutsStay in a certain state a maximum time.4. Methods for specifying deadlinesNot available or in separate control file.executettechnische universitätdortmundfakultät fürinformatik p. marwedel,informatik 12, 2010- 75 -

Dependence graphDefinitionSequenceconstraintNodes could be programsor simple operations Def.: A dependence graph is a directed graph G (V,E) inwhich E V V is a partial order. If (v1, v2) E, then v1 is called an immediate predecessorof v2 and v2 is called an immediate successor of v1. Suppose E* is the transitive closure of E.If (v1, v2) E*, then v1 is called a predecessor of v2 andv2 is called a successor of v1.technische universitätdortmundfakultät fürinformatik p. marwedel,informatik 12, 2010- 76 -

Dependence graphTiming informationDependence graphs may contain additional information,for example: Timing informationArrival time deadline]technische universitätdortmundfakultät fürinformatik p. marwedel,informatik 12, 2010- 77 -

Dependence graphI/O-informationtechnische universitätdortmundfakultät fürinformatik p. marwedel,informatik 12, 2010- 78 -

Dependence graphShared resourcestechnische universitätdortmundfakultät fürinformatik p. marwedel,informatik 12, 2010- 79 -

Dependence graphPeriodic schedules A job is single execution of the dependence graph Periodic dependence graphs are infinitetechnische universitätdortmundfakultät fürinformatik p. marwedel,informatik 12, 2010- 80 -

Dependence graphHierarchical task graphstechnische universitätdortmundfakultät fürinformatik p. marwedel,informatik 12, 2010- 81 -

Models of communication Shared memoryComp-1memoryComp-2Variables accessible to several tasks.Model is useful only for local systems.technische universitätdortmundfakultät fürinformatik p. marwedel,informatik 12, 2010- 82 -

Shared memoryPotential race conditions ( inconsistent results possible) Critical sections sections at which exclusive accessto resource r (e.g. shared memory) must be guaranteed.process a {.P(S) //obtain lock. // critical sectionV(S) //release lock}process b {.P(S) //obtain lock. // critical sectionV(S) //release lock}Race-free accessto shared memoryprotected by SpossibleThis model may be supported by: mutual exclusion for critical sections cache coherency protocolstechnische universitätdortmundfakultät fürinformatik p. marwedel,informatik 12, 2010- 83 -

Non-blocking/asynchronous message passingSender does not have to wait until message has arrived;potential problem: buffer overflow send () technische universitätdortmundfakultät fürinformatik receive () p. marwedel,informatik 12, 2010- 84 -

Blocking/synchronous message passingrendez-vousSender will wait until receiver has received message send () technische universitätdortmund receive () fakultät fürinformatik p. marwedel,informatik 12, 2010- 85 -

Extended rendez-vousExplicit acknowledge from receiver required.Receiver can do checking before sendingacknowledgement. send () technische universitätdortmund receive () ack fakultät fürinformatik p. marwedel,informatik 12, 2010- 86 -

Combined models- languages presented later in this chapter - SDLFSM asynchronous message passing StateChartsFSM shared memory CSP, ADAvon Neumann execution synchronous message passing .See also Work by Edward A. Lee, UCB Axel Jantsch: Modeling Embedded Systems and Soc's: Concurrency andTime in Models of Computation, Morgan-Kaufman, 2004technische universitätdortmundfakultät fürinformatik p. marwedel,informatik 12, 2010- 87 -

PtolemyPtolemy (UC Berkeley) is an environment for simulatingmultiple models of computation.http://ptolemy.berkeley.edu/Available examples are restricted to a subset of thesupported models of computation.Newton‘s craddletechnische universitätdortmundfakultät fürinformatik p. marwedel,informatik 12, 2010 Ptolemy simulations- 88 -

Facing realityNo language that meets all language requirements using compromisestechnische universitätdortmundfakultät fürinformatik p. marwedel,informatik 12, 2010- 89 -

SummarySearch for other models of computation models of components- finite state machines (FSMs)- data flow, . models for communication- Shared memory- Message passingtechnische universitätdortmundfakultät fürinformatik p. marwedel,i

Embedded Systems & Cyber-Physical Systems "Dortmund" Definition: [Peter Marwedel] Embedded systems are information processing systems embedded into a larger product Definition: Cyber-Physical (cy-phy) Systems (CPS) are integrations of computation with physical processes [Edward Lee, 2006].