03. Specification and Modeling

• begin of system design

• -> defines:

  • functionality of system

  • extra/non-functional constraints / properties (e.g. latency, power disspiatoni)

    • -> should comply to standard (compliance…)

  • often done in textural description

• useful during design process

• formally describe the problem (since natural language usually amboguous and incomplete)

• cover different system aspects (function, extra-functional properties)

• from system specificatoin

• executable specificaiton

• during the design process

• yes!

• -> large variety in

  • funcitonlaity

  • characteristics of different fileds of applications

• require broad range of modeling techniques

  
  

• state models

• behavioral models

• (real-)time models

• early stages of design

  • -> have informal description of product (specification)

  • -> convert into formal, executable specification (model)

    • can either be entire system or constituent parts…

  • -> does not yet contain any inforamtion regarding eventual implementation

• executable model is machine readable

  • -> can be simulated

  • -> is used to advance understanding of systems behavior

  • -> may also later on be used as input for implemenation and/or synthesis of the system

• later design and implementation phases progressively introduce concrete components and their accompanying interconnectis into the model

• successively split system into simpler, interconnected subsystems

• model:

  • describes how a system functions

• architecture:

  • describes how system is implemented

• different models reveal different aspects of a system over different design phases

• => allows different characteristics of model to become visible

• demonstrate timing of the system:

  • -> transitions between states

• can descirbe “procedural” input-output relationship of a system

Architecture

• what parts of the overall functionality is implemented in dedicated hardware

• which and how many programmable processor cores are instantiated

• what partes are executed in SW on which programmable processor cores?

• memory subsytem (and parameters, plus data mapping)

• how are the hardware components (accel, proc, memory) inteconnected ?

  • topology, interconnect parameters like data path widths, frequenceis

• input for the subsequent implementation phase

  • implementation of HW

  • programming of SW

  • interface

• paralell development of HW and SW components of a system

conventional:

• SW development on running HW

modern:

• development of cycle-/instruction-accurate HW model

• -> used as the focus of SE development

• -> while actual HW is being implemented…

• shorter time to market

• formal (unambiguous) description of a system or subsystem

• limited to description of certain characteristics, without unneccesary detail (abstraction)

• complete description of a system or subsystem

• partial description of a system

• understandable and simple to modify

• orthogonal (senkrecht)

• -> levels of abstrction: how much detal with which a model is described

• design views: either behavioral, structural or geometrical/physical perspective

• state oriented

  • control-flow dominant

• activity-oriented

  • data-flow dominant

• structure oriented

• time oriented

• data oriented

• combination oriented

• models of computation

• -> definition of a component

  • e.g. subtroutine, process, thread

• mechanisms used to interact between components

  • e.g. message passing

• possibly: what components know about each other

  • e.g. using global variables

• communicating finite state machines (CFSM)

• classical state machines

• kahn process networks (KPN)

• synchronous data flow (SDF)

• component connection diagram (CCD)

• discrete-time event model

• contoinuous-time event model (differential equations)

• message sequence charts

• vertices:

  • operations

  • tasks

  • states

  • processes

• edges:

  • dependencies

  • data-flow

  • control-flow

  • transitions

• data dependencies

• control dependencies

• data flow graphs (DFGs)

• finite state machines (FSMs)

• control and data flow graphs (CDFGs)

• task and problem graphs

• set of states (vertices)

• connected by state transitions (edges)

• that are triggered by external events

• describing control units

• such as reactive real-time controllers

• in which the systems timing (latency) is most important aspect to be modeled

• modeling synchronous sequential circuits in ASICs

• 6-tuple

• (I, O, S, R, f, g)

• I - input alphabet

• O - output alphabet

• S - set of states

• R TM S - set of initial states

• f: SxI -> S - transition funciton

• g - output mapping funciton

  • moore: o = g(s)

  • mealy: o = g(s, i)

moore:

• output depends on

  • current state

mealy:

• output depends on

  • current state

  • current input

• directed, possible cyclic graph

• vertices:

  • atomic chunks of code without jumps - (basic blocks)

  • or jump targets

• edges:

  • jumps in the control flow

