How is the design flow at system level?
What is a system specification?
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
WHat are system models?
useful during design process
formally describe the problem (since natural language usually amboguous and incomplete)
cover different system aspects (function, extra-functional properties)
From what are system models generated?
from system specificatoin
What is another word for system models?
executable specificaiton
When are system models refined?
during the design process
Do we need a broad range of modeling techniques?
yes!
-> large variety in
funcitonlaity
characteristics of different fileds of applications
require broad range of modeling techniques
What different type of (overarching) modeling techniques do we use?
state models
behavioral models
(real-)time models
How is the general flow of specification model and implementation?
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
How is the implemenation of a system accomplished?
successively split system into simpler, interconnected subsystems
What is the difference between a model and an architecture?
model:
describes how a system functions
architecture:
describes how system is implemented
Why do we have different models (types)?
different models reveal different aspects of a system over different design phases
=> allows different characteristics of model to become visible
What do state-based models make visible?
demonstrate timing of the system:
-> transitions between states
What do statealgorithmic models make visible?
can descirbe “procedural” input-output relationship of a system
What is the result of the HW/SW codesign process? What does it describne?
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
What is the architecture used for?
input for the subsequent implementation phase
implementation of HW
programming of SW
interface
What do virtual prototypes allow for?
paralell development of HW and SW components of a system
How does conventional and modern HW/SW development compare?
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…
What is an advantage of modern HW/SW development (in parallel)?
shorter time to market
What are the characteristics of a model?
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
how are models located w.r.t. levels of abstraction an ddesign views?
orthogonal (senkrecht)
-> levels of abstrction: how much detal with which a model is described
design views: either behavioral, structural or geometrical/physical perspective
What different model classes do we have?
state oriented
control-flow dominant
activity-oriented
data-flow dominant
structure oriented
time oriented
data oriented
combination oriented
What has to be defined for a model (MoC)?
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
What MoC do state-oriented models have?
communicating finite state machines (CFSM)
classical state machines
What MoC do activity-oriented models have?
kahn process networks (KPN)
synchronous data flow (SDF)
What MoC do structure-orietned models have?
component connection diagram (CCD)
What MoC do time-oriented models have?
discrete-time event model
contoinuous-time event model (differential equations)
What MoC is possible in a combination model approach?
message sequence charts
How can graphs be used in models? What can vertices and edges represent?
vertices:
operations
tasks
states
processes
edges:
dependencies
data-flow
control-flow
transitions
What type of dependenceis rae there?
data dependencies
control dependencies
What are some common graph models?
data flow graphs (DFGs)
finite state machines (FSMs)
control and data flow graphs (CDFGs)
task and problem graphs
How can a FSM look like?
How can a CFG look like?
How can a Task and problem graph look like?
How can a DFG look like?
How are systems in state oriented models (e.g. finite automaton or FSM) described?
set of states (vertices)
connected by state transitions (edges)
that are triggered by external events
What are state oriented models best suited for?
describing control units
such as reactive real-time controllers
in which the systems timing (latency) is most important aspect to be modeled
For what specific task is state-oriented model most popular?
modeling synchronous sequential circuits in ASICs
What do Finite State Machines consist of ?
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)
What is the difference between moore and mealy state machines?
moore:
output depends on
current state
mealy:
current input
What are CFGs?
directed, possible cyclic graph
atomic chunks of code without jumps - (basic blocks)
or jump targets
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!!!
What are activity oriented models?
e.g. data flow graph DFG
-> describe system as set of actions
which access data or resolve dependencies
What are activity oriented models best suited for?
describing transformaitonal systems
e.g. digital signal processing
in which data is passed through tansfer funciotn at fixed rate
What are DFGs?
data flow graph
describe data dependencies between a number of operations
directed, acyclic graph
opraionts or tasks
data flow
By what are DFGs calculations triggered?
solely by availability of data
can DFGs portray branches in code?
no
-> but can depict parallelization
What are khan process networks (KPN)?
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
How does a graphical depiction of a KPN look like?
What are the properties of channelsn in KPNs?
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 what are the properties of processes in KPNs dependant?
on modeled functionality
What can processes do at each time instance?
read from / write to only one input / output channel
(one token of unspecified data amount)
Are KPN deterministic?
yes
-> for given set of input data (tokens)
-> KPNs will always generate same result
independently of speed and execution order of the processes
When might a true deadlock happen in KPNs?
due to reads from empty buffers
What is a problem of KPNs w.r.t. buffers?
in reality -> memory is finite
=> bounded buffers
What type of deadlocks can occur in KPNs?
true deadlock:
read from empty buffer (KPN read semantics)
artificial deadlock
write into full buffer (bounded memories)
What is required to avoid deadlocks?
scheduler
-> manages execution order of processes
-> thereby indirectly manages buffer fill levels
What aspects of practical feasability do KPN schedules indicate?
boundedness:
does schedule require infinite memory?
completeness:
do all processes get to run indefinitely?
non-termination:
will there be deadlocks?
Does one know a-priori whether a feasible schedule exist for a given KPN?
no not in general !
What scheduling methods exist in KPNs?
data driven scheduling
parks’ algorithm
What is data-driven scheduling? What is a disadvanage?
execute a process as soon as tokens are available
does not necessarily find schedule with bounded buffers
-> even if one exists!
How does parks algorithm (scheduling) work? What is an advantage?
start with buffer size 1 for all channels
apply data driven schedule
if termination occurs -> increase buffer size by 1
repeat
finds a schedule with bounded buffers if one exists
What does parks algorithm prefer (w.r.t. found schedules)?
prefers complete unbounded execution
to a partial, bounded execution
-> not guaranteed to find bounded and complete schedule!
What are synchronous/static dataflows?
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
What are rules of DF (synchronous data flows)?
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
How can one determine valid peiodic schedules of SDF?
through analysis
-> determine number of firings per process in the schedule
identify valid channel buffer sizes
=> use balance equation
What steps to take in SDF analysis?
create balance equations
i.e. 2 qA = 3qB
qB = qC
=> 2qA = 3qB = 3qC (consistent as it has a nonzero solution…)
find smallest integer function for the firing qi
set an arbitrary qPi to one e.g. qA = 1
solve for the rest, here i.e. qB = qC = 2/3
compute least common multiple of all denominators (l = lcm(1,3,3) = 3) (zeug unter bruchstrich…)
multiply all qPi by l
-> possible schedules: AAABBCC,AAABCBC,AABABCC,AABACBC,AABCABC
-> every schedule has differetn (bounded) buffer requirements…
How can one kick-start the execution of a SDF?
perform analysis to decide on schedule (after which the SDF returns into initial state…)
-> initialize tokens required for each loop (-> i.e.
What might happen if we have an inconsistenc balance equation?
tokens increase / decrease…
What are structure oriented models?
describe system as set of physical components / modules ant their interconnections
How do structural models differ to FSM and DFG?
FSM / DFG: describe funcitonality of a system
structure oriented models: depict physical configuration of a system
What are data oriented models? What are they best suited for?
- 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)
What are combined models?
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
What are control/dataflow graphs (CDFG)?
combined models
-> simultaneously describe control structure (e.g. branches) and data dependencies
What are the elements of CDFG?
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
What is an exemplary CDFG at system level?
task graph for an IP router with VoIP
abstract system model
purely functional simulation/model to verify the integrity of all sub-systems
What model characteristics / properties are usually used to allow for the (more efficient) description of a system’s behavior?
concurrency
state transitions
hierarchy
program structure
completion
communication
synchronization
exception handling
non-determinism
timing
What is the advantage of modeling concurrency?
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…
How to model data-oriented concurrency?
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
What is control oriented concurrency?
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…!
How does cuda-style fork-join work?
How does symmetric-multiprocess
How can systems be modeld using state transitions?
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
Why do we employ hierarchical modeling?
real systems usually too complex to be viewed or understood in their entierty
What does hierarchical modelling allow for?
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
What types of hierarchy do we differentiate?
structural hierarchy
behavioral hierarchy
What is structural 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
What is behavioral-/functional hierarchy?
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
What can program structures/constructs be used for?
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…
What does completion refer to?
to a processe’s ability to indicate that it is completed
or the ability of other processes to notice its completion…
When has a process completed?
all calculations made by this proces have been completed
all variables have been assigned their new value
Why is communicatoin important in system modeling?
sub-systems (functions or processes) of a system usually communicate with each other…
Based on which two fundamental principles is communication usually build upon?
shared-memory communication
message passing communicatoin
How does shared memory communicatoin work?
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
How can one indiceate that i.e. shared memroy can be accessed by other processes? (synchronization)
create a ready_flag and set it to 1…
-> other process: include condition for ready_flag before referencing the piece of shared memory…
How does message passing communicatoin work?
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
For message passing, what to important properties are differentiated w.r.t. the communication channel?
blocking
non-blocking
How does a blocking transfer in message passing communication work?
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…)
How does a nob-blocking transfer in message passing communication work?
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)
What is the basic difference between blocking and non-blocking message passing communication?
blocking: synchronous communicaiton
non-blocking: asynchronous communication
Why is synchronization an important tool in system modeling?
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
For what must processes be synchronized with each other?
to exchange data
to execute certain operations across multiple processes at the same time
What methods for synchronization exist / did we discuss?
control-oriented synchronization
data-oriented synchronization
How does control-oriented synchronization work?
control structure of behavioral description determines the synchronization between processes
How does data-oriented synchronization work?
synchronization accomplished using inter-process communicatoin
using shared memory
using message passing
How does data-oriented synchronizuation using status deteciton work?
How does data-oriented synchronizuation using shared events work?
How does data-oriented synchronizuation using shared variable work?
What can necessitate the abrupt (preemtive) termination of a process?
certain events such as
a reset
CPU interrupt
Why do we need exception handling?
to deal with certain events that cause preemtive termination of a process
=> i.e. exceptions…
What happens if an exception occurs?
control is passed to pre-defined exception handling routine
How does exception handling usuallly occur in FSMs?=
by means of state change at higher levels
-> resulting in the interruption or terminaiton of a systems regular behavior
Why can non-determinism be a good tool to employ during modelling a system?
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
What has to be considered w.r.t. non-determinism in the final stage of the modelling process?
at end of desing process all non-determinisms have to be eliminated
Last changed2 years ago