• transition triggered

  • solely by completion of preceding block

• !! only single branch is taken to transition from one block to the next

  • different to DFG!!!

• e.g. data flow graph DFG

• -> describe system as set of actions

• which access data or resolve dependencies

• describing transformaitonal systems

  • e.g. digital signal processing

• in which data is passed through tansfer funciotn at fixed rate

• data flow graph

• describe data dependencies between a number of operations

• directed, acyclic graph

• vertices:

  • opraionts or tasks

• edges:

  • data flow

• solely by availability of data

• no

• -> but can depict parallelization

• dataflow model which is used for

  • capturing data stream applications

• directed graph of nodes (actors) which represent parallel running processes Pi

• processes exchange data via communication channels wiht FIFO buffers

• one reading and one writing process per channel

• reads from channel buffers are blocking if FIFO is empty

• writes to channel buffers are non-blockng (can always be done)

• channel buffers are unbounded (may grow to infinity)

• on modeled functionality

• read from / write to only one input / output channel

• (one token of unspecified data amount)

• yes

• -> for given set of input data (tokens)

• -> KPNs will always generate same result

• independently of speed and execution order of the processes

• due to reads from empty buffers

• in reality -> memory is finite

• => bounded buffers

1. true deadlock:

   • read from empty buffer (KPN read semantics)

2. artificial deadlock

   • write into full buffer (bounded memories)

• scheduler

• -> manages execution order of processes

• -> thereby indirectly manages buffer fill levels

• boundedness:

  • does schedule require infinite memory?

• completeness:

  • do all processes get to run indefinitely?

• non-termination:

  • will there be deadlocks?

• no not in general !

• data driven scheduling

• parks’ algorithm

• execute a process as soon as tokens are available

• does not necessarily find schedule with bounded buffers

• -> even if one exists!

1. start with buffer size 1 for all channels

2. apply data driven schedule

3. if termination occurs -> increase buffer size by 1

4. repeat

• finds a schedule with bounded buffers if one exists

• prefers complete unbounded execution

• to a partial, bounded execution

-> not guaranteed to find bounded and complete schedule!

• restricted form of KPNs

• -> amount of data consumed (i_j) / produced (o_j) by each process known a priori

• channel buffers are bounded with valid periodic schedules

• atomic firing of processes Pn (consume i_n tokens and produce o_n tokens)

• can only fire if all required tokens i_n are available on the inputs

• through analysis

• -> determine number of firings per process in the schedule

• identify valid channel buffer sizes

• => use balance equation

1. create balance equations

   • i.e. 2 qA = 3qB

   • qB = qC

   • => 2qA = 3qB = 3qC (consistent as it has a nonzero solution…)

1. find smallest integer function for the firing qi

   1. set an arbitrary qPi to one e.g. qA = 1

      • solve for the rest, here i.e. qB = qC = 2/3

   2. compute least common multiple of all denominators (l = lcm(1,3,3) = 3) (zeug unter bruchstrich…)

   3. multiply all qPi by l

1. -> possible schedules: AAABBCC,AAABCBC,AABABCC,AABACBC,AABCABC

   • -> every schedule has differetn (bounded) buffer requirements…

• perform analysis to decide on schedule (after which the SDF returns into initial state…)

• -> initialize tokens required for each loop (-> i.e.

• tokens increase / decrease…

• describe system as set of physical components / modules ant their interconnections

• FSM / DFG: describe funcitonality of a system

• structure oriented models: depict physical configuration of a system

• - describe a system as hierarchy of data structures, attributes or class interitance

• best suited for describing systems in which structural representaiton of data more important than systems functionality (e.g. databases)

• merges the benefits of two or more simpler models

• -> usually allowing for complete descrption of a complex system with a single document…

• => well sutied for describing systems that span a large design domain, i.e. real-time systems or ASICs

• combined models

• -> simultaneously describe control structure (e.g. branches) and data dependencies

• CFG:

  • state machine representing sequential control flow

  • operations contained within block are expanded in form of a DFG

• DFG:

  • NOP operations provide uniform entry and exit potin for each block

• => control flow to enforce conditional node execution

• => DFG to perform operations on data

• task graph for an IP router with VoIP

• abstract system model

• purely functional simulation/model to verify the integrity of all sub-systems

• concurrency

• state transitions

• hierarchy

• program structure

• completion

• communication

• synchronization

• exception handling

• non-determinism

• timing

• often more simple and concise to portray behavior of system as set of multiple sub-behaviors

• -> e.g. easier to have 2 FSM having N1 and N2 states than single FSM with up to N1xN2 states…

• operations and assignments given without a specific order

• -> order determined solely by data dependencies

• single assignment rule:

  • every variable appears no more than once on the left hand side of an assignment

• explicit control instructions (fork-join, concurrent behavior) determine the order of operations

• -> appplied at the process- and statement level

! concurrent tasks may contain sequential sub-tasks…!

• set of interconnected states, functions or modes

• -> transitions between funciotns/modes are dependent on events or conditions

• system with N states can have up to N^2 state transitions

• real systems usually too complex to be viewed or understood in their entierty

• splitting system into successively smaller, modular sub-systems

  • -> developers can focuse on single sub-system at a time

  • developers do not need in-depth understanding of entire sytem

• also allows for:

  • reuse of task, object and variable names at different levels

• structural hierarchy

• behavioral hierarchy

• system modeled in structure-oriented fashion

• -> every component made up of a sub-structure of interconnected components at lower levels of abstraction

• simplifies the process of developing refinements for existing components

• used to divide one function (behavior) into multiple sub-functions

  • which can be either sequential or conurrent

• sequential splitting of function can be represented as either set of procedures or set of state machines

• many functoins and system behaviors can be best described using sequential algorithms

  • i.e. after system has be split into smaller and smaller sub-systems

  • -> allows developer to explicitly state order in which to execute instructions…

• such programm constructs include:

  • assignments

  • branches

  • iterations

  • subroutines…

• to a processe’s ability to indicate that it is completed

• or the ability of other processes to notice its completion…

• all calculations made by this proces have been completed

• all variables have been assigned their new value

• sub-systems (functions or processes) of a system usually communicate with each other…

• shared-memory communication

• message passing communicatoin

• sending process writes global variable into shared resources (i.e. shared memory)

• all receiving processes can now read this variable (good broadcasting properties)

• any necessary synchronization must be accomplished separately

• create a ready_flag and set it to 1…

• -> other process: include condition for ready_flag before referencing the piece of shared memory…

• data exchanged between processes using a communication channel to pass messages

• process can acces the channel using send/receive primitives

• at higher level of abstraction -> channels are virtual entities and not bound by implementation details…

• can be unidirectional or bidirectional using

  • point to point

  • or

  • shared (address) bus infrastructure

• blocking

• non-blocking

• sending process waits until

  • receiving process has accepted (or is ready to provide) the data

  • -> required synchronization of the processes prior to transfer

=> blocking := WAIT for other side to signal readyness… (thus process blocks until it was able to send / receive data…)

• sending process writes data into queue and immediately continues processing

• receiving process can then read data from queue at its leisure…

• => allows for sending and receiving process to work independently

  • but requires additional memory (queues)

• blocking: synchronous communicaiton

• non-blocking: asynchronous communication

• concurrent processes in system are almost never completely independent of each other

• -> every process can generate data and/or events that must be handled by other processes

• to exchange data

• to execute certain operations across multiple processes at the same time

• control-oriented synchronization

• data-oriented synchronization

• control structure of behavioral description determines the synchronization between processes

• synchronization accomplished using inter-process communicatoin

  • using shared memory

  • using message passing

• certain events such as

  • a reset

  • CPU interrupt

• to deal with certain events that cause preemtive termination of a process

• => i.e. exceptions…

• control is passed to pre-defined exception handling routine

• by means of state change at higher levels

• -> resulting in the interruption or terminaiton of a systems regular behavior

• ocasisonaly it may be unclear which of several state transitions or sequences of operations are best suited for applicaiton at hand

• -> designer would like to put off final decision about which implementaiton to choose until later in the process

• -> non-determinism allows the specification of multiple options

• at end of desing process all non-determinisms have to be eliminated